분류 전체보기
-
[Python 3] BOJ - 17182 "우주 탐사선"BOJ 2021. 11. 30. 20:59
# 문제 링크 https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 비트마스킹을 이용한 다이나믹 프로그래밍과 플로이드 와샬이라고 생각한다. 상태 공간을 현재 방문한 정점들의 비트인 bit, 현재 위치해있는 정점을 now라고 할 때 드는 최소비용인 dp[bit][now]라고 정의하자. 현재 문제에서 N의 제한이 10으로 매우 작기 때문에 상태 공간에 필요한 공간 복잡도는 $2^{10} * 10$이므로 매우 작..
-
[Python 3] BOJ - 3430 "용이 산다"BOJ 2021. 11. 29. 19:41
# 문제 링크 https://www.acmicpc.net/problem/3430 3430번: 용이 산다 옛날 아주 먼 옛날, 한 마을에 용이 살고 있었습니다. 그 마을에는 호수가 여러개 있었는데, 그 호수들은 모두 물이 들어 있었습니다. 이 마을에는 가끔 비가 내립니다. 신기하게도 비는 한 호수 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 그리디 알고리즘과 우선순위 큐라고 생각한다. 현재 호수를 마실 수 있는 차례라면, 1차적으로는 비지 않은 호수 중 하나를 마실 수 있다. 그런데, 그런 호수들 중에서 앞으로 비가 가장 먼저 올 호수를 비우는 것이 이득임은 자명하다. 따라서, 현재 호수를 마실 수 있다면, 비어 있는 호수들을 확인해야 한다 그런데 문제에서 호수의 갯수가 백만개, 날씨..
-
[Python 3] BOJ - 16565 "N포커"BOJ 2021. 11. 21. 19:34
# 문제 링크 https://www.acmicpc.net/problem/16565 16565번: N포커 첫째 줄에 N장의 카드를 뽑았을 때, 플레이어가 이기는 경우의 수를 10,007로 나눈 나머지를 출력하라. www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다. 승리하는 조건은 포카드가 최소 한번 이상 일어나는 것이다. 예를 들어, 현재 뽑아야 하는 카드 갯수가 9개라면, 포카드가 1번 일어나는 경우 혹은 포카드가 2번 일어나는 경우 모두 승리하는 것이다. 따라서 남은 카드는 절대로 포카드가 되어서는 안된다. 따라서 상태 공간을 현재까지 뽑은 카드수가 cnt, 현재까지 뽑은 카드의 종류(번호 기준)가 kind라고 할 때 포카드가 되지 않는 경우의 수인 d..
-
[Python 3] BOJ - 2478 "자물쇠"BOJ 2021. 11. 17. 22:43
# 문제 링크 https://www.acmicpc.net/problem/2478 2478번: 자물쇠 처음 k-왼쪽밀기의 k를 첫째 줄에, (p,q)-구간뒤집기의 p와 q를 빈칸을 사이에 두고 둘째 줄에, 그리고 마지막 k-왼쪽밀기의 k를 셋째 줄에 출력한다. 만일 답이 여럿일 경우에는 그 중 하나만 출력 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 그리디 알고리즘이라고 생각한다. 위의 그림 1은 n이 4일때 가능한 구간 뒤집기의 결과 중 일부이다. 문제에서 제시한 순서에 따라 자물쇠를 만들어야 하므로 한 번 왼쪽밀기를 했을 때, 인접한 두 수의 차이는 1 혹은 n - 1이 됨을 알 수 있다. 따라서, 위와 같이 연속하거나, 차이가 n - 1이 되는 수열만이 가능하다는 것은 자명하다...
-
[Python 3] BOJ - 20530 "양분"BOJ 2021. 11. 14. 21:18
# 문제 링크 https://www.acmicpc.net/problem/20530 20530번: 양분 첫째 줄에 두 자연수 $N$, $Q$가 주어진다. 주어지는 그래프의 정점과 간선의 개수가 $N$개이며 쿼리가 $Q$개 주어진다는 것을 의미한다. 둘째 줄부터 $N$개의 줄에는 $i$번 간선이 연결하는 두 정점 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 사이클 검출이라고 생각한다. 위 그림 1은 예제 입력 1의 경우를 나타낸 것이다. 이 때, 점선을 빼고 생각하면 이 그래프는 트리임이 자명하다. 트리의 성질로 인해 정점 수가 N개라면, 간선 수는 N-1개이다. 또한 문제에서 제시하는 두 조건, 중복 간선과 루프 간선이 없음을 트리는 만족한다. 그런데 문제에서는 입력으로 주어지는 그래..
-
[Python 3] BOJ - 16161 "가장 긴 증가하는 팰린드롬 부분수열"BOJ 2021. 11. 12. 13:49
# 문제 링크 https://www.acmicpc.net/problem/16161 16161번: 가장 긴 증가하는 팰린드롬 부분수열 팰린드롬 수열이란 앞에서부터 읽을 때와 뒤에서부터 읽을 때 똑같은 수열을 말한다. 수열 {13, 25, 3, 25, 13}, {9, 5, 5, 9}는 팰린드롬이고, {1, 2, 3, 4, 5, 6, 7, 6}, {1, 2, 5, 4, 2}, {1, 1, 3, 2, 4}는 팰린드 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 투 포인터라고 생각한다. 위 그림 1은 문제에서 정의하는 증가하는 팰린드롬 수열의 예시인 [1,3,5,3,1]을 나타낸 그림이다. 그런데 위에서부터 2번째 그림인 [3,5,3]은 첫번째 수열의 부분수열임을 알 수 있고 [3,5,3] 역..
-
[Python 3] BOJ - 20191 "줄임말"BOJ 2021. 11. 6. 16:59
# 문제 링크 https://www.acmicpc.net/problem/20191 20191번: 줄임말 문자열 A가 문자열 B의 줄임말이라는 것은 B의 순서를 바꾸지 않고 0 또는 그 이상 개수의 문자를 지워 A를 만들 수 있다는 뜻이다. 정의에 의해서 B는 자기 자신의 줄임말임에 유의하라. 예를 들 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 그리디 알고리즘과 이분 탐색이라고 생각한다. 위 그림 1은 t가 "aacba"인 경우를 나타낸 그림이다. 이 때 만일 s의 첫글자가 c인 경우를 생각해보자. 그렇다면, 두번째 글자는 a,b,c 중 하나일 것이다. 그런데 a와 b의 경우는 굳이 n을 증가시키지 않아도 얻을 수 있으나, c의 경우는 n을 증가시켜야만 얻을 수 있다. 따라서 현재 ..
-
[Python 3] BOJ - 13392 "방법을 출력하지 않는 숫자 맞추기"BOJ 2021. 11. 4. 20:10
# 문제 링크 https://www.acmicpc.net/problem/13392 13392번: 방법을 출력하지 않는 숫자 맞추기 아래 그림과 같이 N개의 회전이 가능한 숫자 나사가 아래위로 연결되어 있다. 가장 위에 있는 숫자나사는 숫자나사 1이고 가장 아래에 있는 숫자나사는 숫자나사 N이다. 모든 숫자나사는 각각 10 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다. 상태 공간을 현재 idx번째 인덱스이고 위에서 부터 왼쪽으로 left번만큼 돌렸을 때 목표 숫자를 맞추기 위한 최소 움직임인 dp[idx][left]라고 정의하자. 자칫 상태 공간이 메모리 초과에 걸릴만큼 크다고 생각할 수 있으나, 위칸에서 왼쪽으로 얼마나 많이 돌릴지라도 10칸을 돌린..