이진 탐색(혹은 이분 탐색)은 정렬된 배열에서 특정한 값을 찾는 알고리즘이다. 탐색 범위를 절반씩 줄여가며 빠르게 원하는 값을 찾아낼 수 있어 효율적이다. 이진 탐색의 기본적인 원리는 다음과 같다.
이분 탐색을 위해 오름차순 또는 내림차순으로 정렬된 배열을 준비
탐색 범위의 중간에 있는 값을 찾아서, 찾고자 하는 값과 비교
비교에서 범위를 좁힌다. (오름차순 기준) 3-1. 중간값이 찾고자 하는 값보다 크면 탐색 범위를 왼쪽 절반으로 좁힌다. 3-2. 중간값이 찾고자 하는 값보다 작으면 탐색 범위를 오른쪽 절반으로 좁힌다.
3의 과정을 원하는 값을 찾을 때까지 반복
위 과정을 하나의 함수로 정리하면 다음과 같다.
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # 존재하지 않는 경우
백트래킹(backtracking) 알고리즘은 문제 해결을 위한 모든 가능한 해를 체계적으로 탐색하는 방법입니다. 가능한 해를 구성하면서 조건을 만족하지 않는 경우 그 해를 포기하고 이전 단계로 돌아가는 방식 (backtrack)으로 동작합니다. 이 알고리즘은 DFS(깊이 우선 탐색) 방식으로 트리나 그래프 구조에서 해를 찾아가며 불필요한 탐색을 줄여줍니다.
알고리즘 구조
백트래킹 알고리즘은 깊이 우선 탐색(DFS) 방식으로 동작하며, 재귀적으로 호출됩니다. 조건에 부합하지 않은 선택에 대해서는 가지치기(pruning)를 통해 더 이상 탐색하지 않습니다.
종료 조건 확인
먼저, 현재 상태가 문제의 정답이라면 저장하고 종료합니다. 재귀적으로 호출되기에 종료 조건을 확인해서 종료해야 하는 경우 함수 동작을 멈추도록 합니다. 이를 의사코드로 나타내면 다음과 같습니다.
def backtrack(현재_상태):
if 정답인지(현재_상태): # 종료 조건
해답_저장(현재_상태)
return
선택 탐색
종료 조건이 아니라면, 현재 상태에서 선택할 수 있는 모든 경우를 살펴보도록 for문으로 탐색합니다. 백트래킹은 탐색 도중 특정 조건을 만족하는 경우에 대해서만 선택을 시도하고, 탐색이 끝나면 선택을 취소하여 이전 상태로 복구합니다. 파이썬 자료구조에서 리스트에 추가(append)를 통해 선택과 pop을 통해 취소를 구현할 수 있습니다. 기본적인 의사코드는 아래와 같습니다.
for 가능한_선택 in 현재_상태의_모든_선택:
if 유망한_선택(가능한_선택): # 가지치기 조건
선택(가능한_선택)
backtrack(새로운_상태)
선택_취소(가능한_선택) # 원래 상태로 복구
전체 구조
이들을 조합하면 아래와 같은 의사코드 전체를 만들 수 있습니다.
def backtrack(현재_상태):
if 정답인지(현재_상태): # 종료 조건
해답_저장(현재_상태)
return
for 가능한_선택 in 현재_상태의_모든_선택:
if 유망한_선택(가능한_선택): # 가지치기 조건
선택(가능한_선택)
backtrack(새로운_상태)
선택_취소(가능한_선택) # 원래 상태로 복구
백트레킹 예제
아래는 백트래킹 대표 예제 입니다.
조합 생성 문제
주어진 배열에서 길이가 k인 모든 조합을 구하는 문제 입니다.
def generate_combinations(nums, k):
def backtrack(start, combination):
if len(combination) == k: # 종료 조건
result.append(combination[:])
return
for i in range(start, len(nums)):
combination.append(nums[i]) # 선택
backtrack(i + 1, combination) # 다음 선택으로 이동
combination.pop() # 선택 취소
result = []
backtrack(0, [])
return result
# 실행 예시
nums = [1, 2, 3]
k = 2
print(generate_combinations(nums, k)) # 출력: [[1, 2], [1, 3], [2, 3]]
N-Queens 문제
체스판 위에 N개의 퀸을 배치하여 서로 공격하지 않도록 만드는 문제 입니다.
def solve_n_queens(n):
def is_valid(queen_positions, row, col):
# 기존 퀸들과 같은 열 또는 대각선 상에 있는지 확인
for r, c in enumerate(queen_positions):
if c == col or abs(c - col) == abs(r - row): # 같은 열 또는 대각선
return False
return True
def backtrack(queen_positions):
# 종료 조건: 모든 퀸을 배치한 경우
if len(queen_positions) == n:
solutions.append(queen_positions[:]) # 현재 배치를 결과에 저장
return
for col in range(n): # 현재 행에서 모든 열을 탐색
if is_valid(queen_positions, len(queen_positions), col):
queen_positions.append(col) # 선택
backtrack(queen_positions) # 다음 행으로 이동
queen_positions.pop() # 선택 취소 (백트래킹)
solutions = []
backtrack([]) # 초기 상태: 퀸을 아무 곳에도 두지 않음
return solutions
# 실행 예시
n = 4
result = solve_n_queens(n)
print(result) # 출력: [[1, 3, 0, 2], [2, 0, 3, 1]]
동적계획법(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]
이진 트리(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)
위상 정렬(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
