그리디
개념
그리디 알고리즘은 각 단계에서 현재 상태에서 최적으로 보이는 선택을 한다. 이 선택은 지금 당장은 최적이지만, 전체적으로 봤을 때는 항상 최적해를 보장하지 않을 수 있다. 그러나 이러한 선택을 지속적으로 반복하면서 최종적으로는 최적해에 도달할 수 있다.
예시 문제
동전 거스름돈 문제를 생각해보겠다. 동전 거스름돈 문제에서는 가장 적은 수의 동전을 사용하여 거스름돈을 주는 것이 목표다. 그리디 알고리즘을 사용하면 각 단계에서 가장 큰 동전부터 거스름돈을 주는 것이 최적의 선택이 된다.
구현
개념
코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다.
어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다.
예시 문제
백준의 분수찾기 문제를 생각해보겠다. 
다음과 같은 무한히 큰 배열이 있고 이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 한다. X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성해야 한다.
주어진 배열에 규칙을 찾아 문제의 요구사항대로 코드를 구현하면 된다.
DFS
개념
깊이 우선 탐색으로, 그래프나 트리에서 모든 정점을 방문하는 알고리즘이다. DFS는 스택(Stack) 또는 재귀 함수를 통해 구현되고 주로 그래프 탐색, 연결 요소 찾기, 사이클 검사 등에 활용된다.
작동 방식
DFS의 작동 방식은 다음과 같습니다.
- 시작 정점을 방문하고 방문한 정점을 스택에 push한다.
- 스택에서 정점을 pop하여 그 정점의 인접 정점 중 방문하지 않은 정점을 찾는다.
- 방문하지 않은 정점이 있다면 해당 정점을 방문하고 스택에 push합니다. 없다면 스택에서 다음 정점을 pop한다.
- 위의 과정을 스택이 비어있을 때까지 반복한다.
예시 코드
def dfs(graph, start, visited):
# 현재 정점 방문 처리
visited[start] = True
print(start, end=" ")
# 현재 정점과 연결된 인접 정점들을 확인
for neighbor in graph[start]:
if not visited[neighbor]:
dfs(graph, neighbor, visited)
# 그래프 정보
graph = [
[1, 2], # 0번 정점과 연결된 정점들
[0, 3, 4], # 1번 정점과 연결된 정점들
[0, 5], # 2번 정점과 연결된 정점들
[1], # 3번 정점과 연결된 정점들
[1, 6], # 4번 정점과 연결된 정점들
[2], # 5번 정점과 연결된 정점들
[4] # 6번 정점과 연결된 정점들
]
# 방문 여부를 저장하는 배열
visited = [False] * len(graph)
# DFS 호출
dfs(graph, 0, visited)예시 문제
백준의 바이러스 문제를 생각해보겠다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성해야 한다.
이 문제는 주어진 그래프에서 1번 노드로 시작해 깊이 우선 탐색을 하면 간단히 풀 수 있다.
BFS
개념
BFS(Breadth-First Search)는 너비 우선 탐색으로, 그래프나 트리에서 가까운 정점부터 탐색하는 알고리즘이다. BFS는 큐(Queue)를 사용하여 구현되고 주로 최단 경로 탐색, 상태 공간 탐색 등에 활용됩니다.
작동 방식
BFS의 작동 방식은 다음과 같습니다.
- 시작 정점을 큐에 enqueue(삽입)하고 방문한 정점을 표시한다.
- 큐에서 정점을 dequeue(삭제)하고 해당 정점과 인접한 정점들을 확인한다.
- 방문하지 않은 인접 정점들은 큐에 enqueue하고 방문 여부를 표시한다.
- 큐가 빌 때까지 2~3단계를 반복한다.
예시 코드
from collections import deque
def bfs(graph, start, visited):
# 시작 정점을 큐에 삽입하고 방문 처리
queue = deque([start])
visited[start] = True
while queue:
# 큐에서 정점을 추출하고 출력
vertex = queue.popleft()
print(vertex, end=" ")
# 현재 정점과 인접한 정점들을 확인
for neighbor in graph[vertex]:
# 방문하지 않은 정점이면 큐에 삽입하고 방문 처리
if not visited[neighbor]:
queue.append(neighbor)
visited[neighbor] = True
# 그래프 정보
graph = [
[1, 2], # 0번 정점과 연결된 정점들
[0, 3, 4], # 1번 정점과 연결된 정점들
[0, 5], # 2번 정점과 연결된 정점들
[1], # 3번 정점과 연결된 정점들
[1, 6], # 4번 정점과 연결된 정점들
[2], # 5번 정점과 연결된 정점들
[4] # 6번 정점과 연결된 정점들
]
# 방문 여부를 저장하는 배열
visited = [False] * len(graph)
# BFS 호출
bfs(graph, 0, visited)예시 문제
백준의 미로 탐색 문제를 생각해보겠다. 
배열이 위와 같게 표현되어 있다. N, M이 주어지고 (N, M)의 위치로 가는 최소 이동 횟수를 출력해야 한다.
BFS는 탐색할 때 최단 거리를 보장하므로 (1, 1) 위치에서 BFS를 시작하면 간단히 풀 수 있다.
선택 정렬
개념
선택 정렬(Selection Sort)은 배열을 정렬하는 간단한 정렬 알고리즘 중 하나다. 이 알고리즘은 주어진 배열에서 가장 작은(또는 가장 큰) 요소를 선택하여 해당 위치로 이동시키는 과정을 반복하여 배열을 정렬한다.
이 과정을 배열의 크기만큼 반복하면서 정렬을 완료한다. 선택 정렬은 배열의 크기가 N일 때, N-1번의 비교 연산과 최대 N번의 교환 연산을 수행하므로, 시간 복잡도는 O(N^2)다.
작동 방식
- 주어진 배열에서 최솟값(또는 최댓값)을 찾는다.
- 최솟값과 배열의 첫 번째 요소를 교환한다.
- 배열의 첫 번째 요소를 제외하고 나머지 부분에 대해 1~2단계를 반복한다.
예시 코드
def selection_sort(arr):
n = len(arr)
for i in range(n-1):
# 최솟값을 갖는 요소의 인덱스를 저장하는 변수
min_idx = i
# i+1부터 배열의 끝까지 최솟값을 찾음
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# 최솟값을 i번째 요소와 교환
arr[i], arr[min_idx] = arr[min_idx], arr[i]
# 정렬되지 않은 배열
arr = [64, 25, 10, 22, 11]
print("Before sorting:", arr)
# 선택 정렬 수행
selection_sort(arr)
# 정렬된 배열 출력
print("After sorting:", arr)삽입 정렬
개념
삽입 정렬(Insertion Sort)은 배열을 정렬하는 간단한 정렬 알고리즘 중 하나다. 이 알고리즘은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어, 정렬되지 않은 요소를 정렬된 부분에 삽입하는 과정을 반복하여 배열을 정렬한다.
삽입 정렬은 배열의 크기가 N일 때, 최악의 경우(역순으로 정렬되어 있는 경우) N^2번의 비교 및 교환 연산을 수행하므로, 시간 복잡도는 O(N^2)다. 하지만 배열이 이미 정렬되어 있는 경우, 최선의 경우에는 한 번의 비교만 수행하므로 시간 복잡도가 O(N)이 될 수도 있다.
작동 방식
- 주어진 배열을 정렬된 부분(arr[0]부터 arr[i-1])과 정렬되지 않은 부분(arr[i]부터 arr[n-1])으로 나눈다.
- 정렬되지 않은 부분의 첫 번째 요소(arr[i])를 정렬된 부분에 삽입한다.
- arr[i]와 arr[i-1], arr[i-2], ...을 비교하여 삽입할 위치를 찾고, 해당 위치에 arr[i]를 삽입한다.
- 2~3단계를 정렬되지 않은 모든 요소에 대해 반복한다.
예시 코드
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
# key보다 큰 요소들을 한 칸씩 뒤로 이동
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
# key를 삽입
arr[j + 1] = key
# 정렬되지 않은 배열
arr = [64, 25, 10, 22, 11]
print("Before sorting:", arr)
# 삽입 정렬 수행
insertion_sort(arr)
# 정렬된 배열 출력
print("After sorting:", arr)퀵 정렬
개념
퀵 정렬(Quick Sort)은 배열을 정렬하는 빠른 정렬 알고리즘 중 하나다. 이 알고리즘은 분할 정복(Divide and Conquer) 방법을 사용하여 배열을 작은 부분 배열로 분할하고, 각 부분 배열을 정렬한 후 합병하는 과정을 반복하여 배열을 정렬한다.
퀵 정렬의 평균 시간 복잡도는 O(NlogN)다. 하지만 최악의 경우(피벗이 항상 최솟값 또는 최댓값으로 선택되는 경우)에는 시간 복잡도가 O(N^2)가 될 수 있다.
작동 방식
- 배열에서 하나의 요소를 기준으로 선택합니다. 이를 피벗(Pivot)이라 한다.
- 피벗을 기준으로 작은 요소는 피벗의 왼쪽으로, 큰 요소는 피벗의 오른쪽으로 분할한다.
- 분할된 부분 배열에 대해 재귀적으로 위 과정을 반복한다.
- 부분 배열의 크기가 1 이하가 될 때까지 반복하여 정렬을 완료한다.
예시 코드
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + equal + quick_sort(right)
# 정렬되지 않은 배열
arr = [64, 25, 10, 22, 11]
print("Before sorting:", arr)
# 퀵 정렬 수행
sorted_arr = quick_sort(arr)
# 정렬된 배열 출력
print("After sorting:", sorted_arr)계수 정렬
개념
계수 정렬(Counting Sort)은 정수나 정수로 표현할 수 있는 자료에 대해, 각 값이 몇 번 등장하는지 세는 작업을 기반으로 정렬을 수행하는 알고리즘이다. 일반적인 비교 기반의 정렬 알고리즘들과는 다르게, 계수 정렬은 비교를 하지 않고 요소들의 개수를 세어 정렬을 수행한다.
계수 정렬은 모든 요소를 한 번씩만 순회하므로, 시간 복잡도는 O(N)다. 하지만 정수의 범위가 크고 배열의 크기가 클 경우, count 배열과 결과 배열을 저장하기 위한 공간이 많이 필요할 수 있다. 또한, 계수 정렬은 정수나 정수로 표현할 수 있는 자료에 대해서만 사용할 수 있으며, 요소들이 비교 가능한 자료형이 아닐 때는 다른 정렬 알고리즘을 사용해야 한다.
작동 방식
- 정렬할 배열의 최댓값(max_value)을 구한다.
- 길이가 max_value+1인 카운트 배열(count)을 생성하고, 모든 요소를 0으로 초기화한다.
- 정렬할 배열의 모든 요소를 순회하며, 해당 값의 등장 횟수를 count 배열에 기록한다.
- count 배열의 누적 합(cumulative sum)을 계산합니다. 이를 통해 각 값의 정렬된 위치를 알 수 있다.
- 정렬된 배열을 저장할 결과 배열(result)을 생성한다.
- 정렬할 배열을 다시 순회하며, 각 값을 count 배열을 참조하여 정렬된 위치에 배치한다.
- 정렬된 배열을 결과 배열에 저장한다.
예시 코드
def counting_sort(arr):
# 정렬할 배열의 최댓값 구하기
max_value = max(arr)
# 카운트 배열 초기화
count = [0] * (max_value + 1)
# 각 값의 등장 횟수 세기
for num in arr:
count[num] += 1
# 누적 합 계산
for i in range(1, len(count)):
count[i] += count[i - 1]
# 정렬된 배열 저장할 결과 배열
result = [0] * len(arr)
# 정렬된 위치에 값 배치
for num in arr:
result[count[num] - 1] = num
count[num] -= 1
return result
# 정렬되지 않은 배열
arr = [4, 2, 2, 8, 3, 3, 1]
print("Before sorting:", arr)
# 계수 정렬 수행
sorted_arr = counting_sort(arr)
# 정렬된 배열 출력
print("After sorting:", sorted_arr)탐색
선형 탐색
개념
선형 탐색은 리스트나 배열과 같은 데이터 구조에서 처음부터 끝까지 순차적으로 탐색하면서 원하는 값을 찾는 방법이다. 순서대로 하나씩 비교하며 탐색하기 때문에 배열이나 리스트의 크기에 비례하는 시간이 소요된다. 최악의 경우에는 모든 요소를 확인해야 하므로 시간 복잡도는 O(N)이다.
예시 코드
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i # 찾은 경우 인덱스 반환
return -1 # 찾지 못한 경우 -1 반환
# 정렬되지 않은 배열
arr = [5, 3, 8, 4, 2]
target = 8
# 선형 탐색 수행
result = linear_search(arr, target)
if result != -1:
print("Element found at index", result)
else:
print("Element not found")이분 탐색
개념
이진 탐색은 정렬된 배열에서 원하는 값을 찾는 탐색 알고리즘이다. 이진 탐색은 배열의 중간 요소와 비교하여 탐색 범위를 반으로 줄여가면서 값을 찾아간다. 중간 값과 비교하여 찾고자 하는 값이 작으면 왼쪽 부분 배열을, 크면 오른쪽 부분 배열을 탐색한다. 반복적으로 탐색 범위를 반으로 줄여가므로 시간 복잡도는 O(logN)이다. 이진 탐색은 정렬된 배열에서 효율적으로 동작하며, 데이터가 많은 경우에 유용하다.
예시 코드
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 # 찾지 못한 경우 -1 반환
# 정렬된 배열
arr = [2, 4, 6, 8, 10]
target = 8
# 이진 탐색 수행
result = binary_search(arr, target)
if result != -1:
print("Element found at index", result)
else:
print("Element not found")DP
개념
DP(다이나믹 프로그래밍, Dynamic Programming)는 큰 문제를 작은 부분 문제로 나누어 푸는 최적화 기법이다. 동적 계획법이라고도 불리며, 중복되는 부분 문제들을 한 번만 계산하고 이를 이용하여 효율적으로 문제를 해결한다. DP는 최적 부분 구조와 중복되는 부분 문제를 가지는 문제들에 적용할 수 있다.
주요 아이디어
-
최적 부분 구조(Optimal Substructure):
큰 문제의 최적해가 작은 부분 문제의 최적해로 구성되는 성질이다. 큰 문제를 작은 부분 문제로 나눌 수 있으며, 작은 문제의 최적해를 조합하여 전체 문제의 최적해를 구할 수 있다. -
중복되는 부분 문제(Overlapping Subproblems):
작은 부분 문제들이 서로 중복되는 경우를 의미한다. 같은 부분 문제를 반복해서 해결하는 대신 한 번만 계산하고 그 결과를 저장하여 재활용할 수 있다.
알고리즘 단계
-
작은 부분 문제 정의:
큰 문제를 작은 부분 문제로 나누어 정의한다. 작은 부분 문제는 중복되는 구조를 가지며 최적 부분 구조를 따라야 한다. -
작은 부분 문제 해결:
가장 작은 부분 문제부터 시작하여 순차적으로 해결한다. 작은 부분 문제들의 해를 저장하기 위한 자료구조(일반적으로 배열 또는 테이블)를 사용한다. -
작은 부분 문제 결합:
작은 부분 문제들의 해를 결합하여 큰 문제의 해를 구한다. 최적 부분 구조를 활용하여 문제를 해결한다.
다양한 기법들
-
메모이제이션(Memoization):
메모이제이션은 이전에 계산한 결과를 저장하여 중복 계산을 피하는 기법이다. 재귀적인 구조에서 매번 중복되는 호출을 방지하기 위해 결과를 캐싱하여 활용합니다. 일반적으로 배열이나 해시 테이블을 사용하여 결과를 저장한다. -
탑다운(Top-Down) 방식:
탑다운 방식은 재귀적인 구조를 활용하여 문제를 작은 부분 문제로 분할하고, 필요한 부분 문제를 재귀적으로 해결하는 방식이다. 주로 메모이제이션과 함께 사용되며, 큰 문제를 작은 부분 문제로 분할하여 효율적으로 해결한다. -
바텀업(Bottom-Up) 방식:
바텀업 방식은 작은 부분 문제부터 시작하여 순차적으로 해결해 나가는 방식이다. 작은 부분 문제들의 해를 저장하기 위한 배열이나 테이블을 사용하며, 순차적으로 문제를 해결하여 최종적인 결과를 구한다. 일반적으로 반복문을 사용하여 구현한다. -
최적 부분 구조 활용:
최적 부분 구조는 큰 문제의 최적해가 작은 부분 문제의 최적해로 구성되는 성질을 의미한다. DP에서는 작은 부분 문제의 최적해를 조합하여 전체 문제의 최적해를 구한다. 이를 위해 부분 문제 간의 관계를 파악하고, 최적 부분 구조를 활용하여 문제를 해결한다. -
상태 공간 축소:
일부 DP 문제에서는 모든 상태를 저장하지 않고 필요한 상태만 저장하여 공간을 절약할 수 있습니다. 필요한 상태만을 유지하고 이를 활용하여 문제를 효율적으로 해결한다. 예를 들어, 1차원 배열 대신 2개의 변수로 상태를 나타내는 방식 등이 있다.
