1874번: 스택수열 (구현, 스택) - Fastcampus
www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net import sys def run(N, a): res = [] i, st = 1, [] # 스택 for x in a: while x >= i: st.append(i) res.append("+") i += 1 if st[-1] == x: st.pop() res.append("-") else: return ["NO"] return r..
3-2. [그래프 탐색] Kruskal, Prim (최소신장트리)
크루스칼 빠른 간선 순서로 탐색한다 (결과값: 최소신장트리에 해당하는 간선 리스트) 단, 사이클을 만들지 않아야 한다 간선의 두 정점이 서로 다른 분리집합에 있어야 한다 graph = { "vertices": ["A", "B", "C", "D"], "edges": [ (6, "A", "B"), (3, "A", "C"), (2, "B", "C"), (1, "B", "D"), (9, "C", "D"), ], } def find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x] def union(x, y): rx = find(x) ry = find(y) if rx != ry: parent[ry] = rx def kruskal(): # 1...
3-1. [그래프 탐색] BFS (전체탐색) Dijkstra (최단거리)
BFS 인접 정점 순서로 탐색한다 (결과값: 모든 정점) 구현방법: 인접 정점을 큐에 추가... 반복 자료구조: 큐와 visited 테이블 문제유형 모든 정점 탐색 => 탐색된 모든 정점의 개수 , 정점의 리스트 특정 정점 탐색 => 특정 정점에 도달하는 가장 빠른 탐색횟수, 가장 빠른 탐색경로 # [방법 1] 큐에서 꺼내고 방문처리 from collections import deque graph = { "A": ["B", "C"], "B": ["A", "C", "D"], "C": ["A", "B", "D"], "D": ["B", "C"], } S = 'A' qu = deque([S]) visited = [] while qu: node = qu.popleft() if node not in visited:..
2-1. [정렬], [이분탐색]
1. 선택정렬 (최소값을 찾아서 하나씩 넣는다) def find_min_idx(a): min_i = 0 for i in range(1, len(a)): if a[i] < a[min_i]: min_i = i return min_i # 선택정렬: 최소값을 찾아서 하나씩 넣는다... O(N^2) def sel_sort(a): rst = [] while a: i = find_min_idx(a) v = a.pop(i) rst.append(v) return rst d = [2, 4, 5, 1, 3] print(sel_sort(d)) a = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] N = len(a) for i in range(N - 1): min_i = i for j in range(i + 1, N)..