효과는 굉장했다!

17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 알고리즘 분류 구현 그래프 이론 브루트포스 알고리즘 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 최소 스패닝 트리 SOLUTION import sys from collections import deque # bfs를 통해 각 대륙 고유 라벨링 def bfs(i, j): global continent_num queue = deque([[i,j]]) island[i][j] = continent_num while queue: x, y = queue..

1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 알고리즘 분류 그래프 이론 최소 스패닝 트리 SOLUTION import sys # 크루스칼 알고리즘 사용하여 최소 가중치를 구한다 def find(parent, x): if parent[x] != x: parent[x] = find(parent, parent[x]) return parent[x] def union(parent, A, B): root_A = find(parent, A) root_B = find(par..

5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 트리 재귀 SOLUTION import sys sys.setrecursionlimit(10**6) def postorder(start, end): if start > end : # 더 이상 탐색할 노드 존재 X return root = preorder_list[start] # 시작 노드 idx = start + 1 for i in range(idx, end+1): # 서브 노드가 뿌리 노드보다 크다면 인덱스 재..

2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 알고리즘 분류 트리 분할 정복 재귀 SOLUTION import sys sys.setrecursionlimit(10**6) def preorder(inorder_start, inorder_end, postorder_start, postorder_end): if inorder_start > inorder_end or postorder_start > postorder_end: return # 루트 root = postorder[postorder_end] # 전위 순회 : 루트 -> 왼쪽 ->..

1806번: 부분합 첫째 줄에 N (10 ≤ N = S: length = min(length, right - left) tmp -=..

3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 알고리즘 분류 정렬 두 포인터 SOLUTION import numbers import sys n = int(sys.stdin.readline()) nums = sorted(list(map(int, sys.stdin.readline().split()))) x = int(sys.stdin.readline()) # 양 끝에 탐색 시작 포인트를 둔다 start, end = 0, n-1 cnt = 0 while st..

1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 알고리즘 분류 그래프 이론 다익스트라 SOLUTION import sys import heapq INF = sys.maxsize # 다익스트라 알고리즘 def dijkstar(start): heap = [] distance[start] = 0 # 시작점의 가중치는 0 heapq.heappush(heap, (0, start)) while heap: cost, now = heapq.heappop(heap) # 최소비용으로 가는 것이..

1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 알고리즘 분류 그래프 이론 다익스트라 SOLUTION import sys import heapq INF = sys.maxsize def dijkstra(start): heap = [] distance[start] = 0 # heap에 (가중치, 노드) 순으로 넣어놔야 시간을 더 줄일 수 있다 heapq.heappush(heap, (0, start)) while heap: cost, now = heapq.heappop(heap..

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 SOLUTION import sys from collections import deque def bfs(): while queue: y, x = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 SOLUTION import sys from collections import deque def dfs(graph, start_node): queue = deque([start_node]) visit = [] while queue: node = queue.pop() # 가장 깊숙이 있는 노드부터 탐색해야 하므로 if node not in visit: # ..