알고리즘/algospot
-
카쿠로알고리즘/algospot 2016. 12. 11. 16:49
스도쿠나 N-Queens 문제들을 마주할 때면 가슴이 답답하다. 냅색이나 LIS 처럼 차곡차곡 상황들을 쌓아 갈 수 없을 뿐더러 두더지 게임 처럼 하나의 조건을 해결하면 또 다른 문제가 튀어나오니 도대체 어떻게 풀어야 할 지 감을 잡을 수 없었다. 이러한 유형의 문제를 보면 정말 머리 좋은 친구들이 푸는건가보다 하고 그냥 넘어 갔던 것 같다. 알고리즘 해결 전략에서는 스도쿠, N-Queen 그리고 가쿠로 문제처럼 특정한 제약에 해당하는 답을 찾는 문제를 제약 충족 문제라고 한다. 조합 탐색 문제들 중에 하나인데 먼저 조합 탐색은 기존에 사용했던 알고리즘(DP, 탐욕법 등등)을 사용 할 수 없고 가지치기를 통해 검사 할 필요가 없는 경우들을 미리 쳐내는 방법이다. 제약 충족 문제는 조합 문제에서 한 발 더..
-
회전초밥알고리즘/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..
-
조합게임알고리즘/algospot 2016. 7. 25. 21:27
난 항상 이런 문제가 싫었다. - 현재 상태에서 두 선수가 최선을 다했을때 승자는 누가 될 것인가. 여기서 두 선수가 최선을 다한다는 문제의 조건이 항상 마음에 들지 않았다. 도대체 두 선수가 최선을 다한다는 것을 어떻게 정의한다는 것인가? 어떤 경우가 최선을 다하는 것이고 어떤 경우는 최선을 다하지 않는 것인가? 하지만 알고리즘 문제해결전략 책을 탐독한 결과 이런 경우는 현재 상태로부터 가능한 모든 상태를 수를 고려했을때(컴퓨터의 빠른 연산 능력을 이용해) 내가 이길 수 있는지 없는지를 판독해내는 과정이다. 책에서 나온 예제로는 Tic Tac Toc가 있었다. 여기서 책에서 큰 깨달음을 얻은 부분이 "현재의 참가자는 모든 수를 둬 보면서 다음 상태 board에 대해서 이길 수 있는 수가 있으면 무조건 ..
-
ASYMTLING알고리즘/algospot 2015. 2. 21. 12:31
내가 스스로 풀때는 n개를 채울 때 대칭인 경우와 비대칭인 경우로 나누어서접근하려고 했는데 그렇게 풀 필요가 전혀 없었다.책에서 양 끝에서부터 채워가는 방식을 읽고 정말 놀랬다 ㄷㄷㄷㄷ이렇게 생각하면 정말 쉽게 풀리는 구나... 재귀함수의 매력에 놀랬고 저자의 천재성에 감탄하고 나의 부족함을 다시한번 깨달았다 ㅠㅠ양끝이 대칭이면 내부는 비대칭이어야 하고양끝이 비대칭이면 내부는 대칭이어야 한다. 이 경우로 모든 경우의 수를 만들 수 있었다...dp로 문제를 해결하는 두 가지 조건- 모든 경우의 수를 포함해야 하며- 중복되는 경우가 있어선 안된다를 다시 한번 실감하는 순간이었다