BOJ
-
[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을 기준으로 상위에 있는 봉우리를 각기 다른 색깔로 칠해놓았다. 현재 봉우리 중 문제에서 어떤 봉우리에도 속하지 않은, 다시 말해 가장 바깥에 있는 봉우리는 파란색 봉우리와..
-
[Python 3] BOJ - 13398 "연속합 2"BOJ 2021. 9. 3. 00:52
# 문제 링크 https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다. 우선 수를 하나도 빼지 않고 연속한 수들을 더해 최대값을 구하는 것부터 구해보자. 위 그림 1은 현재 3을 선택하는 경우를 나타낸다. 문제에서 연속해야한다고 했기 때문에 이전의 -10을 유지한채 3을 더해야 한다. 그런데 이전의 연속합을 무시하고 지금부터 다시 연속합을 만드는 경우도 있다. 따라서, select의 ..
-
[Python 3] BOJ - 17619 "개구리 점프"BOJ 2021. 9. 1. 14:25
# 문제 링크 https://www.acmicpc.net/problem/17619 17619번: 개구리 점프 첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 정렬과 유니온 파인드라고 생각한다. 위 그림 1에서는 임의의 5개의 선분이 나타나 있다. 현재 a 선분과 d 선분은 겹쳐져 있지 않지만 점프를 통해서 갈 수 있다. 왜냐하면 a에서 b로, b에서 d로 가면 도착할 수 있기 때문이다. c와 d 역시 마찬가지이다. 그러나, e는 자기자신을 제외한 어느 선분도..