본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 19778번 Игра https://www.acmicpc.net/problem/19778 24/05/20  그룹 연습 문제로 풀었던 문제다. 간단한 게임 이론 + 구현 문제다. 최적의 전략을 생각하는 것이 그다지 어렵지는 않지만, 이를 실제로 구현하는 것이 전략을 생각하는 난이도에 비해서 조금 까다로운 편이다. 골드 5에 비해 난이도가 낮다고 생각이 되어서 낮게 측정했다. 문제 접근 방식:  러시아어로 되어 있는 문제이기 때문에 번역을 하면 다음과 같이 번역할 수 있다. 문제 번역:체육 수업 시간에 1학년 페티야와 바샤가 흥미로운 게임을 하고 있습니다. 남학생들 앞에 높이가 다른 $n$개의 기둥이 일렬로 서 있습니다. 남학생들은 $m$개의 반지를 가지고 번갈아 가며 기둥에 던지는데, 기둥에 이미 반지가 있으면 이 기둥에 반지..
[Python] 27852번 Kruskal https://www.acmicpc.net/problem/27852 24/05/17  오랜만에 스프라그-그런디 정리 문제를 해결했기에 글로 작성해본다. 님 게임의 변형 문제로, 어떻게 해야 님 게임으로 치환할 수 있을지를 고민해볼 수 있는 좋은 문제이다. 문제 접근 방식:  문제에서 제시하는 상황은 다음과 같다. 일반적인 님 게임과 비슷하게, 돌 더미들이 여러 개 주어져 있다. 대신, 한 플레이어가 $1$개부터 $K$개까지 돌을 가져갈 수 있으며, 승리 조건이 어느 한 플레이어가 "소수"개수에 해당하는 돌 더미를 만들게 되면 즉시 이기게 되는 게임으로 바뀌었다. 두 플레이어가 최선의 플레이를 진행한다고 할 때, 누가 이길 지를 판별하는 것이 문제의 요구조건이다. 님 게임의 변형으로 돌 개수의 제한을 두는..
[Python] 21772번 가희의 고구마 먹방 https://www.acmicpc.net/problem/21772 24/05/14  업다운 랜디를 하다가 만난 문제이다. 처음에는 BFS로 접근할까 하다가 DFS로 방향을 틀어 접근했다. 문제 접근 방식:  BFS로 접근할 수도 있다. 그 이유는 최대 10번을 탐색하고 한 번 할 때 4방향을 탐색하기 때문에 $4^{10}$번만 탐색하면 충분하고, 이는 시간 안에 들어오기에 충분하기 때문이다. 하지만 DFS로 접근하는 것이 더 쉬울 것 같아서 DFS로 접근했다. 무의식 중에 재귀 깊이를 10만으로 늘린 코드를 작성하긴 했지만, 사실은 10번만 탐색하기 때문에 그렇게까지 깊게 늘리지 않아도 되었던 것 같기도 하다. DFS를 진행하는데, 들어간 자리에 고구마가 있으면 고구마를 먹었다는 표시로, 고구마 글자를..
[Python] 30959번 앙상블할래? https://www.acmicpc.net/problem/30959 24/05/14  간단한 브루트포스 문제다. 파이썬은 이러한 문제에 있어서 쉽게 구현을 할 수 있어서 좋은 것 같다. 문제 접근 방식:  $N$의 제한이 $16$까지이고, 항상 홀수 개의 모델만 선택한다고 했으므로 전수조사를 해도 충분히 시간안에 들어올 수 있음을 생각할 수 있다. 하나의 조합을 통해 앙상블을 구성하는 것은 조합의 크기와 예측 항목의 개수를 곱한 크기에 비례함을 확인할 수 있다. 그 수가 그렇게 많지 않으므로, 모든 조합을 확인해보면 된다. 파이썬의 itertools 모듈의 combinations함수를 사용하면 n개 중 r개를 선택하는 모든 조합의 경우들을 확인할 수 있으므로, 이를 사용하여 쉽게 구현할 수 있다. 인덱스..
[Python] 31462번 삼각 초콜릿 포장 (Sweet) https://www.acmicpc.net/problem/31462 24/05/14  업다운 랜디를 하다가 만난 문제로, 간단하게 그리디적 발상 + 살짝 귀찮은 구현을 요구하는 문제이다. 문제 접근 방식:  그림을 잘 관찰해보면, 빨간색 모양의 초콜릿은 뾰족한 부분이 위에 올라와있고, 파란색 모양의 초콜릿은 뾰족한 부분이 밑으로 내려와 있음을 확인할 수 있다. 따라서 위에서부터 아래로, 왼쪽에서부터 오른쪽으로 탐색을 진행할 때, 아직 발견하지 않은 빨간색 초콜릿을 발견한다면, 이는 빨간색 초콜릿의 뾰족한 부분이라고 결론 지을 수 있다. 마찬가지로, 똑같은 방법으로 탐색을 진행할 때 아직 발견하지 않은 파란색 초콜릿을 발견한다면, 이는 파란색 초콜릿의 평평한 부분이라고 결론 지을 수 있다. 따라서, 배열을..
[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] 28464번 Potato https://www.acmicpc.net/problem/28464 24/04/16  아주 간단한 그리디 문제다. 문제 접근 방식:  편의 상 박 모씨를 A, 성우를 B라고 부르겠다. 문제에서 요구하는 것은 A가 감자튀김을 최대한 많이, B가 감자튀김을 최대한 적게 가져가도록 하는 것이다. A가 먼저 감자튀김을 가져간다고 했다. 상식적으로 생각해보면, A가 감자튀김을 최대한 많이 가져가기 위해서는 감자튀김의 양이 가장 많은 접시부터 순서대로 가져가는 것이 이득일 것이다. 마찬가지로 B가 감자튀김을 최대한 적게 가져가도록 하기 위해서는 감자튀김의 양이 가장 적은 접시부터 순서대로 가져가는 것이 이득일 것이다. 따라서, 주어진 배열을 오름차순으로 정렬하여, 배열의 절반은 A가, 배열의 절반은 B가 가져가도록..

티스토리툴바