본문 바로가기

DP

 (58)
[Python] 12070번 gNumbers (Small) / 12071번 gNumbers (Large) https://www.acmicpc.net/problem/12070https://www.acmicpc.net/problem/12071 24/05/21  스몰과 라지 풀이 방식이 거의 유사해서 같은 글로 적어보려고 한다.  문제 접근 방식:  문제 설명에 앞서서 편의 상 선공이 지는 포지션을 Cold position, 선공이 이기는 포지션을 Hot position이라고 부르겠다. 문제의 내용은 Small문제에 들어가면 wizardrabbit님이 번역해놓은 것이 있으므로 이를 참고해보자.https://www.acmicpc.net/board/view/143383 Small의 경우는 제한이 $N = 1, 000$까지이므로, DP배열을 $1,000$까지 선언하여 DP를 돌리면 된다. 이 때 어떤 숫자가 g-num..
[Python] 28218번 격자 게임 https://www.acmicpc.net/problem/28218 24/05/24  간단한 게임 DP 문제이다. 최근 게임 이론 문제들을 많이 풀어보고 있는데, 꽤나 재미있다. 문제 접근 방식:  접근 방식은 나이브한 게임 DP이다. 골드 난이도에서 진행되는 게임 DP는 스프라그-그런디 정리가 섞이는 경우가 없기 때문에, 그냥 누가 이기는지 지는지에 대한 여부만 DP배열에 저장해주면 된다.(즉, 님버를 굳이 저장할 필요가 없다.) 선공이 지는 포지션을 0으로 저장하고, 선공이 이기는 포지션을 1로 저장하자. 내가 어떤 행동을 통해 말을 움직이면, 움직여진 게임 판 그대로 상대방이 처음부터 시작하는 것과 같다. 즉, 내가 어떤 행동을 통해 말을 움직여서 나의 턴을 끝내면, 그 상태 그대로 상대방이 선공으..
[Python] 15681번 트리와 쿼리 https://www.acmicpc.net/problem/15681 24/03/29  트리 DP를 연습할 수 있는 아주 좋은 문제다. 이전에 해결했던 문제를 복습하는 겸, 글로 작성해본다.  문제 접근 방식:  나이브하게 각 쿼리마다 위의 값을 일일히 구해서 내보내려고 한다면, 최악의 경우 $\mathcal{O}(QN)$이 소요된다. 각 쿼리마다 DFS를 한 번 진행할 것이고, 트리에서의 DFS는 $\mathcal{O}(N)$의 시간 복잡도가 소요되기 때문이다. 따라서, 한 번의 DFS를 진행하여, 그 결과를 저장해야한다. 즉, DP를 진행하는데, DFS를 진행하며 DP를 진행하면 된다. 탑다운 DP의 구현 방식과 비슷한데, 트리 DP는 서브 트리 별로 문제를 분할하는 것이 핵심이다. DP 점화식을 다음..
[Python] 28422번 XOR 카드 게임 https://www.acmicpc.net/problem/28422 24/04/10  간단한 DP문제다. 이 문제를 통해 파이썬의 bit_count라는 좋은 내장함수를 알 수 있었다. 문제 접근 방식:  문제를 요약하면, 쌓인 카드 더미에서 카드를 2장 혹은 3장씩만 가져갈 수 있는데, 카드에 쓰인 모든 숫자를 XOR하고 그 값을 이진수로 변환했을 때 1의 개수만큼 내가 점수를 획득할 수 있다고 한다. 그때, 이 게임에서 얻을 수 있는 최고의 점수를 구하는 것이 문제이다. 카드는 2장 혹은 3장 단위로만 가져갈 수 있으므로 마지막에 카드가 1장이 남는 상황이라면 모든 점수가 0이 된다. 다음과 같이 DP식을 세우자.$$DP[i] = i\text{장을 가져갔을 때 얻을수 있는 최고 점수}$$ 이 식에 따르..
[Python] 2600번 구슬게임 https://www.acmicpc.net/problem/2600 24/05/13  단순한 님 게임의 변형으로 해결할 수 있는 문제다. 스프라그-그런디 정리를 배우면서 님버에 대한 개념을 익혔다면 쉽게 해결할 수 있는 문제다. 그 외에도 이차원 DP로도 해결할 수 있다. 문제 접근 방식:  나는 이 문제를 스프라그-그런디 정리를 공부하며 얻은 지식인 님버를 활용하여 문제를 해결했다. 결국 이 문제는 님 게임의 변형이고, 처음 두 통에 들어 있는 구슬의 수가 최대 $500$개로 제한되어있기 때문에 충분히 빠른 시간 안에 님버를 구할 수 있다. 또한, 내 차례 때 할 수 있는 행동의 가지 수가 최대 $3$가지이기 때문에 각 숫자 별로 구하는 님버가 최대 $3$까지임을 확인할 수 있다. 현재 게임 판의 님버를..
[Python] 5069번 미로에 갇힌 상근 https://www.acmicpc.net/problem/5069 5069번: 미로에 갇힌 상근 상근이는 오른쪽 그림과 같은 미로에 갇혀있다. 미로는 육각형 모양의 방이 계속해서 붙어있는 모양이고, 이러한 방은 무수히 많이 있다. 또, 인접한 방은 문으로 연결되어 있어서, 한 방에서 다 www.acmicpc.net 24/02/01 DP문제로, 골드 4보다는 훨씬 어렵다고 느껴졌던 문제입니다. 문제 접근 방식: 처음에 접근했던 방식은, 초기 몇 개의 항을 문제에서 주어진 그대로 브루트포스+백트래킹을 사용하여 구한 뒤, OEIS를 이용해 답을 구한 방식이었습니다. 이 문제에 대한 OEIS링크는 아래에 있습니다. https://oeis.org/A002898 A002898 - OEIS A002898 Number..
[Python] 31530번 새로운 AVL 트리 만들기 https://www.acmicpc.net/problem/31530 31530번: 새로운 AVL 트리 만들기 첫 번째, 두 번째, 세 번째, 네 번째 테스트 케이스의 경우 아래와 같이 $1$가지, $1$가지, $4$가지, $15$가지이다. www.acmicpc.net 24/03/21 간단한 DP문제로, 토글링의 방법으로 해결할 수 있는 문제다. 문제 접근 방식: DP테이블을 다음과 같이 정의하자. $$DP[i][j] = \textrm{높이가 }i\textrm{이고 가능한 균형값의 상태가 }j\textrm{일 때의 경우의 수}$$ 이때, 가능한 균형값의 상태는 다음과 같이 정의한다. $$j = 0, 1, 2 \rightarrow \{-1\} , \{0\} , \{1\}$$ $$j = 3, 4, 5 \rig..
[Python] 27114번 조교의 맹연습 https://www.acmicpc.net/problem/27114 27114번: 조교의 맹연습 첫 번째 줄에 각각 좌로 돌아, 우로 돌아, 뒤로 돌아에 들어가는 에너지를 나타내는 세 정수 $A, B, C$와 사용하고자 하는 총 에너지양을 나타내는 정수 $K$가 공백으로 구분되어 주어진다. $(1\leq A,B www.acmicpc.net 24/02/26 간단한 DP문제로, 처음엔 BFS로 잘못 접근했던 문제이다. DP테이블 정의와 점화식 유도는 빠르게 할 수 있었지만, 자잘한 실수가 있어서 아쉬웠다. 문제 접근 방식: $K$만큼의 에너지를 소모하여 처음 바라보고 있던 방향으로 제식 연습을 끝마쳤을 때 제식 수행 횟수의 최솟값을 구하는문제이다. 처음에는 BFS로 접근하고, 과도한 루프 방지를 위해 일정 ..

티스토리툴바