전체 글
-
11437알고리즘/acmicpc 2016. 7. 30. 14:21
LCA를 푸는 문제다. LCA 최적화 알고리즘은 이미 정리해두었으니 넘기자. 문제에 주어진 간선을 가지고 어떻게 트리의 형태로 만드느냐가 LCA를 풀기 위한 조건이다. 일반적으로 간선에 대한 자료구조들은 2차원 배열을 이용해서 표현하지만 N이 10000을 넘어가면 2차원 배열의 최대 크기를 초과하게된다. C++에서는 vector를 사용해서 위와같은 문제를 간단히 해결 할 수 있지만 경우에 따라서 vector를 사용하지 못하는 상황도 존재한다. 간선 정보들을 필요할 때 마다 신속히 접근하는 자료구조가 중요한데 매번 모든 간선 정보O(N)를 찾아볼 수도 없을 노릇이다. 이런 경우에는 특정 경우 대해서 정렬을 해주는 방법이 유용하다. 간선에 대한 정보를 from들에 대해서 정렬을 해주고 각각의 시작점을 확인해..
-
LCA(Lowest Common Ancestor)알고리즘/자료구조 2016. 7. 30. 13:24
트리 내부에 있는 두개의 노드 사이의 최저 공통 조상을 효율적으로 찾아주는 자료구조이다. 가장 간단히 생각 할 수 있는 구현방법(모든 모드를 일일히 탐색하는)으로는 최저 공통 조상을 찾는데 O(N)의 시간이 걸리지만 최적화된 LCA 알고리즘으로는 O(logN)시간만에 구할 수 있다. LCA 알고리즘에서 트리의 노드들은 자신의 부모노드에 대한 정보외에 현재 높이에서 2^i 위에 위치한 조상노드에 대한 정보도 가지고 있다.그림으로 표현하면 다음과 같다. (자신의 부모노드 뿐만 아니라 2^i위치에 해당하는 조상노드의 정보를 가지는 것은 빠른 탐색을 할 때 유용하게 쓰인다.) 알고리즘의 절차는 다음과 같다. 1. 두 노드의 depth가 다르다면 depth를 맞춰준다.* 이때 일일히 모든 부모노드를 방문하는 것이..
-
조합게임알고리즘/algospot 2016. 7. 25. 21:27
난 항상 이런 문제가 싫었다. - 현재 상태에서 두 선수가 최선을 다했을때 승자는 누가 될 것인가. 여기서 두 선수가 최선을 다한다는 문제의 조건이 항상 마음에 들지 않았다. 도대체 두 선수가 최선을 다한다는 것을 어떻게 정의한다는 것인가? 어떤 경우가 최선을 다하는 것이고 어떤 경우는 최선을 다하지 않는 것인가? 하지만 알고리즘 문제해결전략 책을 탐독한 결과 이런 경우는 현재 상태로부터 가능한 모든 상태를 수를 고려했을때(컴퓨터의 빠른 연산 능력을 이용해) 내가 이길 수 있는지 없는지를 판독해내는 과정이다. 책에서 나온 예제로는 Tic Tac Toc가 있었다. 여기서 책에서 큰 깨달음을 얻은 부분이 "현재의 참가자는 모든 수를 둬 보면서 다음 상태 board에 대해서 이길 수 있는 수가 있으면 무조건 ..
-
2253알고리즘/acmicpc 2016. 7. 24. 13:10
위 문제는 가속/감속을 최대 1 만큼 한다는 것에 힌트가 있다. 돌의 개수가 최대 10000개 일 때 최대로 낼 수 있는 속도는 142이다. K*(K+1)/2 < 10000 현재 위치의 돌과 돌에 도착할 때의 속도로 새롭게 정점을 표현한다면 최대 정점의 개수는 10000 * 142 로 배열 내에서 선언이 가능한 범위가 된다. dp[N][V] : N번째 돌에 V번째 속도로 도착할 때의 최소 점프횟수 이제 각각의 정점을 방문해서 다음 위치에 움직일 때 최소 횟수로 움직이는 값을 업데이트 해주면 된다. #include #define MAXN 10000 int dp[MAXN + 5][200]; int forbid[MAXN]; int main() { int N, M; int i, j, tmp; int ans; f..
-
11049알고리즘/acmicpc 2016. 7. 24. 12:14
DP의 예시로 알고리즘 책에서 자주 나오는 유형 DP는 배열의 인덱스 값을 얼마나 유용하게 잘 사용하느냐에 달려있는 것 같다. dp[FROM][TO] : FROM부터 TO까지의 행렬들을 곱할 때의 값 위 값을 통해서 지속적으로 업데이트 해나가면 문제를 풀 수 있다. #include #define MAXN 500 int dp[MAXN][MAXN]; int data[MAXN][2]; int main() { int N; int i, j, len; freopen("input.txt", "r", stdin); scanf("%d", &N); for (i = 0; i < N; i++) scanf("%d%d", &data[i][0], &data[i][1]); for (len = 1; len < N; len++) { f..
-
2229알고리즘/acmicpc 2016. 7. 24. 11:38
나이순으로 정렬이 이미 되었으니 해야 할 일은 여기서 연속된 배열을 어떻게 여러개로 나눠서 최대의 점수를 내는 조를 만드느냐이다. (문제가 나이 정렬을 해주지 않고 냈으면 더 어려울 뻔 했는데 친절하게 나이 정렬을 해준 뒤에 문제를 풀라고 했다) 위 문제는 DP로 풀 수 있다. 먼저 다음과 같은 배열을 선언한다 dp[FROM][TO] : FROM학생부터 TO학생까지 조를 짤 때의 최대의 점수가 나오는 경우 목표는 FROM, TO까지 무조건 최대의 점수를 가지는 것이며 어떻게 분할 되는지는 상관하지 않는다 FROM에서 TO까지의 범위를 차근차근 늘려서 1번 학생부터 N번 학생가지 포함되는 경우까지 만들어준다. #include #define MAXN 1000 #define MAX(A, B) ((A) > (B..
-
Count sort알고리즘/자료구조 2016. 7. 23. 19:47
quicksort나 mergesort처럼 일반적인 sorting알고리즘은 O(NlogN)을 가지나 sorting에 사용되는 값들을 사전에 알고 있는 경우에는 시간복잡도를 O(N)까지 단축 시킬 수 있다. 그중에서도 가장 강력하게 사용되는 알고리즘이 Count sorting이다. Count sorting은 정렬에 쓰이는 값이 충분히 작은 경우(배열의 최대 크기가 될 수 있는 값보다 작아야 한다)에 주로 사용할 수 있다. 배열의 인덱스는 이미 자동적으로 정렬되있으니 수열에 포함된 값 각각의 개수를 배열의 인덱스에 해당하는 값에 저장해둔 후 그 그 개수를 참고해서 정렬하는 방식이다. 글로 설명하기에는 어려우니 예를 들어보자. 5 3 6 7 4 5 인 수열을 정렬한다고 하자. 위 수열의 각 값의 개수를 관리하는..
-
4307알고리즘/acmicpc 2015. 10. 17. 22:58
처음에는 '와 이 문제 장난아니다. 어떻게 풀어야되냐, 감이안온다 ㄷㄷ' 라 생각했는데 자세히 생각해보니 매우 간단한 문제임을 발견했다. 두 개미가 부딪히면 다른 방향으로 이동한다. 이건 둘이 교차한다는 의미랑 같다. 어차피 충돌하면 한 개미는 왼쪽으로 이동하고 다른 개미는 오른쪽으로 이동한다. 그러면 이건 교차한다고 봐도 무방하다. 결국 막대기를 벗어나는 개미들 중에 가장 오랜 시간이 걸리는 애를 고르면 되는 문제.. #include int main(){ int tc; scanf("%d", &tc); while(tc--){ int len, n, loc, min=0, max=0; scanf("%d %d", &len, &n); while(n--){ scanf("%d", &loc); int cur_min, ..