전체 글
-
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[][]함..
-
오일러회로알고리즘/자료구조 2015. 2. 27. 15:21
오일러 회로는 그래프의 모든 간선을 방문하고 시작점과 끝점이 같은 회로를 말한다. 우리에게는 연필로 모든 간선을 칠하고 다시 돌아오는 것으로 친숙하다. 별표그릴때를 생각해보면. 이 회로를 만들기 위한 조건은 각 정점들마다 나가고 들어오는 간선의 수가 같아야 한다(무방향의 그래프는 정점과 연결된 간선의 수가 짝수개여야 한다) 정말 간단히 생각하면 된다. 어떤 정점의 나가는 간선의 수가 들어오는 간선의 수보다 적다면 그 정점으로 들어오는 간선들은 아직 방문하지 못한채 그 정점에서 나가지 못하게 된다. 위의 그림에서 정점은 2개의 나가는 간선과 3개의 들어오는 간선이 있다. 검은색 간선은 이미 방문 한 것이고 파란색 간선은 아직 방문하지 않는 것이다. 현재 위치는 정점 3인데 여기서 더이상 어느 곳으로 나갈 ..
-
트라이알고리즘/자료구조 2015. 2. 27. 14:35
요즘 운영체제에서는 단어 몇글자만 치면 자동완성 기능을 제공하는데자동완성의 기본 알고리즘이 바로 트라이다. 자동완성을 만들려면 사전에 입력한 단어들을 저장하고 빠른시간안에 탐색 할 수 있어야 한다. 하지만 문자열은 숫자로 이루어진 이진트리와 달리 원소 비교를 상수시간 내에 할 수 없으므로 특화된 자료구조가 필요하다. 이때 유용한 자료구조가 트라이다. 구조는 다음과 같다. 만약 내가 TR, THE, TRY, TREE라는 단어를 저장해두었다고 하자. 그러면 다음과 같은 트리가 형성된다. 각각의 단어의 공통된 접두사를 부모로 두는 방법이다. 하지만 공통된 접두사가 내가 입력한 단어가 아니라면 bool 값을 이용해서 표현해야한다. 그림에는 하얀색 바탕으로 표현했다. 위 자료구조의 시간 복잡도는 트리의 높이로 볼..
-
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값을 통해서 참조 할 수 있게 ..