알고리즘/acmicpc
-
1976알고리즘/acmicpc 2015. 3. 29. 16:16
딱 보면 알고리즘에 배운 Floyd Warshall로 해결 할 수 있을 것 같지만 Floyd Warshall 알고리즘은 나중에 한 값이 이전에 한 값에 영향을 줄 수 있는 문제점이 있다. 즉 나중에 연결 한 선이 이전에 연결한 선까지 변경 할 수 있다는 말이다(말이 좀 어렵다. 그림으로 표현하면 쉬울것 같은데 그림 그리자니 그건 귀찮고) 그래서 내가 10달전에 제출해보았던 코드들은 대부분 Floyd 알고리즘을 썼더니 모두 틀렸다. 새롭게 생각해낸 방법은 다익스트라 알고리즘을 이용한 방식이다. 한 점을 루트 로 잡고 그 점으로 부터 bfs 탐색을 한다 여기서 bfs로 거쳐가는 노드들은 모두 루트로부터 연결이 가능한 노드들이다. 난 좀 무식하게 해서 모든 점을 루트로 잡아서 연결을 했다. 그러면 이건 나중에..
-
1199알고리즘/acmicpc 2015. 3. 1. 17:50
문제가 좀 불친절 한 것 같다. 여기서 입력이 핵심인데 두 정점 사이에 간선이 여러개 있을 수 있다고 한다. 그런데 간선이 여러개 있는 것을 어떻게 표현할 것인가에 대한 설명은 없다. 그래서 나는 주어진 간선 이차원 배열에서 입력받는 정수가 두 정점 사이의 간선의 개수라 생각하고 문제를 풀었다. 나머지는 오일러 회로 문제라 생각하면 된다. 오일러 회로의 성립 요건은 모든 정점의 인접한 간선의 수가 짝수여야 한다는것 이걸로 오일러 회로가 성립 하지 않는 경우에 대해서 -1을 출력했고 성립하는 경우 정점 출력 순서는 주위의 간선이 존재하지 않는 것으로 stack을 이용했다. 여기서 속도 문제가 있었는데 그거는 각 노드마다 자신과 인접한 노드를 queue로 저장해서 관리하는 방법으로 해결했다. 그러면 매번 각..
-
4256알고리즘/acmicpc 2015. 2. 28. 19:40
전위탐색에서의 값을 중위탐색에서 찾으면 그것의 왼쪽에 있는 것들은 left child, 오른쪽에 있는 것들은 right child이다. 이 성질을 이용해서 풀면 쉽게 풀수있다. 재귀함수를 이용해 좀 더 깔끔히 푸는 방식이 있으나 나는 규칙성과 stack을 같이 응용해 풀었다. #include #include #include using namespace std; int d[1005]; int pre[1005]; int ior[1005]; int main() { int tc, size; stack s; scanf("%d", &tc); d[0]=1; while(tc--) { scanf("%d", &size); d[size+1]=1; for(int i=1; i
-
2156알고리즘/acmicpc 2015. 2. 28. 18:23
바로 전 문제 dp를 쉽게 풀어서 이 문제 만만히 봤는데 4번맞에 맞았다;; 너무 내가 성급히 접근한것 같다. 경우의 수를 좀 철저히 따져봐야 했는데. 문제의 핵심은 연속 3잔은 마실 수 없다는 것이다. 그러면 경우의 수로 나눌 수 있는데 1 2 3 4 5 6 이렇게 포도주가 있으면 12 3 45 6 하나를 공백으로 두고 마시는 경우와 12 3 4 56 두개를 공백으로 두는 경우 그리고 1 2 3 4 5 6 하나씩 공백으로 두는 경우로 나눌 수 있다. 이 문제를 풀기위한 자료구조로 이차원 배열을 생각해냈다 d[][2] -> d[][0]는 현 위치에서 연속이 끝나는, d[][1]는 현 위치에서 연속이 시작하는 위의 모든 경우와 자료구조를 정의했으니 다음과 같은 점화식을 낼 수 있다. d[here][0] -..
-
10159알고리즘/acmicpc 2015. 2. 28. 13:54
처음에 이 문제를 읽을때 위상정렬을 써야하나 깊이 고민했는데 올림피아드 문제에서 대학생들이 공부하는 위상정렬을 여기서 쓰겟나 싶어서 간단히 접근한결과 무식하게 풀기를 생각해냈다. 이차원 배열을 선언하고 다음과 같이 정의한다. judge[from][to] from과 to의 값을 비교 결과를 저장하는 배열이다. from to 이면 1, 알수 없으면 0으로 저장한다. 여기서 너무도 당연한 사실을 생각 할 수 있는데 from < to 이면 from과 from보다 작은 값들과, to와 to보다 높은 값들과 비교를 할 수 있다는 사실 그래서 난 from과 from보다 작은 값들을 loser라는 벡터에 두고 to와 to보다 높은 것들을 winner라는 벡터에 두어서 (judge[][]함..
-
9489알고리즘/acmicpc 2015. 2. 26. 23:35
예전에는 왜 이렇게 많이 틀렸을까 보니... 입력이 1 2로 시작하는 경우를 생각 안해서 그런것 같다 이런 경우는 트리가 두개 생길 수 있는데 나는 그냥 하나의 트리로 놓고 문제를 풀었으니 틀릴수밖에... 조금은 불친절한 문제인것 같다, 이런 경우도 있다는걸 알려줘도 무방 할 것 같은데 뭐 이런것도 실력이니까; #include #include #include #include using namespace std; struct Node{ int root, idx; vector children; }; Node data[1005]; int main() { int n, k, bfo, cur, root, tgt_idx; queue q; Node tmp; while(1) { scanf("%d %d", &n, &k);..
-
2517알고리즘/acmicpc 2015. 2. 26. 21:54
처음에 바로 BIT로 풀어야지 했다가 정수의 범위가 1000000000까지인걸 단순히 BIT로 접근해선 안되겠음을 깨달았다. 이전까지 탐색한 정보들을 Heap에 넣어둘까 하다가 최악의 경우가 O(n*n)이라 별 소용이 없음을 생각하고 다른 방법을 강구... 그러다가 어차피 선수의 수가 500000이하니까 1~1000000000을 1~500000로 좁히는 방법을 생각했다. 방법은 1~1000000000의 data들을 정렬해서 그 data의 index값을 BIT에 쓰는 방법이다. 해당 index 값을 찾는 과정은 이진 탐색이니까 O(log(500000))으로 확 준다. 그러면 BIT에 index값까지의 합을 확인하고 현재까지 탐색한 선수의 수를 빼주고 그 index에 1만큼 update한다. 이 과정은 O(..
-
2568알고리즘/acmicpc 2015. 2. 25. 13:33
초등부의 전깃줄 문제에서 한발 나아간 문제.기본적으로 LIS를 이용해서 풀 수 있는 것은 똑같지만 Input의 개수가 1000배이상 증가해서O(N*N) 기본탐색 알고리즘을 사용하면 시간초과가 날게 틀림없으므로좀 더 효율적인 자료구조를 활용해 속도를 높일 필요가 있었다. 나는 priority queue를 이용해서 풀었는데priority queue는 이전 까지 탐색했던 line중에서 LIS값이 높은 순위로 저장되어있다.priority queue는 pair로 이루어져 있는데 pq가 pair.first를 통해서 정렬한다는 점을 알면 구현하기 편리하다 d값, value값, idx값 총 세가지 값이 필요한데 나는 pair.second로 idx값을 넣어서 value값은 넣지 않고 idx값을 통해서 참조 할 수 있게 ..