알고리즘으로 생각하기 - 양성봉 참고
백준 문제를 풀다가 알고리즘 풀이가 잘 기억이 나지 않아서
교과서에 있는 알고리즘 코드를 외우기 위해 작성
순환 팩토리얼
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
print(factorial(5))
5 * 4 * 3 * 2 * 1
팩토리얼 반복문
factorial = 1
for i in range(1, 6):
factorial *= i
print(factorial)
1 * 2 * 3 * 4 * 5
팩토리얼 계산은 순환 사용보다 반복문 이용하는 것이 메모리를 훨씬 적게 사용한다.
순차 탐색
설명
리스트에 값이 있고, 원하는 값을 첫 번째부터 비교하면서 그 위치 값을 리턴하는 알고리즘
시간 복잡도
O(n)
코드
def search_list(a, x):
n = len(a) # 입력 크기 n
for i in range(0, n): # 리스트 a의 모든 값을 차례로
if x == a[i]: # x 값과 비교하여
return i # 같으면 위치 돌려줍니다.
return -1 # 끝까지 비교해서 없으면 -1을 돌려줍니다.
v = [17, 92, 18, 33, 58, 7, 33, 42]
print(search_list(v, 18)) # 2(순서상 세 번째지만, 위치 번호는 2)
print(search_list(v, 33)) # 3(33은 리스트에 두 번 나오지만 처음 나온 위치만 출력)
print(search_list(v, 900)) # -1(900은 리스트에 없음)
순환 이진 탐색
설명
오름차순으로 정렬된 데이터를 반으로 나누고, 나누어진 반을 또 나누고 반복해서
원하는 숫자를 찾는 알고리즘
시간 복잡도
O(logn)
코드
def binary_search(a, left, right, K):
if right >= left:
mid = (left + right)//2
if a[mid] == K:
return True
elif a[mid] > K:
return binary_search(a, 0, mid - 1, K)
else:
return binary_search(a, mid + 1, right, K)
else:
return False
input_list = [10, 20, 25, 35, 45, 55, 60, 75, 85, 90]
n = len(input_list)
print('55 탐색:', binary_search(input_list, 0, n-1, 55))
print('50 탐색:', binary_search(input_list, 0, n-1, 50))
스택
def push(item):
stack.append(item)
def pop():
if len(stack) != 0:
item = stack.pop(-1)
return item
stack = []
큐
def add(item):
q.append(item)
# 스택과 같다
def remove():
item = q.pop(0) # 스택과는 달리 pop(-1)이 아닌 pop(0)
return item
q = []
힙 정렬
설명
힙 트리를 사용해 정렬
O(nlogn)
코드
import heapq
a = [54, 88, 77, 26, 93, 17, 49, 10, 11, 31, 22, 44, 20]
print('정렬 전:\t', a)
heapq.heapify(a) # 최소 힙 만들기
print('힙: \t\t', a)
s = []
while a:
# 힙에서 루트를 삭제하여 s의 맨 뒤에서 추가하는 방식으로 정렬
s.append(heapq.heappop(a))
print('정렬 후:\t', s)
힙 = 부모의 우선순위가 자식의 우선순위보다 높은 것
파이썬 heapq
heapq.heapify(a) # 리스트 a를 최소 힙으로 만들기
heapq.heappush(a, item) # item을 힙 a에 삽입
heapq.heappop(a) # 힙 a의 루트 삭제
heapq.heappushpop(a, item) # 힙 a에 item을 삽입한 후, 루트 삭제
heapq.heapreplace # 힙 a의 루트를 삭제한 후, item을 삽입
그래프 DFS
설명
깊이 우선 탐색(DFS)
탐색이 각 정점을 한번씩 방문하며, 각 간선을 한번씩(두번? = 백트래킹도 하기 때문)만 사용하여
탐색하기 때문에 O(n+m) * 2정도
- n = 그래프의 정점의 수, m = 간선의 수
DFS 방문 순서: 0 2 3 9 8 1 4 5 7 6
코드
adj_list = [[2, 1], [3, 0], [3, 0], [9, 8, 2, 1],
[5], [7, 6, 4], [7, 5], [6, 5], [3], [3]]
n = len(adj_list)
visited = [False for _ in range(n+1)]
def dfs(v):
visited[v] = True # v를 방문하고
print(v, ' ', end='') # v를 출력
for w in adj_list[v]:
if not visited[w]:
dfs(w) # v에 인접하면서 방문 안 된 w를 가지고 순환 호출
print('DFS 방문 순서')
for i in range(n): # 그래프가 2개 이상의 연결 성분을 가진 경우를 대비하여
if not visited[i]:
dfs(i) # 정점 i로 dfs 호출
그래프 BFS
너비 우선 탐색(BFS)
각 정점을 한번씩 방문하며, 각 간선을 한 번씩만 사용하여 탐색하기 때문에 O(n+m)
BFS 방문 순서: 0 2 1 3 9 8 4 5 7 6
4 5 6 7이 아니고 4 5 7 6인 이유는 4 → 5가고 백트래킹 했을 때 6으로 가는 곳이 없어서
코드
adj_list = [[2, 1], [3, 0], [3, 0], [9, 8, 2, 1],
[5], [7, 6, 4], [7, 5], [6, 5], [3], [3]]
n = len(adj_list)
visited = [False for _ in range(n+1)]
def bfs(v):
queue = []
visited[v] = True
queue.append(v)
while len(queue) != 0:
u = queue.pop(0)
print(u, ' ', end='')
for w in adj_list[u]:
if not visited[w]:
visited[w] = True
queue.append(w)
print('BFS 방문 순서:')
for i in range(n):
if not visited[i]:
bfs(i)