취약 개념 보충
중간중간 소홀했지만 그래도 조금씩이나마 무언갈 하고 있었습니다.
프로그래밍 경시대회나 여타 문제들을 풀면서 일부 개념을 문제에 적용하지 못하는 경우가 있어 그 경우를 정리하고자 합니다.
Hash
해쉬(Hash)는 임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것을 말합니다. 특정한 배열의 인덱스나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있습니다. 해쉬의 경우 대부분의 연산에서 시간복잡도 O(1)을 가집니다. 따라서 데이터를 삽입, 삭제, 검색하는 일이 많은 경우 이를 사용해야 합니다.
파이썬에서는 Dictionary를 통해 해쉬를 사용할 수 있습니다.
# 빈 딕셔너리
dict1 = {}
dict2 = dict()
# 데이터가 들어있는 딕셔너리
User = {
'ID' : 'Mukho'
'Line' : 'Support'
}
Users = {
'LOL' : {'ID' : 'Mukho', 'Line' : 'Support'},
'Kart' : {'ID' : '97lineMusic', 'Position' : 'Runner'}
}
# 삽입, 삭제, 수정, 검색
User['Top_Rating'] = 'D2'
del User['Top_Rating']
User['Line'] = 'AD Carry'
User.get('ID', 'no') # User 딕셔너리에서 Key가 'ID'인 Value를 가져와라. 단, 없을 경우 'no'를 반환한다.
# 출력
for key in dict:
print(key) # key값만 출력됨
print(dict[key]) # value값이 출력됨
for k in dict.keys():
print(k)
for v in dict.values():
print(v)
for k, v in dict.items():
print(k, v)
조합(Combinations), 순열(Permutations)
조합(combination)은 n개의 원소를 갖는 집합에서 r개의 원소를 선택하는 것으로, 순서는 중요하지 않습니다.
순열(permutation)은 n개의 원소에서 순서에 유의하여 r개를 나열하는 것입니다.
조합과 순열은 기본적으로 중복을 허용하지 않습니다만, 경우에 따라서 중복을 허용해야 하는 경우가 있습니다.
조합과 순열은 backtracking을 통해 만들 수 있으나, python에는 itertools라는 라이브러리가 있어 이를 이용해 편하게 만들 수 있습니다.
# 조합 및 중복조합
from itertools import combinations, combinations_with_replacement
lst = [1, 2, 3]
# 조합
print('---조합---')
for i in range(1, 4):
for combi in combinations(lst, i):
combi = list(combi)
print(combi)
# 중복조합(자기 자신의 중복을 허용. 단, 순서만 다른 case는 배제)
print('---중복조합---')
for i in range(1, 4):
for combi in combinations_with_replacement(lst, i):
combi = list(combi)
print(combi)
'''
---조합---
[1]
[2]
[3]
[1, 2]
[1, 3]
[2, 3]
[1, 2, 3]
---중복조합---
[1]
[2]
[3]
[1, 1]
[1, 2]
[1, 3]
[2, 2]
[2, 3]
[3, 3]
[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 2, 2]
[1, 2, 3]
[1, 3, 3]
[2, 2, 2]
[2, 2, 3]
[2, 3, 3]
[3, 3, 3]
'''
# 순열과 중복순열
from itertools import permutations, product
lst = [1, 2, 3]
# 순열
print('---순열---')
for i in range(1, 4):
for permu in permutations(lst, i):
permu = list(permu)
print(permu)
# 중복순열
print('---중복순열---')
for i in range(1, 4):
for prod in product(lst, repeat=i):
prod = list(prod)
print(prod)
'''
---순열---
[1]
[2]
[3]
[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
---중복순열---
[1]
[2]
[3]
[1, 1]
[1, 2]
[1, 3]
[2, 1]
[2, 2]
[2, 3]
[3, 1]
[3, 2]
[3, 3]
[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 2, 1]
[1, 2, 2]
[1, 2, 3]
[1, 3, 1]
[1, 3, 2]
[1, 3, 3]
[2, 1, 1]
[2, 1, 2]
[2, 1, 3]
[2, 2, 1]
[2, 2, 2]
[2, 2, 3]
[2, 3, 1]
[2, 3, 2]
[2, 3, 3]
[3, 1, 1]
[3, 1, 2]
[3, 1, 3]
[3, 2, 1]
[3, 2, 2]
[3, 2, 3]
[3, 3, 1]
[3, 3, 2]
[3, 3, 3]
'''
Backtracking
백트래킹은 모든 경우의 수를 전부 고려하는 알고리즘입니다. 트리 탐색 알고리즘의 일종이며 깊이 우선 탐색(DFS: Depth First Search), 너비 우선 탐색(BFS: Breadth First Search), 최선 우선 탐색(Best First Search/Heuristic Search) 등이 있습니다.
보통 모든 경우의 수를 고려해야 하는 문제라면 DFS가 낫지만, 최단거리 구하기 등 트리의 깊이가 무한대가 되는 경우에는 Queue를 이용한 BFS를 사용하는 것이 낫습니다.
DFS, BFS
DFS는 상태공간을 나하낸 트리에서 바닥에 도달할 때까지 한 쪽 방향으로만 내려가는 방식입니다. 재귀함수나 스택으로 구현할 수 있습니다.
BFS는 모든 분기점을 다 검사하면서 진행하는 방식입니다. BFS에서는 queue를 사용하여 구현하며, 각 경우를 검사하면서 발생하는 새로운 경우를 queue에 집어넣고, 검사한 경우는 queue에서 빼는 순으로 진행합니다.
얼마 전에 한 알고리즘 문제를 DFS와 BFS 두 방법으로 풀어보았습니다.
하단의 코드에서 sys.setrecursionlimit()은 파이썬의 재귀 깊이 default 값인 1000을 확장하기 위한 방법입니다.
'''
백준 2468번: 안전 영역(Silver I)
개념: 그래프 이론/탐색, 브루트포스, DFS, BFS
https://www.acmicpc.net/problem/2468
'''
import sys
from queue import Queue
sys.setrecursionlimit(10000)
# U, D, L, R
dx = [+0, +0, -1, +1]
dy = [-1, +1, +0, +0]
def in_range(x, y):
return 0 <= x and x < N and 0 <= y and y < N
def DFS(x, y, n):
# move
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if in_range(nx, ny) and visited[nx][ny] == 0 and local[nx][ny] > n:
# check
visited[nx][ny] = 1
DFS(nx, ny, n)
def BFS(x, y, n):
q = Queue()
q.put([x, y])
while not q.empty():
cx, cy = q.get()
# move
for i in range(4):
nx = cx + dx[i]
ny = cy + dy[i]
if in_range(nx, ny) and visited[nx][ny] == 0 and local[nx][ny] > n:
# check
visited[nx][ny] = 1
q.put([nx, ny])
answer = 1
N = int(input())
in_min = 101
in_max = 0
local = []
for _ in range(N):
in_row = list(map(int, input().split()))
local.append(in_row)
in_min = min(min(in_row), in_min)
in_max = max(max(in_row), in_max)
for n in range(in_min, in_max):
visited = [
[0 for _ in range(N)]
for _ in range(N)
]
cnt = 0
for i in range(N):
for j in range(N):
if local[i][j] > n and visited[i][j] == 0:
visited[i][j] = 1
cnt += 1
#DFS(i, j, n)
BFS(i, j, n)
answer = max(answer, cnt)
print(answer)
트리(Tree)
트리는 부모 노드 밑에 여러 자식 노드가 연결되고, 자식 노드 각각에 다시 자식 노드가 연결되는 재귀적 형태의 자료구조입니다. 맨 위에 있는 노드는 root node라고 합니다. 유닉스/윈도우의 디렉터리 구조가 트리의 일종이라고 할 수 있습니다.
이진 트리는 부모의 자식 노드 개수(차수=degree)가 최대 2개인 트리로, 가장 간단한 형태입니다. 이진 트리의 순회 방법은 전위 순회, 중위 순회, 후위 순회, 레벨 순서 순회가 있습니다. 레벨 순서 순회의 경우 노드를 레벨 순서로 방문하는 방법으로, 큐를 활용해 구현할 수 있습니다.
이때, root node 기준으로 left node에 작은 값, right node에 큰 값이 들어가는 tree를 이진 탐색 트리(Binary Search Tree)라고 합니다.
BST에서 값을 삭제하는 과정은 복잡합니다. 만약 삭제하는 노드의 자식 노드가 하나라면 그 자식 노드를 삭제한 노드 위치로 가져오면 됩니다. 하지만 자식 노드가 두개라면 오른쪽 자식 노드의 가장 왼쪽 아래에 있는 노드를 삭제한 노드 위치로 가져오면 됩니다.
# Binary Search Tree
from queue import Queue
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def __str__(self):
return str(self.data)
class BST:
def __init__(self):
self.root = None
# 삽입
def insert(self, data):
self.root = self.insert_data(self.root, data)
def insert_data(self, node, data):
if node == None:
node = Node(data)
else:
if data <= node.data:
node.left = self.insert_data(node.left, data)
else:
node.right = self.insert_data(node.right, data)
return node
# 탐색
def find(self, key):
return self.find_data(self.root, key)
def find_data(self, node, key):
if node == None:
return False
if node.data == key:
return True
elif node.data > key:
return self.find_data(node.left, key)
else:
return self.find_data(node.right, key)
# 전위 순회
def preorder(self, node):
if node != None:
print(node.data, end=' ')
self.preorder(node.left)
self.preorder(node.right)
# 중위 순회
def inorder(self, node):
if node != None:
self.inorder(node.left)
print(node, end=' ')
self.inorder(node.right)
# 후위 순회
def postorder(self, node):
if node != None:
self.postorder(node.left)
self.postorder(node.right)
print(node, end=' ')
# 레벨 순서 순회
def levelorder(self, node):
if node != None:
q = Queue()
q.put(node)
while not q.empty():
n = q.get()
if n.left != None:
q.put(n.left)
if n.right != None:
q.put(n.right)
print(n, end=' ')
# 삭제
def delete(self, key):
self.root, is_deleted = self.delete_data(self.root, key)
return is_deleted
def delete_data(self, node, key):
if node == None:
return node, False
is_deleted = False
if key == node.data:
is_deleted = True
if node.left and node.right:
parent, child = node, node.right
while child.left != None:
parent, child = child, child.left
child.left = node.left
if parent != node:
parent.left = child.right
child.right = node.right
node = child
elif node.left or node.right:
node = node.left or node.right
else:
node = None
elif key < node.data:
node.left, is_deleted = self.delete_data(node.left, key)
else:
node.right, is_deleted = self.delete_data(node.right, key)
return node, is_deleted
tree = BST()
lst = [5, 3, 10, 1, 7, 15, 2, 6, 8]
# BST에 삽입
for x in lst:
tree.insert(x)
print('Pre-Order Traversal: ', end='')
tree.preorder(tree.root)
print('\nIn-Order Traversal: ', end='')
tree.inorder(tree.root)
print('\nPost-Order Traversal: ', end='')
tree.postorder(tree.root)
print('\nLevel-Order Traversal: ', end='')
tree.levelorder(tree.root)
'''
5 3 1 2 10 7 6 8 15
1 2 3 5 6 7 8 10 15
2 1 3 6 8 7 15 10 5
5 3 10 1 7 15 2 6 8
'''
동적 계획법(Dynamic Programming)
동적 계획법은 분할 정복과 비슷하며, 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법입니다. 쉽게 말하면 답을 구하기 위해 과거의 답을 재활용하는 것으로, Memoization 개념이 쓰입니다.
메모이제이션은 ‘메모’에 초점이 맞춰진 단어이면서, 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써 중복 계산을 방지할 수 있게 하는 기법입니다. 즉, 동적 계획법은 메모리라는 공간 비용을 투입해 계산에 소요되는 시간 비용을 줄이는 방식입니다.
'''
피보나치(재귀)
-> 숫자가 조금만 커져도 시간 복잡도와 공간 복잡도가 지수 스케일로 증가한다.(Exponential Explosion)
'''
def fib(n):
if n <= 2:
return n-1
return fib(n-2) + fib(n-1)
# Top-Bottom
memo = [-1] * 100 # 0, 1번째는 신경쓰지 않아도 됨.
def dp_fib(n):
if n <= 2:
return n-1
if memo[n] != -1:
return memo[n]
memo[n] = dp_fib(n-2) + dp_fib(n-1)
return memo[n]
# Bottom-Up
top = 1
memo2 = [-1] * 100
memo2[0] = 0
memo2[1] = 1
def dp_fib2(n):
global top
if memo2[n-1] == -1:
for i in range(top+1, n):
memo2[i] = memo2[i-2] + memo2[i-1]
top = n-1
return memo2[n-1]
for i in range(1, 11):
print(fib(i))
for i in range(1, 11):
print(dp_fib(i))
for i in range(1, 11):
print(dp_fib2(i))
시간복잡도
- O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(N^3) < … < O(2^N) < O(N!)
파이썬 list 연산의 시간 복잡도
- O(1): append, pop, len, [i]
- O(K): [i:j]
- O(N): x in list, count, index, pop(0)->전체복사, del, min, max, reverse
- O(N log N): sort