🔊 이번 포스팅에는 최근에 Python으로 알고리즘을 공부하기 시작하면서 알게 된 여러 알고리즘의 원리와 Python으로 구현하는 방법에 대해 소개해보려 한다. 필자는 최근 알고리즘 공부를 '나동빈'님의 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 이라는 책과 백준 온라인 저지 사이트로 하고 있다. 이 중 '나동빈'님이 저자이신 책에서 가르쳐주는 내용을 기반으로 배운 내용을 정리해보려 한다.
알고리즘 종류가 다양하지만 이번에 배운 개념들은 탐색 알고리즘의 대표적 방법들인 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색), 그리고 정렬 알고리즘의 종류들인 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬에 대해 알아보자. 또 각 챕터마다 하단에는 Python으로 알고리즘을 구현해 보기도 하자.
탐색 알고리즘의 종류들부터 알아보기 이전에 탐색 알고리즘들은 기본적으로 그래프라는 데이터를 이용할 때 자주 사용된다. 그래프 데이터란, 노드(Node = Vertex = 정점)와 엣지(Edge = 간선)로 이루어진 데이터 형태이다. 아마 몇몇 분들은 딥러닝 모델 중 GNN(Graph Neural Network) 이라는 것을 알고 계실 텐데, 이 GNN에서 말하는 Graph와 비슷한 형태이다. 이러한 데이터로 이루어진 문제를 해결할 때 DFS, BFS 알고리즘이 자주 사용된다.
어쨌거나 탐색 알고리즘은 위와 같이 그래프 데이터일 때 자주 사용된다. 그런데 컴퓨터는 위와 같은 그림 형태의 데이터를 인식하지 못하고 숫자로 이야기를 해주어야 한다. 어떻게 나타낼까? 크게 2가지 방법으로 나타낼 수 있다. 먼저 인접 행렬(Adjacency Matrix)로 나타낼 수 있다. 인접 행렬은 우리가 고등학교 수학 시간에 배웠던 적이 있어 어렴풋이 기억이 날 수 있을 것이다.
이러한 인접 행렬을 '코딩 테스트' 차원에서 바라보자면 메모리 측면에서 비효율적이게 된다. 왜냐하면 중간 중간 0값이 존재하는 즉, 서로 연결되어 있지 않는 노드들 간의 관계까지 설명하고 있기 때문이다. 하지만 이것이 장점이 될 때도 있다. 어떤 특정한 두 노드들 간의 연결 유무를 파악할 때는 바로 밑에서 소개할 인접 리스트 방식 보다는 효율적이다.
그렇다면 인접 리스트 방식은 무엇일까? 바로 노드들 간의 인접한 정보를 Python의 이중 리스트로 나타낸 것을 의미한다. 다음 그림을 살펴보자.
위 그림의 왼쪽인 그래프 형태의 데이터를 인접 리스트 방식으로 변형한다면 오른쪽과 같아진다. 빨간색 글씨로 되어 있는 부분은 두 노드 간의 간선에 부여된 값을 의미한다. 여기서는 간선에 부여된 값은 중요하지 않고 오른쪽의 인접 리스트 형태를 Python 리스트 자료구조로 변환하면 다음과 같아진다.
# 가장 바깥을 감싸고 있는 리스트의 index 값이 노드 번호를 의미
# 각 요소를 이루고 있는 튜플의 첫 번째 값은 노드를 두 번째 값은 두 노드를 연결하는 간선에 부여된 값을 의미
adjacency_list = [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]
위 코드의 주석에도 써있다시피 이중 리스트 중 가장 바깥을 감싸고 있는 리스트의 index 번호가 노드 번호를 의미한다. 즉, 0번째 index인 0번 노드는 1번 노드와 간선이 7인 값으로 연결되어 있고 2번 노드와 간선이 5인 값으로 연결되어 있음을 의미한다.
이러한 인접 리스트 방식으로 표현하게 되면 인접 행렬 방식과는 달리 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다. 반면 인접행렬의 장점이기도 했던 '두 노드간의 연결 여부를 확인' 하는 문제에서는 인접 리스트 방식이 정보를 얻는 속도가 느리다는 단점이 있다.
자, 이제 DFS, BFS에 대해 본격적으로 배워보자.
탐색 알고리즘
1. DFS(Depth-First-Search)
깊이 우선 탐색 알고리즘이라고도 한다. 이름 그대로 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택이라는 자료구조를 활용해서 구현된다. 스택 자료구조는 FILO(First-In-Last-Out) 방식을 따른다. 즉, 스택에 데이터를 집어넣을 때 순서와 스택에서 데이터를 꺼낼 때 순서가 역방향이라는 것이다. 다음 그림을 보면 이해가 수월할 것이다.
DFS 알고리즘은 특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후 다시 돌아가 다른 경로를 탐색하는 알고리즘이다. 이 때 경로를 탐색하다 동일한 깊이의 인접한 노드가 여러개 있다면 이 중 노드의 번호가 작은 것부터 차례대로 탐색하는 것이 관행이라고도 한다. DFS 알고리즘이 노드를 탐색하는 구체적인 과정은 나동빈님의 7분 강의를 참고하자.
그렇다면 이 DFS 알고리즘을 Python으로 어떻게 구현할까? 주목할 만한 점은 재귀함수를 사용한다는 것이다. 최대한 '깊게' 탐색하는 것이기 때문에 인접한 노드의 인접한 노드의 인접한... 이런 식으로 진행되기 때문에 재귀함수를 사용하게 된다. 다음과 같은 그래프 데이터가 있다고 가정하고 Python으로 DFS를 구현해보자.
참고로 구현할 때 인접 리스트 방식으로 그래프 데이터를 변환했다.
# DFS - 깊이 우선 탐색 -> 스택을 이용. 파이썬에서 리스트는 스택으로 구현되어 있음!
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 방문노드
visited = [False] * len(graph)
def dfs(graph, v, visited):
visited[v] = True
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
# 0번 노드가 없으니 1번 노드부터 탐색
dfs(graph, 1, visited)2. BFS(Breadth-First-Search)
너비 우선 탐색 알고리즘이라고도 한다. 너비 우선 탐색은 가장 가까운 노드부터 탐색하는 알고리즘이다.(이러한 측면에서 봤을 때 DFS는 최대한 깊은 부분을 탐색한다는 점에서 가장 멀리 있는 노드를 우선으로 탐색한다는 차이점이 있다.)
BFS는 큐라는 자료구조를 사용한다. 큐는 FIFO(First-In-First-Out) 방식을 사용한다. 즉, 큐에 데이터를 넣을 때 순서와 큐에서 데이터를 뺄 때 순서가 동일하다. 다음 그림을 살펴보자.
BFS도 만약 동일한 깊이의 노드가 여러개 있다면 큐에 노드에 새겨진 숫자가 작은 노드들 부터 삽입한다는 점을 알고있자. BFS가 동작하는 구체적인 프로세스도 나동빈님의 7분 강의를 참고하자.
이제 BFS도 Python으로 구현해보자. 큐를 사용해야 하는데 Python에서는 collections 라이브러리가 제공하는 deque 메소드를 사용하면 된다. DFS 구현 때와 동일하게 다음과 같은 그래프 데이터가 주어졌을 때 BFS를 Python으로 구현한 코드는 다음과 같다.
# BFS - 너비 우선 탐색 - 큐(FIFO)를 이용. collections의 deque 이용!
from collections import deque
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * len(graph)
def bfs(graph, start, visited):
# 시작 노드를 큐에다가 먼저 삽입(삽입할 때 파이썬 리스트[]로 감싸주기)
queue = deque([start])
# 시작 노드를 방문 처리
visited[start] = True
# 큐에서 노드를 pop하고 그 노드의 인접노드들을 탐색. 단, 큐가 빌(False)때 까지
while queue:
v = queue.popleft()
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
visited[i] = True
queue.append(i)
bfs(graph, 1, visited)
정렬 알고리즘
1. 선택 정렬(Selection Sort)
개인적으로 생각하기에 단순 무식(?)한 정렬 방법인 것 같다. 무작위로 정렬된 데이터가 있을 때, 가장 작은 데이터를 선별해 가장 앞의 인덱스 위치에 놓고 그 다음으로 작은 데이터를 선별해 두 번째 인덱스 위치에 놓고... 계속적으로 하여 N-1번 반복하는 알고리즘이다. 그림으로 표현하면 다음과 같다.
선택 정렬을 Python으로 구현하면 다음과 같아진다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(array)):
min_idx = i
for j in range(i+1, len(array)):
if array[j] < array[min_idx]:
min_idx = j
# 위치 스와핑하기
array[i], array[min_idx] = array[min_idx], array[i]
print(array)
선택정렬은 원소를 모두 비교하기도 하며 위 Python 코드를 보면 이중 for loop 구문을 사용한 것을 보면 알겠지만 시간 복잡도가 $O(N^2)$이 된다.
2. 삽입 정렬(Insertion Sort)
삽입 정렬의 아이디어는 데이터를 하나씩 확인하면서 그 데이터의 적절한 위치에 삽입해보자는 것에서 유래했다. 삽입 정렬의 주요한 특징은 주어진 데이터의 가장 첫 번째에 위치한 데이터는 정렬되었다고 가정하고 시작을 한다. 따라서 두 번째 위치에 있는 데이터부터 하나씩 확인해보면서 왼쪽에 있는 데이터와 비교를 해서 왼쪽에 있는 데이터보다 작다면 왼쪽으로 계속 이동하고 크다면 그 자리에 그대로 두는 로직으로 구성된다. 이러한 로직으로 구성되면 비교를 점차적으로 하면서 왼쪽에 있는 데이터들은 항상 오름차순을 유지하게 된다.
삽입 정렬을 Python으로 구현하면 다음과 같다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(array)): # 0번째 데이터는 정렬된 것으로 가정
for j in range(i, 0, -1): # i번째부터 1번째 idx까지 왼쪽으로 이동
if array[j-1] > array[j]:
array[j-1], array[j] = array[j], array[j-1]
else:
break
print(array)
삽입 정렬은 만약 주어진 데이터가 거의 정렬되어 있다면 매우 효율적으로 동작한다. 하지만 최악의 경우 삽입 정렬의 시간 복잡도는 $O(N^2)$가 된다.
3. 퀵 정렬(Quick Sort)
퀵 정렬은 알고리즘 종류 중 가장 많이 사용되는 알고리즘 중 하나이다. 퀵 정렬과 비슷한 유형으로 병합 정렬 알고리즘이 있는데, 이 병합 정렬은 Python 정렬 라이브러리를 구현할 때 사용된 알고리즘이라고 한다.
퀵 정렬은 기준 데이터를 설정하고 그 기준보다 큰 데이터, 작은 데이터의 위치를 바꾸는 아이디어에서 출발했다. 이 때 기준 데이터를 피벗(Pivot)이라고 한다. 피벗을 정하는 기준에 여러가지가 있지만 여기서는 호어 분할 방식의 기준으로 하여 데이터의 가장 첫 번째 요소를 피벗으로 설정하도록 한다.
피벗 데이터를 선정하고 왼쪽 방향부터 시작해 차례차례 데이터를 확인해가면서 피벗 데이터 값보다 큰 데이터 값이 첫 번째로 등장한 데이터를 지정한다. 반대로 오른쪽 방향(데이터 끝에서)으로 차례차례 데이터를 확인해가면서 피벗 데이터보다 작은 데이터 값이 첫 번째로 등장한 데이터를 지정한다. 그리고 이 두개의 위치를 교환한다.
이런 과정을 반복하다가 두개의 데이터 위치 index가 엇갈릴 경우 피벗보다 작은 값으로 처음 등장한 데이터와 피벗 데이터와 위치를 교환한다. 그리고 피벗의 바뀐 위치를 기준으로 양 옆으로 '분할(파티션이라고도 함)'해 만들어진 2개의 리스트에서 각각 퀵 정렬을 또 수행한다. 텍스트로 이해가 잘 안된다면 하단의 그림을 참고하자.
위 그림을 보고도 잘 이해가 되지 않는다면 나동빈님의 10분 강의를 살펴보자. 나동빈 님의 책에서도 언급했지만 퀵 정렬 동작 과정이 잘 이해가 안간다면 종이에 숫자를써서 잘라서 직접 해보라고 했다. 필자도 한 번에 이해가 안되서 3,4번 정도 직접 해보니 이해가 확 와 닿았다. 개인적으로 손으로 하는 방식도 추천한다!😀
퀵 정렬을 Python으로 구현하는 방법은 크게 2가지로 나뉠 수 있는데 첫 번째는 일반적인 재귀함수를 사용하는 것이고 두 번째는 파이썬의 장점을 살려 재귀함수로 구현한 방법이다. 먼저 일반적인 재귀함수를 사용한 소스 코드이다.
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array, start, end):
if start >= end: # 원소 개수가 1개이거나 end가 -1일 경우 멈추기
return
# 얘네들은 index위치를 나타냄!
pivot = start
left = start + 1
right = end
# 왼,오른쪽이 엇갈지지 않을 경우 계속 반복
while left <= right:
while left <= end and array[left] < array[pivot]:
left += 1
while right > start and array[right] > array[pivot]:
right -= 1
# 왼,오 이동하다가 엇갈릴 떄 -> right와 pivot 교체
if right < left:
array[pivot], array[right] = array[right], array[pivot]
# 왼, 오 엇갈리지 않으면 -> right, left 값 교체
else:
array[left], array[right] = array[right], array[left]
# 엇갈린 다음엔 파티션이 이루어지고 피벗을 기준으로 왼,오 퀵정렬 재귀적으로 수행
quick_sort(array, start, right-1) # right자리에 pivot이 있기 때문!
quick_sort(array, right+1, end)
quick_sort(array, 0, len(array)-1)
print(array)
다음은 파이썬의 장점을 살려 재귀함수로 구현한 코드이다.
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array):
# 재귀함수 종단 조건
if len(array) <= 1:
return array
pivot = array[0]
tail = array[1:]
# Pivot값 기준으로 왼쪽은 모두 Pivot보다 작은 값, 오른쪽은 큰 값들
left_side = [x for x in tail if x <= pivot]
right_side = [x for x in tail if x > pivot]
return quick_sort(left_side) + [pivot] + quick_sort(right_side)
res = quick_sort(array)
print(res)
퀵 정렬의 평균 시간 복잡도는 $O(NlogN)$이다. 하지만 최악의 경우 시간 복잡도가 $O(N^2)$까지 늘어날 수 있다. 따라서 데이터가 무작위로 입력될 경우 퀵 정렬을 사용하면 빠르게 동작할 확률이 높다. 하지만 이미 데이터가 정렬되어 있는 경우(이럴 때 삽입 정렬을 사용하는 게 적절하다고 위에서 언급했었다!) 매우 느리게 동작하게 된다. 그래도 책에선 Python에서 제공하는 정렬 라이브러리가 이러한 퀵 정렬의 단점을 잘 보완하면서 병합정렬 기반으로 구현되었기에 "우리에겐 파이썬 정렬 라이브러리가 있으니 큰 걱정은 하지말라!"고 안심(?)을 시켜준다.
4. 계수 정렬(Counting Sort)
계수 정렬은 특정한 조건이 부합할 때만 사용할 수 있지만, 그 조건을 만족할 경우 사용하면 매우 빠른 정렬 알고리즘이다. 그 조건이라 함은 바로 제한된 크기 범위의 정수 형태로 데이터가 주어질 경우에만 사용할 수 있다는 것이다. 그리고 가장 큰 데이터와 가장 작은 데이터의 차이가 백만(1,000,000)을 넘지 않을 때 효과적으로 사용할 수 있고 중복된 데이터가 여러개 나타날 경우에도 적절히 사용될 수 있다.
그리고 계수 정렬을 사용할 때 주목할 만한 점은 주어진 데이터의 모든 범위를 담을 수 있는 크기의 빈 리스트를 먼저 정의해야 한다는 것이다. 그리고 이름에서 알 수 있다 시피 Count 즉, 빈 리스트에 데이터의 값들이 몇 번 발생했는지 횟수를 기록한다. 다음 그림을 살펴보자.
계수 정렬을 Python으로 구현한 소스코드는 다음과 같다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 데이터 범위만큼의 빈 리스트 정의 => array의 길이만큼이라는 뜻은 아님!!! 왜냐면 중복된 값이 있을 수 있기 때문!
count = [0] * (max(array) + 1)
for i in range(len(array)):
count[array[i]] += 1
for i in range(len(count)):
for j in range(count[i]):
print(i, end=' ')
계수 정렬은 모든 데이터가 양의 정수인 상황에서 데이터 개수를 N, 데이터의 최댓값을 K라고 할 때, 시간 복잡도는 $O(N+K)$가 된다. 공간 복잡도도 또한 $O(N+K)$가 된다.
'Python > 알고리즘 개념' 카테고리의 다른 글
| [Python] 우선순위 큐를 활용한 개선된 다익스트라(Dijkstra) 알고리즘 (6) | 2021.09.23 |
|---|---|
| [Python] 최단경로를 위한 다익스트라(Dijkstra) 알고리즘 (0) | 2021.09.22 |
| [Python] 알고리즘을 위한 주요 라이브러리와 유의점 (0) | 2021.09.14 |
| [Python] Dynamic Programming(동적계획법) 알고리즘 (0) | 2021.04.14 |
| [Python] 순차(Sequential) 탐색과 이진(Binary) 탐색 알고리즘 (0) | 2021.04.12 |
