글 (385) 썸네일형 리스트형 [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$개의 반지를 가지고 번갈아 가며 기둥에 던지는데, 기둥에 이미 반지가 있으면 이 기둥에 반지.. 1. Internet Architecture Part 1 이 글은 제가 개인적으로 컴퓨터 네트워크를 공부하기 위해 작성하는 일련의 글들로, 오류 사항이 존재할 수 있으며, 잘못된 개념이 작성될 수도 있습니다. 또한 GPT를 적극적으로 사용하여 글을 작성하고 있으며, 글이 많이 정돈된 형태가 아닙니다. 이 글의 목적은 지극히 저의 공부에 있으며, 누구를 이해시키기 위해 작성하는 글이 아니므로, 참고하시면 좋을 것 같습니다. 혹시 이 글을 읽고 있는 독자 분들이 만약 이 글들에서 오류를 발견한다면, 댓글을 남겨주세요. 글에 반영하도록 하겠습니다. Q. DARPA Internet Protocol이 뭐야? GPT Says:DARPA Internet Protocol(DARPA IP)는 인터넷의 기본 프로토콜인 TCP/IP(Transmission Control Prot.. [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 ··· 6 7 8 9 10 11 12 ··· 49 다음
