알고리즘
-
회전초밥알고리즘/algospot 2016. 8. 1. 23:06
항상 이런 DP문제들을 보면 어떤 값을 배열의 index로 표현할까가 나의 관심사였다. 가장 배열에 넣을 만한 값들은 예산에 해당하는 값들이었고 이 값들이 배열의 최대 범위를 초과하지 않기를 기도할 뿐이었다. 하지만 최대 범위를 초과한다면.. 그 문제는 내겐 그때부터는 DP문제가 아니였다. 어떻게 최적화 할 것인가 머리를 짜매다가 풀지 못한 문제로 남아버렸다. 책에서본 회전초밥문제도 그랬다. 단순 DP문제로 풀 수 있을 줄 알았는데 예산의 범위가 10^9이하여서 배열로 넣기는 무리였다. 문제의 힌트로 가격이 항상 100의 배수라 10^7정도는 배열에 넣으면 되겠다 생각했는데 메모리의 크기 제한이 64MB였다. int형으로 배열의 크기가 10^7로 잡자니 메모리가 초과할 것 같고 그렇다고 최대한 메모리를 ..
-
블록게임알고리즘/algospot 2016. 8. 1. 22:11
조합게임의 예제로 나온 문제. 모두가 최선을 다했을 때 이길 수 있는 경우에 대한 것은 앞에서 설명했으니 넘어가고 블록과 보드게임의 상태를 비트 연산을 이용해 어떻게 깔끔히 표현했는지에 주목하자. void precalc() { for(int y = 0; y < 4; y++) for (int x = 0; x < 4; x++) { vector cells; for (int dy = 0; dy < 2; dy++) for (int dx = 0; dx < 2; dx++) cells.push_back(cell(y + dy, x + dx)); int square = cells[0] + cells[1] + cells[2] + cells[3]; for (int i = 0; i < 4; i++) moves.push_back..
-
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..