1-4. [구현] 자주 사용하는 라이브러리
0. 방향 벡터 # direction: 서, 남, 동, 북 dx = [0, 1, 0, -1] dy = [-1, 0, 1, 0] steps = [(0, -1), (1, 0), (0, 1), (-1, 0)] steps = {'W': (0, -1), 'S': (1, 0), 'E': (0, 1), 'N': (-1, 0)} 1. itertools: 조합, 순열, 중복순열 import itertools result = list(itertools.combinations([1, 2, 3], 2)) print(result) # [(1, 2), (1, 3), (2, 3)] result = list(itertools.permutations([1, 2, 3], 2)) print(result) # [(1, 2), (1, 3),..
3-3. [그래프 탐색] 백트래킹
1. N Queen 문제 def check(a, row, col): for r, c in enumerate(a): if col == c or abs(col - c) == abs(row - r): return False return True def recursive(row, a): global result if row == 4: result.append(a[:]) return for col in [0, 1, 2, 3]: if check(a, row, col): # 가지치기 (이전 퀀의 위치에 따라 탐색 제외) a.append(col) recursive(row + 1, a) a.pop() result = [] recursive(0, []) print(result) # [[1, 3, 0, 2], [2, 0, ..
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)..
1-3. [구현] 수학
1. 진수변환 (2진수 문자열 => 10진수 => 2진수 문자열) # 2진수 문자열을 10진수로 바꾸기 def b2d(num): a = list(map(int, num.replace('0b', ''))) # [1, 1, 0, 1] result = 0 for x in a: result = result * 2 + x return result print(int('0b1101', 2), b2d('0b1101')) # 2진수 '1101' => 10진수 13 # 10진수를 2진수 문자열로 바꾸기 def d2b(num): a = [] while num: a.append(num % 2) num //= 2 a.reverse() # [1, 1, 0, 1] return '0b' + ''.join(map(str, a)) pr..
1-2. [구현] 재귀
재귀함수의 매개변수 선언순서에 규칙을 주자 => 입력, 출력, 내부변수 1. 팩토리얼 # 재귀... O(N) def fact(n): if n == 1: return 1 return n * fact(n - 1) print(fact(3)) 2. 최대공약수 # 재귀... O(logN) def gcd(a, b): if b == 0: return a return gcd(b, a % b) print(gcd(9, 6)) 3. 하노이탑 # 재귀... O(2^N) def hanoi(n, from_p, to_p, aux_p): if n == 1: print(f"{from_p} -> {to_p}") return hanoi(n - 1, from_p, aux_p, to_p) print(f"{from_p} -> {to_p}") ..
