동적계획법(Dynamic programming)은 복잡한 문제를 여러 개의 간단한 문제로 분리, 단위별로 문제를 해결하여 전체 문제를 푸는 방법입니다. 동적계획법의 원리와 구현 방식은 다음과 같다고 합니다. [1]
큰 문제를 작은 문제로 나눈다.
작은 문제들이 반복되고, 작은 문제들의 결과 값은 항상 같아야 한다.
작은 문제들은 한 번만 계산해 DP 테이블(Dynamic Programming Table)에 저장합니다. 작은 문제들의 답을 활용할 때는 DP 테이블에서 가져옵니다. (Memoization)
이를 Top-down과 Bottom-up 방식 중 하나로 구현합니다.
이렇게만 보면 이해가 어렵기 때문에 대표적인 동적계획법 문제인 피보나치 수열 구현을 통해 살펴보겠습니다.
피보나치 구현
과정 1
피보나치 수열은 다음 항이 이전 두 항의 합으로 이뤄진 수열입니다. 그리고 두 개의 항 역시 그 이전의 항들의 합들로 이뤄지는 점화식 형태이기 때문에 작은 문제들로 분리할 수 있습니다.
과정 2
점화식 형태로 나타낼 수 있다는 것은 작은 문제들이 반복되고, 그 구조가 비슷함을 의미합니다. 따라서, 피보나치 문제는 동적계획법을 통해 접근이 가능합니다.
피보나치 수열 점화식 [2]
과정 3
메모이제이션(Memoization)은 어떻게 구현해야 할까요? 처음에 주어지는 두 항을 저장하고 그 다음부터는 점화식에 따라 계산되는 값을 저장해주면 될 것입니다.
과정 4
피보나치 수열은 비교적 간단한 코드이기 때문에 바로 비교해보도록 하겠습니다. 우선 Top-down 방식은 주로 재귀 함수를 통해 구현하며, 그렇기 때문에 가독성이 좋습니다. 다만, 재귀함수를 쓰는만큼 반복해야 하는 숫자가 증가할 경우 런타임 에러를 발생시킬 우려가 있습니다.
세그먼트 트리(Segment Tree)는 구간 합과 같이 구간에 대한 데이터 쿼리와 업데이트를 효율적으로 처리하기 위한 자료구조 형태 입니다. 세그먼트 트리는 트리 구조를 통해 구간 연산을 빠르게 수행할 수 있습니다.
세그먼트 트리는 배열을 트리 형태로 표현하여 배열의 구간을 부모 노드에 저장합니다. 구간의 크기를 반으로 나눠 트리의 리프 노드에는 배열의 원소를 저장하고, 상위 노드에는 하위 노드의 값을 합쳐서 저장합니다.
세그먼트 트리 구현
세그먼트 트리는 다음과 같은 과정을 통해 동작합니다.
트리 초기화 : 배열을 리프 노드로 갖는 세그먼트 트리 초기화
구간 질의 : 특정 구간의 연산 결과(구간 합, 최대값, 최소값)을 빠르게 계산
업데이트 : 배열의 특정 값을 변역하고, 그에 맞춰 트리의 값 업데이트
이러한 동작을 하기 위해서는 아래와 같은 트리 구조를 구현해야 합니다.
루트 노드 : 배열 전체를 나타내며, 배열의 합을 저장
리프 노드 : 배열의 각 원소
내부 노드 : 두 자식 노드를 더한 값을 저장
트리 초기화
리프 노드의 갯수가 데이터 개수(n) 이상이 되도록 트리 리스트를 만듭니다. 트리 리스트의 크기는 2n으로 생성합니다. 리프 노드로는 n부터 2n-1까지가 사용됩니다. 리프 노드에는 원본 데이터 값으로 채웁니다. 리프 노드를 다 채웠다면, 자식 노드의 인덱스는 이진 트리 형식에 맞춰 트리를 채웁니다. (여기서는 나머지 노드에 역순으로 구현)
class SegmentTree:
def __init__(self, data):
self.n = len(data)
self.tree = [0] * (2 * self.n)
self.build(data)
# 세그먼트 트리 초기화 (트리 빌드)
def build(self, data):
# 리프 노드를 배열의 값으로 채운다
for i in range(self.n):
self.tree[self.n + i] = data[i]
# 내부 노드를 구간 합으로 채운다 (역순으로 채워감)
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
구간 질의
주어진 질의 인덱스를 세그먼트 트리의 리프 노드에 해당하는 인덱스로 변경합니다. 기존 샘플을 기준으로 한 인덱스 값과 세그먼트 트리 리스트를 변경합니다. 질의 값을 구하는 과정은 다음과 같이 진행 됩니다.
시작 인덱스(left)가 홀수일 때 해당 노드를 선택
끝 인덱스(right)가 짝수일 때 해당 노드를 선택
시작 인덱스 깊이 변경 : left = (left +1) / 2
끝 인덱스 깊이 변경 : right = (right -1) / 2
left <= right 인덱스가 유지되는 한 1~4 과정을 반복
# 구간 합을 구한다 (left, right 구간의 합)
def query(self, left, right):
left += self.n
right += self.n
sum = 0
while left <= right:
if left % 2 == 1:
sum += self.tree[left]
left += 1
if right % 2 == 0:
sum += self.tree[right]
right -= 1
left //= 2
right //= 2
return sum
업데이트
데이터 업데이트는 부모 노드로 이동하며서 업데이트를 진행합니다. 다만, 어떤 연산을 수행할 것인지에 따라서 방식이 다르다는 점만 이해하시고 진행하면 됩니다. 아래는 구간 합 기준으로 설명합니다.
# 값 업데이트 (pos번째 원소를 value로 변경)
def update(self, pos, value):
# 리프 노드 업데이트
pos += self.n
self.tree[pos] = value
# 부모 노드들을 갱신
while pos > 1:
pos //= 2
self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]
전체 코드
class SegmentTree:
def __init__(self, data):
self.n = len(data)
self.tree = [0] * (2 * self.n)
self.build(data)
def build(self, data):
for i in range(self.n):
self.tree[self.n + i] = data[i]
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
def query(self, left, right):
left += self.n
right += self.n
sum = 0
while left <= right:
if left % 2 == 1:
sum += self.tree[left]
left += 1
if right % 2 == 0:
sum += self.tree[right]
right -= 1
left //= 2
right //= 2
return sum
def update(self, pos, value):
pos += self.n
self.tree[pos] = value
while pos > 1:
pos //= 2
self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]
최소신장트리(Minimum Spanning Tree, MST)는 그래프의 모든 정점을 연결하는 트리 중에서 가중치들의 합이 최소인 트리를 말합니다. 가중치 최소화를 목적으로 하기 때문에 다양한 최적화 문제에 사용될 수 있는데, MST를 구하는 대표적인 알고리즘으로 크루스칼 알고리즘을 활용할 수 있습니다.
크루스칼 알고리즘(Kruskcal's Algorithm)은 엣지 중심의 알고리즘으로 엣지를 가중치 기준으로 오름차순 정렬하고, 최소 가중치 엣지부터 차례대로 사이클이 발생하지 않도록 트리를 구성하는 방식으로 동작합니다. 사이클을 방지하기 위해 Union-Find를 활용합니다. 크루스칼 알고리즘의 동작 과정은 다음과 같습니다.
엣지 리스트 생성 : 그래프의 엣지를 가중치에 따라 오름차순으로 정렬
정렬된 엣지 리스트에서 하나씩 선택하고, 사이클을 만들지 않으면 트리에 포함
2를 모든 간선을 선택할 때까지 반복
엣지 리스트 생성
MST는 엣지 중심이므로 엣지 리스트를 저장해야 합니다. 파이썬에서는 Priority Queue(우선순위 큐) 라이브러리를 제공하고 있으므로 활용합니다. 우선순위 큐에서는 앞에서부터 정렬되기 때문에 가중치를 가장 앞으로 배치해서 값을 넣어줍니다. 또한, 사이클 처리하기 위한 Union Find를 위한 리스트도 함께 초기화합니다. 유니온 파인드 리스트는 인덱스를 해당 자리의 값으로 초기화하면 됩니다.
from queue import PriorityQueue
uf_list = [0] * (N+1) # N은 노드 수
for i in range(N+1):
uf_list[i] = i
pq = PriorityQueue()
for _ in range(M): # M은 엣지 수
s, e, w = map(int, input().split())
pq.put((w, s, e)) # Priority Queue에서는 앞부터 정렬되기 때문에 가중치를 가장 앞으로 배치
가중치가 낮은 엣지부터 연결
가장 작은 가중치의 엣지부터 연결을 시도합니다. 연결하기 전에 사이클 발생 여부를 판별(find를 통해 같지 않음을 확인 후)하고 사이클이 없을 경우에만 연결을 합니다. 연결된 경우에는 유니언 파인드 리스트에 업데이트를 진행합니다. 그리고 이 과정을 노드 수 N에 대하여 연결한 엣지가 N-1가 될 때까지 반복합니다.
def find(a):
if a == uf_list[a]:
return a
else:
uf_list[a] = find(uf_list[a])
return uf_list[a]
def union(a, b):
a = find(a)
b = find(b)
if a != b:
uf_list[b] = a
edge = 0
while edge < N-1:
w, s, e = pq.get()
if find(s) != find(e):
union(s, e)
edge += 1
전체 코드
from queue import PriorityQueue
uf_list = [0] * (N+1)
for i in range(N+1):
uf_list[i] = i
pq = PriorityQueue()
for _ in range(M):
s, e, w = map(int, input().split())
pq.put((w, s, e))
def find(a):
if a == uf_list[a]:
return a
else:
uf_list[a] = find(uf_list[a])
return uf_list[a]
def union(a, b):
a = find(a)
b = find(b)
if a != b:
uf_list[b] = a
edge = 0
while edge < N-1:
w, s, e = pq.get()
if find(s) != find(e):
union(s, e)
edge += 1
이항 계수(Binomial Coefficient)는 주어진 n개 중 k개를 고르는 경우의 수를 의미하며, 수학적으로 표현하면 다음과 같이 표현됩니다. 흔하게 조합이나, nCk의 형태로 표현되기도 합니다.
이항 계수의 정의[1]
식으로 표현된 것처럼 팩토리얼을 통해 구현하는 방법도 있지만, 이는 재귀적으로 구현해야 하며 연산량이 매우 커질 수 있습니다. 이에 대한 대안으로 동적 계획법(Dynamic Programming)을 이용한 이항 계수를 계산하는 방법이 있습니다. 이는 아래와 같이 파스칼의 법칙이라 불리는 점화식의 형태로 정리할 수 있습니다.
파스칼의 법칙 [1]
이를 구현하기 위해 파이썬 코드로 정리하면 다음과 같습니다. 우선, 파스칼의 삼각형을 만들 2차 리스트를 만듭니다. 그리고 하나도 고르지 않거나 / 모두 고르는 경우의 수는 1, 전체 중 하나는 고르는 경우의 수는 해당 숫자로 초기화 합니다.
N = 5
C = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(0, N+1):
C[i][1] = i
C[i][0] = 1
C[i][i] = 1
>>>
위에 언급한 파스칼 법칙의 점화식을 이중 for 루프를 통해 적용합니다. 아래 이미지를 보면 잘 적용된 것을 확인할 수 있습니다.
for i in range(2, N+1):
for j in range(1, i):
C[i][j] = C[i-1][j] + C[i-1][j-1]
주어진 이미지와 그에 해당하는 클래스가 대응되는 분류 문제와 다르게 객체 탐지 문제는 객체를 찾고(Localization), 이를 분류(Classification)해야 하는 두가지 일이 존재하기 때문에 데이터의 양식이 조금 더 복잡합니다. 특히, 하나의 이미지에서 여러 개의 객체가 존재할 수도 있기 때문에 더욱 어려운 문제가 될 수 있죠.
이러한 문제들을 극복하기 위해 데이터에 레이블을 붙이는 어노테이션(annotation)을 수행하게 되는데, 어노테이션 방식에 따라 데이터를 처리하는 방식이 달라져야 합니다. 가장 대표적인 객체 탐지 데이터 형식은 COCO, Pascal VOC, YOLO 등이 있습니다.
COCO
COCO는 Common Objects in COntext의 약자로 해당 데이터셋은 객체 탐지, 세그멘테이션, 키포인트 추출 등 다양한 작업을 위한 대규모 데이터셋입니다. COCO 데이터셋은 JSON 파일로 객체의 위치, 크기, 분류 정보를 저장하고 있습니다. 객체 탐지를 위한 주요한 정보는 아래와 같이 정리할 수 있습니다.
Image Info : 이미지 id, 이미지 파일명, 크기(width, height), 이미지 출처 및 수집 시기 등 관련 정
Categories : 클래스 정보(id, 명칭)
Annotations : 각 객체에 대한 어노테이션 정보로 bounding box, segmentation 정보, 클래스 id 등 포함
Bounding box : (x, y, width, height) 형태로 저장되며, 좌측 상단 모서리 좌표(x,y)와 너비와 높이
Segmentation : 객체를 폴리곤 형태로 나타내는 좌표 목록
Category ID : 객체 클래스의 ID
IsCrowd : 객체가 군중인지 여부 (1이면 군중)
특히, Annotations가 중요하므로 예시를 살펴보면 아래와 같이 나타납니다.
COCO 데이터 포맷 중 annotations 예시 [2]
좀 더 자세한 내용을 살펴보고 싶으신 경우 아래 링크들을 참고하면 데이터셋 운영주체나 AWS에서 기술하고 있는 설명을 확인할 수 있습니다.
img0001에 대한 정보를 담은 Pascal VOC 포맷 예시입니다. 보면 상단에는 이미지에 대한 정보들이 있고, object 부터 이미지에 존재하는 여러 객체들에 대한 정보(클래스, 바운딩박스 위치 정보)를 담고 있는 것을 확인할 수 있습니다.
Pascal VOC 예시 [3]
YOLO
YOLO(You Only Look Once)는 객체 탐지 모델로 유명하지만, 데이터셋의 어노테이션 양식도 있습니다. YOLO의 포맷은 txt 형태로 저장되며, 각 줄에 한 객체의 어노테이션 정보를 한 칸씩 띄어쓰기한 형태로 포함합니다. (이러한 형태로 ➡️ 클래스 x y w h)
클래스 인덱스 : 객체가 어떤 클래스에 포함되는지 표현하는 정수
바운딩 박스 좌표 : (x_center, y_center, width, height) 순으로 표현되며, 모두 상대적인 좌표 (0~1 사이 존재)로 주어집니다.
YOLO 데이터셋 포맷의 예시는 아래와 같습니다. 다른 형태에 비해 비교적 간단하게 담아냅니다.
YOLO 데이터셋 포맷 예시[4]
데이터 변환
위에서 살펴보면 데이터셋이 담는 파일 양식(json, xml, txt), 바운딩 박스 표현도 다른 것을 알 수 있습니다. 양식이야 그때 그때 맞춰주면 되겠지만, 바운딩 박스 양식은 크게 영향을 받을 수 있는데 각각의 데이터셋을 변환하는 방법을 정리하려고 합니다. 사실 원리만 알면 2~3개만 정리해도 되지만, 언제든 편리하게 갖다 쓰기 위해 모든 경우의 수를 고려한 6가지 소제목으로 아래와 같이 정리합니다.
COCO ➡️ Pascal VOC
def coco_to_voc(coco_annotations):
voc_annotations = []
for ann in coco_annotations:
x_min, y_min, width, height = ann["bbox"]
xmax = x_min + width
ymax = y_min + height
class_name = coco_category_to_voc_class(ann["category_id"]) # Map category ID to class name
voc_annotations.append({
"class_name": class_name,
"xmin": int(x_min),
"ymin": int(y_min),
"xmax": int(xmax),
"ymax": int(ymax)
})
return voc_annotations
이진 트리(Binary tree)는 각 노드의 자식 노드의 개수가 2개 이하로 구성되어 있는 트리입니다. 이진 트리는 포화 이진 트리, 완전 이진 트리 등이 있습니다. 포화 이진 트리(perfect binary tree)는 트리의 높이가 모두 일정하며 모든 리프 노드가 꽉 찬 이진 트리이며, 완전 이진 트리(complete binary tree)는 마지막 레벨을 제외하고서는 완전하게 노드들이 채워져 있고, 마지막 레벨에는 왼쪽부터 채워진 이진 트리입니다.
이진 트리를 구성하는 자료구조의 형태는 리스트를 활용할 수 있습니다. 리스트의 인덱스에 해당 하는 값을 입력해서 트리를 채우는 방식으로 구현이 가능합니다.
기본 구조 및 데이터 삽입
이진 트리를 만들기 위한 클래스를 선언하고, 리스트에 값을 넣는 함수(insert)와 현재 트리를 반환하는 함수(display)를 작성하였습니다. 다만, 파이썬의 경우 인덱스가 0부터 시작하기 때문에 편의상 1부터 맞춰주기 위해 첫 번째 인덱스는 비워두도록 구성하였습니다.
class BinaryTree:
def __init__(self):
# 이진 트리를 위한 리스트, 첫 번째 인덱스(0)는 비워둠
self.tree = [None]
def insert(self, value):
# 리스트 끝에 새 값을 추가하여 트리에 삽입
self.tree.append(value)
def display(self):
# 현재 트리의 상태를 출력 (리스트 형태로)
return self.tree
자식 노드
이진 트리는 두가지 갈래(왼쪽, 오른쪽)로 나뉩니다. 각각의 자식 노드를 가져오기 위해 별도의 인덱스 접근법이 필요합니다. 가장 상단에 있는 루트 노드를 1로 두고 작성하였을 때는 현재 인덱스(index) 기준으로 아래와 같이 접근할 수 있습니다.
왼쪽 자식 노드 : 2 * index (제약 조건 : 2 * index 가 노드 개수보다 작거나 같은 경우)
오른쪽 자식 노드 : 2 * index + 1 (제약 조건 : 2 * index + 1 가 노드 개수보다 작거나 같은 경우)
이를 파이썬으로 구현하면 아래와 같습니다.
def get_left_child(self, index):
# 왼쪽 자식의 인덱스 계산 (2 * index)
left_index = 2 * index
# 인덱스가 리스트 범위를 넘지 않았을 때만 반환
if left_index < len(self.tree):
return self.tree[left_index]
return None
def get_right_child(self, index):
# 오른쪽 자식의 인덱스 계산 (2 * index + 1)
right_index = 2 * index + 1
# 인덱스가 리스트 범위를 넘지 않았을 때만 반환
if right_index < len(self.tree):
return self.tree[right_index]
return None
부모 노드
자식 노드는 리스트에서 더 하단에 있기 때문에 인덱스가 커졌다면, 부모 노드는 상단에 위치하기 때문에 나눗셈으로 인덱스를 줄여줍니다. 제약 조건은 현재 노드가 루트 노드가 아니어야 합니다.
def get_parent(self, index):
# 부모 노드의 인덱스 계산 (index // 2)
if index == 1:
return None # 루트 노드는 부모가 없음
parent_index = index // 2
return self.tree[parent_index]
전체 코드
위 내용을 전체 코드로 구현하면 아래와 같이 작성할 수 있습니다.
class BinaryTree:
def __init__(self):
self.tree = [None]
def insert(self, value):
self.tree.append(value)
def get_left_child(self, index):
left_index = 2 * index
if left_index < len(self.tree):
return self.tree[left_index]
return None
def get_right_child(self, index):
right_index = 2 * index + 1
if right_index < len(self.tree):
return self.tree[right_index]
return None
def get_parent(self, index):
if index == 1:
return None
parent_index = index // 2
return self.tree[parent_index]
def display(self):
return self.tree
트라이(Trie)는 문자열을 저장하고 검색하기 위한 트리 기반의 자료구조 입니다. 주로 문자열 탐색에 사용되며, 보통 사전, 자동 완성 기능, 접두사 검색 등에 많이 활용됩니다. 트라이의 주요 구조는 다음과 같습니다.
각 노드는 하나의 문자를 나타냅니다.
루트 노드는 비어 있고, 각 자식 노드는 해당 문자에 대응하는 노드를 갖습니다.
문자열이 삽입될 때, 각 문자를 순차적으로 노드를 따라가며 없으면 새 노드를 추가합니다.
특정 문자열의 끝을 나타내기 위해 노드에 종료 표시(flag)를 할 수 있습니다.
트라이는 일반적으로 단어들을 사전의 형태로 생성합니다.
class TrieNode:
def __init__(self):
# 각 노드는 자식 노드들을 담는 딕셔너리를 가집니다.
self.children = {}
# 이 노드가 어떤 단어의 끝인지를 나타내는 플래그
self.is_end_of_word = False
class Trie:
def __init__(self):
# 트라이의 루트 노드는 빈 노드입니다.
self.root = TrieNode()
트라이는 삽입(Insertion), 검색(Search), 접두사 검색 등 주요 연산을 구현 가능합니다.
삽입
주어진 문자열을 하나씩 처리하여 트리에 삽입합니다. 그리고 각 문자는 트리에서 해당하는 자식 노드로 연결되며, 없을 경우 새로 추가합니다. is_end_of_word 플래그는 True로 설정합니다.
def insert(self, word):
# 루트부터 시작
node = self.root
for char in word:
# 현재 문자가 자식 노드에 없으면 추가
if char not in node.children:
node.children[char] = TrieNode()
# 다음 노드로 이동
node = node.children[char]
# 단어의 마지막 노드에 도달하면 플래그 설정
node.is_end_of_word = True
검색
트라이에서 특정 문자열이 존재하는지 확인합니다. 문자를 하나씩 따라가면서 마지막 문자가 is_end_of_word 플래그를 가지고 있는지 탐색하고, 끝까지 도달하면 성공, 그렇지 않으면 실패합니다.
def search(self, word):
# 루트부터 시작
node = self.root
for char in word:
# 자식 노드에 현재 문자가 없으면 단어가 존재하지 않음
if char not in node.children:
return False
# 다음 노드로 이동
node = node.children[char]
# 마지막 문자까지 도달했으며, 그 노드가 단어의 끝이어야 함
return node.is_end_of_word
접두사 검색
입력한 접두사(prefix)가 트라이에 존재하는지 확인합니다. 단어 전체가 아닌 접두사만 확인하므로 is_end_of_word를 확인하지 않습니다.
def starts_with(self, prefix):
# 접두사가 트라이에 존재하는지 확인하는 함수
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
# 접두사로 끝나는 부분까지 도달했다면 True 반환
return True
삭제
삭제 과정은 단어가 완전히 일치할 때에만 실행됩니다. 재귀적으로 각 문자를 따라가면서 자식 노드가 있는지, 다를 단어의 일부가 아닌지를 판단하여 노드를 삭제합니다.
_delete 함수는 내부적으로 재귀를 사용하여 단어의 끝에서부터 시작해 트리를 따라 올라가면서 노드를 삭제합니다. 단어가 끝난 지점에서 is_end_of_word를 False로 설정합니다. 그 후 해당 노드가 자식 노드를 가지고 있지 않으면 노드를 삭제하고, 그렇지 않으면 노드를 유지합니다.
def delete(self, word):
def _delete(node, word, depth):
# 기저 사례: 단어의 모든 문자를 확인한 경우
if depth == len(word):
# 단어가 존재하는지 확인
if not node.is_end_of_word:
return False # 단어가 존재하지 않음
# 단어의 끝에서 플래그를 해제
node.is_end_of_word = False
# 자식 노드가 없으면 True를 반환해서 삭제 가능
return len(node.children) == 0
char = word[depth]
if char not in node.children:
return False # 단어가 트라이에 없으므로 삭제 불가
# 재귀적으로 자식 노드로 이동
can_delete_child = _delete(node.children[char], word, depth + 1)
# 자식 노드를 삭제할 수 있다면, 삭제
if can_delete_child:
del node.children[char]
# 이 노드가 다른 단어의 일부가 아니면 True 반환
return len(node.children) == 0 and not node.is_end_of_word
return False
# 루트에서 삭제 시작
_delete(self.root, word, 0)
최종 코드
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def starts_with(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
def delete(self, word):
def _delete(node, word, depth):
if depth == len(word):
if not node.is_end_of_word:
return False
node.is_end_of_word = False
return len(node.children) == 0
char = word[depth]
if char not in node.children:
return False
can_delete_child = _delete(node.children[char], word, depth + 1)
if can_delete_child:
del node.children[char]
return len(node.children) == 0 and not node.is_end_of_word
return False
_delete(self.root, word, 0)
torch.utils.data.Dataset은 데이터셋을 정의하는 기본 클래스입니다. 데이터를 메모리에서 가져오는 방법을 정의하며, 개발자가 자체적으로 데이터셋을 만드는데 사용됩니다. Dataset의 중요한 메서드는 __len__, __getitem__ 입니다. __len__은 데이터셋의 크기를 반환하고, __getitem__ 주어진 인덱스에 해당하는 데이터를 학습에 적합한 형태로 변환할 수 있습니다.
from torch.utils.data import Dataset
class MyDataset(Dataset):
def __init__(self, data):
self.data = data
def __len__(self):
return len(self.data)
def __getitem__(self, idx):
return self.data[idx]
1.2. DataLoader
Pytorch로 딥러닝 학습을 진행하면, torch.utils.data.DataLoader라는 것을 많이 사용하게 됩니다. DataLoader는 데이터셋에서 데이터를 배치 단위로 로드하는 역할을 수행합니다. 이를 통해 모델이 배치 단위로 학습을 진행하고, 별도로 구현된 코드를 통해 메모리 사용을 최적화하고 학습 속도를 높여줄 수 있습니다.
DataLoader에는 다음과 같은 주요 세팅 값을 지정해서 사용할 수 있습니다.
batch_size : 배치당 얼마나 많은 데이터 샘플을 가져갈지 결정
shuffle : 데이터를 로드할 때마다 순서를 무작위로 섞을지를 결정
num_workers : 데이터 로드를 위해 얼마나 많은 병렬처리를 위한 서브프로세서를 사용할지 결정
이렇듯 원래라면 한줄씩 코드를 구현하는 노력이 필요하겠지만, 학습 코드에서 제외하고 별도의 Class를 통해 가독성을 높일 수 있기 때문에 (심지어 직접 구현한 것보다 더 효율적일 수 있기 때문에) 자주 활용됩니다.
2. DataLoader 오류
2.1. DataLoader 작동
Dataset 자체는 이터레이터가 아니므로, next()를 사용할 수 없습니다. 하지만 __getitem__을 통해 인덱스를 통해 데이터를 반환하는 방식이 동작할 수 있습니다. DataLoader는 __iter__와 __next__ 메서드를 구현해 이터레이터로 동작합니다. DataLoader는 인덱스 - 이미지(데이터)로 반환하고 있는 Dataset을 받아서 사용하고 있습니다. 그렇기 때문에 아래와 같은 코드가 가능합니다.
for images in tqdm(data_loader):
# 정상적인 이미지 처리
images = images.to(device)
predictions = model(images)
하지만, 이터레이터 특성상 중간에 데이터가 빌 경우 문제가 발생할 수 있습니다.
2.2. DataLoader 오류 해결
DataLoader를 잘 사용하던 중 아래와 같은 오류가 나왔습니다.
error: OpenCV(4.9.0) /io/opencv/modules/imgproc/src/color.cpp:196: error: (-215:Assertion failed) !_src.empty() in function 'cvtColor'
위 오류의 설명은 OpenCV의 cvtColor() 함수가 비어 있는 이미지를 처리하려고 할 때 발생한 문제입니다. 즉, 이미지가 None인 상태에서 cvtColor()를 호출하려고 해서 실패하고 있는 것입니다.
위(2.1)에서 언급하고 있는 DataLoader 작동을 생각해봤을 때 이미지가 없다는 것은 iterable 객체에 중간에 데이터가 비어 있을 것이라 추론할 수 있습니다. 살펴보니 데이터셋으로 가져오고 있는 데이터가 비어있는 것을 발견해 데이터를 추가해서 오류를 해결했습니다.
위상 정렬(Topology sort)은 방향 그래프에서 노드 순서를 찾을 수 있는 알고리즘입니다. 이 정렬은 대학의 선수과목 프레임워크와 같이 수강 순서가 주어지는 경우를 찾는데 활용할 수 있습니다. 작업 스케줄링, 프로세스 순서 결정, 의존성 해결 등 다양한 문제에서 활용할 수 있습니다.
위상 정렬 알고리즘은 크게 DFS와 Kahn의 알고리즘이 존재합니다. DFS는 이전에 공부했기에 여기서는 Kahn의 알고리즘을 살펴보려고 합다.
단계 1 : 진입 차수 계산
진입 차수(in-degree)는 해당 노드로 들어오는 에지 개수를 의미합니다. Kahn 알고리즘에서는 진입 차수를 기반으로 위상 정렬을 수행하기 때문에 진입 차수를 계산해야 합니다. 엣지에 대한 정보를 기반으로 진입 차수를 계산합니다.
# 진입 차수 배열
in_degree = [0] * vertices
# 그래프 인접 리스트 초기화
graph = [[] for _ in range(vertices)]
# 간선 정보 추가 및 진입 차수 계산
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
단계 2 : 진입 차수 0인 노드 삽입
진입 차수가 0인 노드를 큐에 삽입합니다.
# 진입 차수가 0인 노드를 큐에 삽입
queue = deque([i for i in range(vertices) if in_degree[i] == 0])
단계 3 : 위상 정렬 수행
정렬은 아래와 같은 순서로 큐가 빌 때까지 반복합니다.
큐에서 노드를 꺼내 정렬된 리스트에 추가
해당 노드와 연결된 모든 노드의 진입 차수 1 감소
만약 진입 차수가 0이 된 노드는 큐에 삽입
# 위상 정렬 결과를 저장할 리스트
topological_order = []
# 큐가 빌 때까지 반복
while queue:
node = queue.popleft()
topological_order.append(node)
# 해당 노드와 연결된 모든 노드의 진입 차수를 감소시키고
# 진입 차수가 0이 된 노드를 큐에 추가
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
단계 4 : 정렬 확인 (사이클 여부 판별)
단계 3이 마무리되면(즉, 큐가 다 비었을 때) 정렬이 잘 되었는지 확인합니다. 확인하는 방법은 노드의 개수와 위상 정렬 결과의 개수가 일치하게 되면 위상 정렬이 정상적으로 수행되었다는 것을 의미합니다. (반대로, 다르다면 위상 정렬이 불가능한 그래프에 사이클이 존재하는 경우 입니다)
from collections import deque
def topological_sort(vertices, edges):
in_degree = [0] * vertices
graph = [[] for _ in range(vertices)]
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque([i for i in range(vertices) if in_degree[i] == 0])
topological_order = []
while queue:
node = queue.popleft()
topological_order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(topological_order) != vertices:
return []
return topological_order
