알고리즘 (382) 썸네일형 리스트형 [Python] 8170번 Pebbles (추후 보강 예정) https://www.acmicpc.net/problem/8170 24/05/19 스프라그-그런디 문제로, 증명하기가 꽤나 어렵고 규칙을 발견하는 것도 쉽지 않은 문제인 것 같다. 나는 이 문제를 해결하기는 했지만, 왜 그렇게 나오는지에 대한 증명은 하지 않아서, 추후에 증명을 하게 된다면 보강해서 작성할 예정이다. 문제 접근 방식: 처음에 문제를 접근한 방식은 나이브한 탑-다운 DP였다. 가지고 있는 현재 조약돌의 전체 상황을 튜플로 저장하여, 그 상황을 딕셔너리에 집어넣는 풀이였다. 당연히 시간초과를 받을 수 밖에 없었는데, 잘 생각해보면 돌 더미의 개수가 최대 $1,000$개이고, 내가 어떤 게임판의 상황에서 할 수 있는 행동 또한 정말 많기 때문에 시간초과가 날 수밖에 없다. 그래서 규칙을 찾.. [Python] 5981번 Cow Checkers https://www.acmicpc.net/problem/5981 24/05/23 모르면 쳐맞는 종류의 게임 이론 문제인 것 같아서 따로 정리해야겠다, 싶어 정리해본다. 문제 접근 방식: https://en.wikipedia.org/wiki/Wythoff%27s_game Wythoff's game - WikipediaFrom Wikipedia, the free encyclopedia Two-player mathematical subtraction game Wythoff's game is played with two piles of counters Wythoff's game is a two-player mathematical subtraction game, played with two piles of .. [Python] 31687번 Trokut https://www.acmicpc.net/problem/31687 24/05/18 스프라그-그런디 정리 문제이다. 약간 웰노운 성이 있는 것 같아서, 정리해보면 좋을 것 같아 글을 써본다. 문제 접근 방식: 문제의 접근 방식은 이전에 내가 글로 작성했던 다각형 게임과 동일하다. 심지어, 해당되는 게임조차 같다. 근데 다각형 게임의 코드를 그대로 복붙하면 시간초과를 받는다.2022.11.01 - [알고리즘/백준 문제 풀이] - [Python] 13034번 다각형 게임 / 16187번 Game on Plane [Python] 13034번 다각형 게임 / 16187번 Game on Planehttps://www.acmicpc.net/problem/13034 13034번: 다각형 게임 N개의 꼭짓점으로 이.. [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 업다운 랜디를 하다가 만난 문제로, 간단하게 그리디적 발상 + 살짝 귀찮은 구현을 요구하는 문제이다. 문제 접근 방식: 그림을 잘 관찰해보면, 빨간색 모양의 초콜릿은 뾰족한 부분이 위에 올라와있고, 파란색 모양의 초콜릿은 뾰족한 부분이 밑으로 내려와 있음을 확인할 수 있다. 따라서 위에서부터 아래로, 왼쪽에서부터 오른쪽으로 탐색을 진행할 때, 아직 발견하지 않은 빨간색 초콜릿을 발견한다면, 이는 빨간색 초콜릿의 뾰족한 부분이라고 결론 지을 수 있다. 마찬가지로, 똑같은 방법으로 탐색을 진행할 때 아직 발견하지 않은 파란색 초콜릿을 발견한다면, 이는 파란색 초콜릿의 평평한 부분이라고 결론 지을 수 있다. 따라서, 배열을.. 이전 1 ··· 7 8 9 10 11 12 13 ··· 48 다음