분류 전체보기
-
[Python 3] BOJ - 2233 "사과나무"BOJ 2021. 10. 9. 20:56
# 문제 링크 https://www.acmicpc.net/problem/2233 2233번: 사과나무 첫째 줄에 정점의 개수 N(1≤N≤2,000)이 주어진다. 둘째 줄에는 벌레가 만드는 2×N자리의 이진수가 주어진다. 셋째 줄에는 썩은 사과의 위치를 나타내는 두 정수 X, Y가 주어진다. 이는 2×N자리의 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 스택과 LCA라고 생각한다. 크게 보면 문제는 트리를 만들고 썩은 두 사과의 LCA를 파악하는 두 단계로 나누어져있다. 위 그림 1은 스택을 이용하여 트리를 구현하는 그림이다. 문제에서 제시한 바에 따라 0이라면 현재 가리키는 노드가 처음 진입하는 의미이기 때문에 그대로 스택에 추가한다. 위 그림 2는 리프 노드인 C까지 진행된 과정을..
-
[Python 3] BOJ - 6988 "타일 밟기"BOJ 2021. 9. 30. 21:38
# 문제 링크 https://www.acmicpc.net/problem/6988 6988번: 타일 밟기 첫째 줄에는 타일의 개수 N이 주어진다. N은 3 이상 3,000 이하이다. 둘째 줄에는 N개의 타일에 적힌 자연수들이 증가하는 순서로 빈칸을 사이에 두고 주어진다. 타일에 적힌 자연수들은 각각 1,000,0 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라 생각한다. 상태 공간을 dp[i][j], 현재 i번째 인덱스에서 j번째 인덱스로 타일을 밟을 때 얻을 수 있는 점수의 최대라고 정의한다. 위 그림 1에서 빨간색으로 칠한 두 숫자를 보자. 두 숫자의 차이는 2이며 그 다음에 밟을 타일의 숫자가 5로 정해지게 된다. 위 배열에서 5는 존재하기 때문에 현재 0에서..
-
[Python 3] BOJ - 2250 "트리의 높이와 너비"BOJ 2021. 9. 13. 23:00
# 문제 링크 https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 중위 순회라고 생각한다. 왜냐하면 가장 왼쪽 노드가 1번, 가장 오른쪽 노드가 n번이 됨이 문제의 조건에 의해 보장되기 때문이다. 따라서, 중위 순회를 하되 현재 노드의 위치와 깊이를 추적해가면서 정답을 구하면 된다. 다만 주의할 점은 루트 번호가 1이 아니라는 점이다. # 코드 import sys # dfs : 현재 노드 번호..
-
[Python 3] BOJ - 2169 "로봇 조종하기"BOJ 2021. 9. 9. 13:07
# 문제 링크 https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다. 이 때 상태공간은 현재 (i, j)에 있고 이전 방향이 k일 때 얻을 수 있는 가치의 최대값으로 정의한다. 문제에서 가장 중요한 조건은 한 번 방문한 곳은 재방문하지 않는 경우인데, 갈 수 있는 방향이 오른쪽, 아래, 왼쪽이기 때문에 이전에 오른쪽에서 왔다면 다음에 왼쪽으로 가는 경우는 재방문하는 경우..
-
[Python 3] BOJ - 2629 "양팔저울"BOJ 2021. 9. 8. 12:34
# 문제 링크 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 배낭 문제라고 생각한다. 문제에서 가능한 추의 무게는 500g이고 갯수는 30개이므로 가능한 추의 합의 최대값은 15000이다. 따라서 배낭문제를 위해 15000 * 30만큼의 메모리가 필요하고 이는 충분하다. 마찬가지로 450,000번의 연산은 충분히 시간안에 할 수 있다. 따라서 상태공간을 현재 i번째 추를 기준으로 무게 j가 가능한지 여부(T..
-
[Python 3] BOJ - 1300 "K번째 수"BOJ 2021. 9. 7. 22:32
# 문제 링크 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net # 풀이 개인적으로 이 문제는 이분 탐색이 핵심이라고 생각한다. 만일 어떤 수 X보다 작거나 같은 수가 K개 이상이라고 한다면, 그 때 X는 K번째 수의 후보임에는 자명하고 반대 경우, 즉 X 이하의 수가 K개 미만이면 그 때 X는 K번째 후보가 될 수 없다는 것이 자명하다. 따라서, 어떤 수 X 이하의 수가 K 이상인 X 중 가장 작은 수가 정답이 됨..
-
[Python 3] BOJ - 1256 "사전"BOJ 2021. 9. 6. 17:03
# 문제 링크 https://www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 조합론이라고 생각한다. 문제를 분석하게 되면 결국에 몇번째 문자이건 시작은 A또는 Z임에는 자명하다. cnt[i]를 현재 길이가 i일 때 가능한 모든 문자열의 갯수라고 정의하자. 그렇다면 현재 그림 1의 가장 왼쪽은 수평선을 기준으로 위쪽 부분은 A로 시작하며, 아래쪽 부분은 Z로 시작함을 알 수 있다. 그런데, 어느 쪽이든 시작하는 부분을 선택하고 그 다음 경우에 가능한 모든 문자열의 갯수는..
-
[Python 3] BOJ - 14865 "곡선 자르기"BOJ 2021. 9. 3. 14:46
# 문제 링크 https://www.acmicpc.net/problem/14865 14865번: 곡선 자르기 컴퓨터 그래픽 캔버스는 컴퓨터 화면에서 그림을 그릴 수 있는 직사각형 영역을 말한다. 캔버스는 2차원 좌표 평면처럼 각 점의 위치를 좌표로 표시한다. 캔버스의 정중앙 점이 원점 (0,0)이고, www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 괄호 문자열이라고 생각한다. 자칫보면 기하학 문제처럼 보일 수 있으나, 문제 구조를 자세히 관찰하면 사실상 스택문제임을 알 수 있다 위 그림 1에서는 빨간선, 즉 y = 0을 기준으로 상위에 있는 봉우리를 각기 다른 색깔로 칠해놓았다. 현재 봉우리 중 문제에서 어떤 봉우리에도 속하지 않은, 다시 말해 가장 바깥에 있는 봉우리는 파란색 봉우리와..