BOJ
-
[Python 3] BOJ - 9015 "정사각형"BOJ 2021. 12. 27. 21:05
# 문제 링크 https://www.acmicpc.net/problem/9015 9015번: 정사각형 각 테스트 케이스마다 가장 큰 정사각형의 넓이를 한 줄에 하나씩 출력한다. 단, 정사각형이 없는 경우 0을 출력한다. www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 정사각형의 성질을 이해하는 것이라 생각한다. 정사각형은 모든 변의 길이가 같으며 각각의 내각이 90도로 모두 같은 사각형을 의미한다. 따라서, 시간복잡도를 고려하지 않고 정사각형을 판별하려면 단순히 4점을 뽑으면 된다. 3점을 뽑아도 역시 정사각형을 판별할 수 있다. 그러나 3점으로는 절대로 시간안에 정답을 구할 수 없다. N 제한이 3000이기 때문에 최대 $O(N^2)$의 시간 복잡도가 허용된다. 즉, 2점을 뽑고 남은..
-
[Python 3] BOJ - 10564 "팔굽혀펴기"BOJ 2021. 12. 26. 21:36
# 문제 링크 https://www.acmicpc.net/problem/10564 10564번: 팔굽혀펴기 각각의 테스트 케이스에 대해서, 동혁이가 응원하는 팀이 득점한 점수의 최댓값을 출력한다. 만약, 불가능한 경우에는 -1을 출력한다. www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다. 상태 공간을 현재까지 한 팔굽혀펴기 횟수를 cnt, 현재 득점한 순간이 끝에서 부터 몇번째 순간인지를 turn이라고 할 때 얻을 수 있는 최대 점수인 dp[cnt][turn]이라고 정의하자. 위 그림 1은 팔굽혀펴기 갯수를 만족시키기 위해 필요한 전체 차례가 k인 경우를 나타낸 그림이다. i번째 턴에 해당하는 점수는 $a_i$이다. 이 때 전체 팔굽혀펴기의 횟수는 $k..
-
[Python 3] BOJ - 2132 "나무 위의 벌레"BOJ 2021. 12. 16. 22:33
# 문제 링크 https://www.acmicpc.net/problem/2132 2132번: 나무 위의 벌레 첫째 줄에는 트리의 정점의 개수를 나타내는 정수 n(1 ≤ n ≤ 10,000)이 주어진다. 다음 줄에는 차례로 1번, 2번, …, n번 정점에 매달려 있는 열매의 개수가 주어진다. 다음 n-1개의 줄에는 트리의 각 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 특정 알고리즘이라기 보다는 문제에 대한 관찰이라고 생각한다. 위 그림 1은 문제에서 제시된 입력을 나타낸 그림이다. 예제 입력 1에서 5개의 구슬을 떨어뜨리면 각각의 순서는 2,4,2,5,2가 된다. 이 때, 떨어지는 순서를 무시하고 각 서브트리(자기 자신도 포함)가 가지고 있는 구슬의 갯수를 세어보자. 그렇게 하면 위..
-
[Python 3] BOJ - 2305 "자리 배치"BOJ 2021. 12. 14. 16:58
# 문제 링크 https://www.acmicpc.net/problem/2305 2305번: 자리 배치 어떤 극장의 자리는 한 줄로 배치되어 있고 자리번호는 왼쪽부터 1에서 N까지 차례대로 매겨져 있다. 이 N개의 자리 중에서 N-1개의 자리는 지정석으로 모두 판매하고, 어떤 한 자리만 자유석으로 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다. 위 그림 1은 N이 4이고 자유석이 없는 경우를 나타낸 그림이다. 위 그림에서 물음표는 아직 주인이 정해지지 않은 자리이다. 따라서, 현재 그림 1은 3번 사람이 앉을 때 가능한 상황을 나타낸다고 할 수 있다. 왼쪽 위 그림의 경우는 1번 사람은 제자리에, 2번 사람 역시 제자리에 앉아 있는 경우이다. 이 때 ..
-
[Python 3] BOJ - 13711 "LCS 4"BOJ 2021. 12. 8. 20:41
# 문제 링크 https://www.acmicpc.net/problem/13711 13711번: LCS 4 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, [1, 2, 3]과 [1, 3, 2]의 LCS는 [1, 2] 또는 [1, 3] www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 가장 긴 증가하는 수열(LIS)라고 생각한다. 위 그림 1은 입력으로 주어지는 배열 A와 B, 그 때의 정답배열인 C 그리고 각각의 C배열의 원소들이 A와 B에서의 인덱스를 기호화한 그림이다. 문제의 조건에 따라, 정답배열인 C는 반드시 1부터 N까지의 수 중 하나이어야 ..
-
[Python 3] BOJ - 13308 "주유소"BOJ 2021. 12. 4. 20:52
# 문제 링크 https://www.acmicpc.net/problem/13308 13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 다익스트라 알고리즘이라고 생각한다. 다만, 일반적인 다익스트라와는 다르게 상태 공간을 현재 정점의 번호가 idx, 현재 기름을 넣기 위해 드는 단위 비용을 cost일 때 드는 최소 비용인 2차원 상태 공간 d[idx][cost]라고 정의하자. 위 그림 1은 임의의 그래프 중 일부 정점과 간선을 나타낸 그림이다. 우선 i번..
-
[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차적으로는 비지 않은 호수 중 하나를 마실 수 있다. 그런데, 그런 호수들 중에서 앞으로 비가 가장 먼저 올 호수를 비우는 것이 이득임은 자명하다. 따라서, 현재 호수를 마실 수 있다면, 비어 있는 호수들을 확인해야 한다 그런데 문제에서 호수의 갯수가 백만개, 날씨..