[2024 동계 모각코] 1주차 계획
1주차 계획
개요
1주차(1. 2~ 1. 7)의 계획입니다.
- 9장 DP 활용
- 조합 게임
- 문제: TICTACTOE
- 문제: NUMBERGAME
- 문제: BLOCKGAME
- 반복적 동적 계획법
- 문제: SUSHI
- 문제: GENIUS
- 조합 게임
조합 게임
문제: TICTACTOE
틱택토를 DP를 이용해서 기보가 주어졌을 때 누가 이기는지, 무승부인지 판별합니다.
Top-down 알고리즘으로 작성했습니다.
문제는 여기에
코드는 여기에 있습니다!
더 개선 가능한 부분으로는, 게임판을 좌우, 상하, 대각선으로 뒤집기, 90도 회전을 해도 승패는 동일하니 이를 이용해 프로그램을 빨리 만들 수 있다는 것입니다.
틱택토에는 의미가 없을 수 있으나 체스의 엔드게임 분석 알고리즘을 만들 때 유용한 테크닉입니다.
문제: NUMBERGAME
게임에서 플레이어 1이 플레이어 2와 차이를 낼 수 있는 숫자의 최대 합을 구하는 문제입니다.
이것 또한 Top-down 알고리즘으로 작성해서, int 포인터 두 개와 플레이어 1, 2 턴을 나타내는 bool 파라미터를 이용하여 DP를 적용한 재귀 함수를 선언했습니다.
이 문제는 작은 미니맥스 알고리즘입니다.
문제는 여기에
코드는 여기에 있습니다!
문제: BLOCKGAME
블록 배치도가 주어지면, 블록을 놓을 수 없으면 패배하는 게임입니다. 반대로 상대를 블록을 놓을 수 없게 하면 승리하는 게임입니다.
알고리즘의 구현은 잘 했으나, int[1 << 25]가 엄청나게 큰 숫자여서 런타임 에러가 발생했습니다. int[1 << 25]가 아닌 char[1 << 25]로 bitmask를 구현해야 했습니다.
문제는 여기에
코드는 여기에 있습니다!
반복적 동적 계획법
문제: SUSHI
공간 복잡도를 낮추기 위해 슬라이딩 윈도 기법을 활용하여 반복적 동적 계획법을 사용하는 문제입니다.
다이나믹 프로그래밍과 그리디 알고리즘을 섞어 쓸 수 있습니다!
포스트는 여기에 있습니다.
문제: GENIUS
Dynamic programming과 행렬 거듭제곱과 응용을 통해 푸는 문제입니다.
포스트는 여기에 있습니다.
돌아보며
어려웠던 문제
이번 주차는 그리 어려운 문제가 없었던 것 같습니다. 전 주차에 했던 내용들은 엄청나게 어려웠습니다만..
9장 DP활용 파트를 돌아봤을 때, 가장 어려웠던 문제는 KLIS였습니다.
문제: KLIS에 대한 포스트는 여기에 있습니다.
풀 때는 $O(n^2)$시간이 걸리는 반복적 동적 계획법으로 풀었으나, $O(n \times \log n)$시간 알고리즘이 또 있더라고요, 시간이 나면 풀어 볼 예정입니다.
Dynamic programming 정리
동적 계획법을 보통 DP + 재귀함수로 구현하나. 반복문 + DP table으로도 구현이 가능합니다.
반복문 + DP table의 조합으로 구현하는 것을 반복적 동적 계획법이라 합니다.
Subproblem 간의 의존성이 명확한 경우에 반복적 동적 계획법이 유리한 편이며
상황에 따라 두 가지 방법을 선택해서 구현하면 좋을 것 같습니다.