문제링크:https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 다루는 주제: 그래프 탐색 # 이진트리를 전위탐색할시에 부모 노드값은 배열 [0] 이고 부모노드값보다 커지는 숫자가 나올때까지 왼쪽 서브트리 그 이후엔 오른쪽 서브 트리다. # 전위 탐색은 부모노드 -> 왼쪽 자식 -> 오른쪽 자식 후위 탐색은 왼쪽 -> 오른쪽 -> 부모노드 순이다. import sys sys.setrecursionlimit(10 ** 9) input = s..
문제링크:https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 다루는 주제: 그래프 탐색 import sys N, M = map(int, sys.stdin.readline().split()) matrix = [[0] * (N + 1) for _ in range(N + 1)] visit = [False] * (N + 1) count = 0 for _ in range(M): u, v = ma..
문제링크:https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 다루는 주제: 그래프 탐색 import sys # N은 정점의 개수 M은 간선의 개수, V는 탐색을 시작할 정점의 번호 N, M, V = map(int, sys.stdin.readline().split()) matrix = [[0] * (N + 1) for _ in range(N + 1)] # 인접영 행렬 visit = [0] * (N + 1) # 방..
문제링크:https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 다루는 주제: 그래프 탐색 import sys def find(parent, x): # 부모노드 비교 if parent[x] != x: parent[x] = find(parent, parent[x]) return parent[x] def union(parent, a, b): # 합치면서 부모노드가 더 작은쪽으로 부모를 바꿔 a = find(p..
문제링크:https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 다루는 주제: 그래프탐색 import sys N = int(sys.stdin.readline()) tree = {} for _ in range(N): root, left, right = sys.stdin.readline().strip().split() tree[root] = [left, right] def preorder(root): if root != ".": print(ro..
문제풀이: https://www.acmicpc.net/problem/5904 5904번: Moo 게임 Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o www.acmicpc.net 다루는 주제: 분할정복 # n 에서 전차수를 뺄때 1이면 n return은 m이다 나머진 전부 o # 새로운 차수 = S(k-1) + oxk+m + S(k-1) 새로운차수 길이 = 전차수 + 3 + 전차수 # n이 l보다 크고 다음 차수로 가는 필요길이보다 작을때만 # +++ l다음 글자는 무조건 m이다 import sys def moo(n, k, l..
문제링크:https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 다루는 주제: 이분 탐색 import sys def binary(arr, start, end): result = 0 while start middle: # 나무길이가 중간값보다 크면 total += tree - middle # 나무길이 - 중간값 즉 가져갈 나무길이를 total에 저장 if total < M: # 가져갈 나무길이의 총합이 M에 미치지..
문제링크:https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 다루는 주제: 스택 import sys # 탑의 수 N = int(sys.stdin.readline()) # 탑의 높이 tops = [0] + list(map(int, sys.stdin.readline().split())) result = [0] * (N + 1) stack = [] for i in range(1, N + 1): # Stack에 탑의 정보가 남아있다면 while stac..
