본문 바로가기

알고리즘

 (371)
[Python] 25280번 Marathon https://www.acmicpc.net/problem/25280 25280번: Marathon Erik wants to run a marathon. Most of all, he wants to win the race. To plan his training, he has looked up how the other contestants performed in previous races and made a model to predict his chances of winning. The finishing time for each contestant is www.acmicpc.net 23/08/05 확률론적인 부분만 해결하면 쉽게 풀 수 있는 이분탐색 문제이다. 문제 접근 방식: 문제는 그렇게 길지 않으니 바..
[Python] 24838번 배열 구간합 놀이 https://www.acmicpc.net/problem/24838 24838번: 배열 구간합 놀이 각 테스트 케이스의 정답인 Alice가 달성할 수 있는 $S(A, x, y)$의 최댓값, 그리고 이를 달성할 수 있는 방법의 수를 공백으로 구분하여 출력한다. 단, 방법의 수가 매우 커질 수 있으므로 $10^9+7$로 www.acmicpc.net 23/08/04 내가 있는 스터디 그룹에서 이번 주 주간 문제로 다룬 문제 중 하나로, 구간 합을 적절히 이용한 재미있는 문제이다. 단점이라고 하면, 지문이 너무 길다는 것... 이 글에서는 지문을 전부 이해하고 있다는 가정 하에서 글을 쓸 것이다. 문제 접근 방식: 문제에서 주어진 예제를 잘 이해해 보자. 예제에서는 결론적으로, $1000$을 $2$번 더하고, ..
[Python] 24187번 Korta vokaler https://www.acmicpc.net/problem/24187 24187번: Korta vokaler Att lösa algoritmproblem är svårt, men en sak som ofta är ännu svårare är att förbereda testdatan. Ta problemet Arabiska till exempel. Här har juryn lagt många timmars intensivt arbete åt att konstruera mästerverk som hej vad heter du. En fråg www.acmicpc.net 23/07/03 언어 장벽이 있는 스웨덴어 문제로, 다른 사람들의 풀이와는 다르게 푼 듯 하여 올려본다. 문제 접근 방식: 먼저, 문제를 요..
[Python] 24230번 트리 색칠하기 https://www.acmicpc.net/problem/24230 24230번: 트리 색칠하기 정점이 $N$개인 트리가 있다. 정점에는 1부터 $N$까지 번호가 붙어있다. 트리의 루트는 항상 1번 정점이며 맨 처음에는 모든 정점이 하얀색으로 칠해져 있는 상태이다. 하나의 정점에 색칠하면 해 www.acmicpc.net 23/05/29 골드 5 짜리 문제 치고는 아이디어가 매우 좋았던 문제이다. 문제 접근 방식: 문제 정보를 보면, 트리가 주어져 있는데 각 노드별로 색깔 정보가 주어진다고 했다. 한 노드를 색칠하면, 그 노드를 포함한 서브트리는 모두 같은 색으로 색칠된다고 한다. 이때, 모든 정점을 원하는 색으로 칠하고자 할 때 구하는 최소 색칠 횟수를 구하는 것이 우리의 목적이다. 맨 처음 떠올렸던 방..
[Python] 15703번 주사위 쌓기 https://www.acmicpc.net/problem/15703 15703번: 주사위 쌓기 아래 설명에서 k개의 주사위가 쌓여져 있고, 위에서부터 적혀있는 정수가 s1, s2, ..., sk인 주사위 탑을 (s1, s2, ..., sk)로 표현했다. 예제 1의 경우에는 주사위 탑 1개를 만들 수 있다. (1, 2, 4, 5) 또는 ( www.acmicpc.net 23/05/25 구현을 조금 요하는 그리디 문제이다. 문제 접근 방식: 문제 요약을 하면 다음과 같다. 주사위가 주어져 있고, 하나의 주사위의 모든 면에는 같은 눈금이 적혀있다. 이런 주사위들을 모아 주사위 탑을 쌓고자 하는데, 한 주사위에 적힌 눈금이 $5$라면, 그 주사위 위에는 $5$개를 넘어서 주사위를 쌓을 수 없다고 한다. 이럴 때,..
[Python] 8845번 Gra https://www.acmicpc.net/problem/8845 8845번: Gra Dla każdej konfiguracji początkowej w osobnej linii wypisz "W", jeśli Hektor wygra grę przy danym ustawieniu, "P" w przeciwnym przypadku. www.acmicpc.net 23/05/31 스프라그-그런디 정리가 적용되는 게임은 DAG(Directed Acyclic Graph)로 모델링 될 수 있다는 사실을 알고 있다면 쉽게 풀 수 있는 문제이다. 비슷한 문제들로 다음과 같은 문제들을 추천하니, 풀어본다면 좋은 연습이 될 것이다. https://www.acmicpc.net/problem/10363 10363번: Circ..
[Python] 16887번 루트 님 게임 https://www.acmicpc.net/problem/16887 16887번: 루트 님 게임 첫째 줄에 돌 더미의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 둘째 줄에 돌 더미에 포함된 돌의 개수 Ai(1 ≤ Ai ≤ 1,000,000,000,000)가 주어진다. www.acmicpc.net 23/04/06 스프라그-그런디 문제로, 사실 스프라그-그런디 정리를 곁들인 수학 문제라고 봐도 무방한 문제다. 그런디 수를 구하는 경계가 조금 구하기 귀찮기 때문에 난도가 높은 것이라고 생각한다. 하지만 개인적으로 플레티넘 1을 받을 정도의 난이도는 아니라고 생각하는 문제다. 문제 접근 방식: 문제에서 주어진 것 처럼 그대로 구현하면 당연히 시간 초과가 날 것이다. 이는 직접 해보면 잘 알 것이다.. ..
[Python] 19114번 Master Zhu and Candies (증명 추가 필요) https://www.acmicpc.net/problem/19114 19114번: Master Zhu and Candies Master Zhu puts $n$ heaps of candies on the table. Two players are playing the following game: on their turn, each player can either pick any positive number of candies from the same heap, or split some heap into three smaller non-empty heaps. Player who p www.acmicpc.net 23/05/03 전형적인 스프라그-그런디 정리 문제로, 문제에서 주어지는 그대로 착실하게 구현하면 된..

티스토리툴바