무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리이다.

대표적인 트리 문제

보통 최소 신장 트리(MST) 문제는 아래 형태로 많이 나온다.

1. 모든 정점을 최소 비용으로 연결
   • 도시들을 도로로 연결 문제
   • 컴퓨터들을 네트워크로 연결 문제
2. 섬 연결
   • 여러 섬을 다리로 연결하면서 건설 비용 최소화 문제
3. 통신망 / 전기망 구축
   • 모든 지역을 연결하면서 케이블 설치 비용 최소화 문제
4. 기존 연결망에서 최소 비용 구하기
   • 여러 연결 방법 중 전체를 연결할 수 있는 최소 비용 선택 문제

2. Prim 알고리즘

하나의 정점에 연결된 간선들 중에서, 하나씩 선택하면서 MST를 만들어 가는 방식이다.

1. 임의 정점 하나를 선택해서 시작한다.
2. 선택한 정점과 인접하는 정점들 중의 최소비용의 간선이 존재하는 정점을 선택한다.
3. 모든 정점이 선택될 때까지 앞의 과정을 반복한다.

우선 순위 큐

Prim 알고리즘에서는 현재 선택 가능한 간선 중 가장 가중치가 작은 간선을 계속 찾아야 한다.

그래서 최소값을 빠르게 꺼낼 수 있는 우선순위 큐(Priority Queue)를 사용한다.

파이썬에서는 heapq를 이용한다.

최소 힙

import heapq

arr = []

heapq.heappush(arr, 13)
heapq.heappush(arr, 5)
heapq.heappush(arr, 17)
heapq.heappush(arr, 9)

print(arr)

for i in range(len(arr)):
    print(heapq.heappop(arr))

print(arr)

출력

최대 힙

import heapq
arr = [3, 234, 23, 12, 31]
heap = []
for i in range(len(arr)):
        # 음수로 바꿔서 넣으면 최대 힙처럼 사용
        # 음수 중에서는 가장 작은 값이 원래 값으로 보면 가장 큰 값
    heapq.heappush(heap, -arr[i])

for i in range(len(arr)):
    print(heapq.heappop(heap)*-1)

출력

Prim → 최소 비용 간선을 반복해서 선택 → 우선순위 큐 사용의 흐름으로 연결된다.

3. Kruskal 알고리즘

간선을 하나씩 선택해서 MST를 찾는 알고리즘이다.

1. 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬한다.
2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다.
   • 사이클이 존재하면 다음으로 가중치가 낮은 간선을 선택한다.
3. n - 1 개의 간선이 선택될 때까지 2를 반복한다.

# (가중치, 시작 정점, 끝 정점)
edges = [
    (1, 1, 2),
    (2, 1, 3),
    (3, 2, 3),
    (4, 2, 4),
    (5, 3, 4)
]

edges.sort()

parent = [0, 1, 2, 3, 4]

def find_set(x):
    if x != parent[x]:
        parent[x] = find_set(parent[x])

    return parent[x]

def union(x, y):
    x = find_set(x)
    y = find_set(y)

    if x != y:
        parent[y] = x

total = 0

for cost, x, y in edges:
    # 서로 다른 집합이면 사이클이 발생하지 않음
    if find_set(x) != find_set(y):
        union(x, y)
        total += cost

        print(x, y, cost)

print("최소 비용:", total)

출력

가중치가 작은 간선부터 확인하면서 사이클이 없는 간선만 선택한다.

4. Dijkstra 알고리즘

최단 경로

가중치가 있는 그래프에서 두 정점 사이의 경로 중 가중치 합이 최소인 경로이다.

Dijkstra 알고리즘

시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 알고리즘이다.

1. 시작 정점(s)에서 끝 정점(t)까지의 최단 경로에 정점 x가 존재한다.
2. 최단 경로는 s에서 x까지의 최단 경로와 x에서 t까지의 최단 경로로 구성된다.
3. 탐욕 기법을 사용한 알고리즘으로 MST의 Prim 알고리즘과 유사하다.

import heapq

# 그래프 정보
# graph[정점] = [(가중치, 연결된 정점), ...]
graph = [
    [],
    [(2, 2), (5, 3)],   # 1번 정점 -> 2번(비용 2), 3번(비용 5)
    [(1, 3), (4, 4)],   # 2번 정점 -> 3번(비용 1), 4번(비용 4)
    [(1, 4)],           # 3번 정점 -> 4번(비용 1)
    []
]

# 무한대 값
INF = int(1e9)

# 각 정점까지의 최단 거리 저장
# 처음에는 아직 최단 거리를 모르기 때문에 무한대로 초기화
distance = [INF] * 5

# 우선순위 큐
pq = []

# 시작 정점은 1번
# 자기 자신까지의 거리는 0
distance[1] = 0

# (거리, 정점) 형태로 우선순위 큐에 저장
heapq.heappush(pq, (0, 1))

while pq:
    # 현재 가장 거리가 짧은 정점을 꺼냄
    dist, node = heapq.heappop(pq)

    # 이미 더 짧은 경로가 저장되어 있다면 무시
    if distance[node] < dist:
        continue

    # 현재 정점과 연결된 정점 확인
    for cost, next_node in graph[node]:

        # 현재 정점을 거쳐 다음 정점으로 가는 거리
        new_dist = dist + cost

        # 기존에 저장된 거리보다 더 짧다면 갱신
        if new_dist < distance[next_node]:
            distance[next_node] = new_dist

            # 갱신된 거리와 정점을 우선순위 큐에 추가
            heapq.heappush(pq, (new_dist, next_node))

# 1번 정점에서 각 정점까지의 최단 거리 출력
for i in range(1, 5):
    print(i, distance[i])

출력

시작 정점이 1이므로:

1 → 1 : 0
1 → 2 : 2
1 → 3 : 3
1 → 4 : 4

처럼 1번 정점에서 각 정점까지의 최소 비용이 출력된다.

정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료 구조이다.

그래프 유형

1. 무향 (무방향) 그래프
2. 유향 (방향) 그래프
3. 가중치 그래프
4. 사이클 없는 방향 그래프

그래프 표현

• 간선의 정보를 저장하는 방식, 메모리나 성능을 고려해서 결정한다.
• 인접 행렬
  • N x N 크기의 2차원 배열을 이용해서 간선 정보를 저장한다.

graph = [
    [0, 1, 1],
    [1, 0, 0],
    [1, 0, 0]
]

• 인접 리스트
  • 각 정점마다 해당 정점과 인접한 정점 정보를 저장한다.

graph = [
    [1, 2],
    [0],
    [0]
]

• 간선의 배열
  • 간선을 배열에 연속적으로 저장한다.

edges = [
    (0, 1),
    (0, 2)
]

2. DFS

한 경로를 끝까지 탐색한 뒤, 더 이상 갈 곳이 없으면 이전 갈림길로 돌아가 탐색을 이어간다.

재귀 또는 스택을 이용한다.

재귀 방식

def dfs(v):
    visited[v] = True
    print(v, end=' ')

    for next_node in graph[v]:
        if not visited[next_node]:
            dfs(next_node)

• 현재 정점을 방문 처리한다.
• 연결된 정점 중 방문하지 않은 정점으로 계속 들어간다.

스택 방식

def dfs(start):
    stack = [start]
    visited[start] = True

    while stack:
        v = stack.pop()
        print(v, end=' ')

        for next_node in graph[v]:
            if not visited[next_node]:
                stack.append(next_node)
                visited[next_node] = True

3. BFS

시작 정점에서 가까운 정점부터 차례대로 탐색한다.

큐(Queue)를 이용한다.

from collections import deque

def bfs(start):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        print(v, end=' ')

        for next_node in graph[v]:
            if not visited[next_node]:
                queue.append(next_node)
                visited[next_node] = True

• 시작 정점을 큐에 넣는다.
• 큐에서 하나씩 꺼내면서 인접 정점을 확인한다.
• 방문하지 않은 정점은 다시 큐에 넣는다.

DFS / BFS 차이

4. Union-Find

서로소 집합(Disjoint Set)을 관리하기 위한 자료구조이다.

Make-Set, Find-Set, Union 연산을 사용한다.

Make-Set

각 원소가 자기 자신을 대표자로 가지도록 만든다.

N = 5

parent = [0] * (N + 1)

for i in range(1, N + 1):
    parent[i] = i

Find-Set

해당 원소가 속한 집합의 대표자를 찾는다.

def find_set(x):
    if x != parent[x]:
        parent[x] = find_set(parent[x])

    return parent[x]

parent[x] = find_set(parent[x])를 통해 대표자를 직접 가리키도록 변경하는 것을 경로 압축(Path Compression)이라고 한다.

Union

두 원소가 속한 집합을 하나로 합친다.

def union(x, y):
    root_x = find_set(x)
    root_y = find_set(y)

    if root_x != root_y:
        parent[root_y] = root_x

사용 예시는 다음과 같다.

union(1, 2)
union(2, 3)

print(find_set(1))
print(find_set(2))
print(find_set(3))

1, 2, 3은 같은 대표자를 가지게 된다.

5. Union-Find 최적화

트리가 한쪽으로 길어지면 Find-Set 과정이 오래 걸릴 수 있다.

Rank

높이가 낮은 트리를 높은 트리 아래에 붙인다.

def union(x, y):
    root_x = find_set(x)
    root_y = find_set(y)

    if rank[root_x] > rank[root_y]:
        parent[root_y] = root_x

    else:
        parent[root_x] = root_y

        if rank[root_x] == rank[root_y]:
            rank[root_y] += 1

1. 백트래킹이란?

백트래킹은 여러 가지 선택지가 존재하는 상황에서 하나를 선택하고, 그 선택을 기반으로 다음 선택을 이어가며 정답을 찾는 방식이다.

탐색을 진행하다가 하나의 경로가 끝나면 이전 상태로 돌아가 다른 선택지를 다시 탐색한다.

즉, 백트래킹의 핵심은 다음과 같다.

선택 → 탐색 → 선택 취소 → 다른 선택

예를 들어 [1, 2, 3]을 이용해 순열을 만든다고 생각하면,

1 선택
 └─ 2 선택
     └─ 3 선택

탐색 완료
↓
2 선택 취소
↓
3 선택

처럼 이전 선택을 취소하고 다른 경우를 다시 탐색한다.

2. 백트래킹과 DFS의 차이

DFS(Depth First Search)는 한 방향으로 최대한 깊게 들어가며 탐색하는 탐색 방식이다.

백트래킹은 DFS를 이용해 하나의 선택을 탐색한 뒤, 탐색이 끝나면 이전 상태로 되돌아가 다른 선택을 시도하는 문제 해결 방식이다.

DFS
= 한 방향으로 깊게 탐색

백트래킹
= 선택 → 깊게 탐색 → 선택 취소 → 다른 선택

DFS 역시 탐색이 끝나면 이전 노드로 돌아온다.

하지만 백트래킹에서는 단순히 탐색 위치만 돌아가는 것이 아니라, 탐색 전에 변경했던 상태까지 원상복구한다는 점이 중요하다.

3. 가지치기(Pruning)

백트래킹 과정에서 현재 선택이 정답으로 이어질 가능성이 없다고 판단되면, 해당 경로를 더 이상 탐색하지 않을 수 있다.

이것을 가지치기(Pruning)라고 한다.

현재 경로
   ↓
정답 가능성 없음
   ↓
더 이상 탐색하지 않음

가지치기를 사용하면 모든 경우를 끝까지 확인하지 않아도 되기 때문에 탐색 횟수를 크게 줄일 수 있다.

백트래킹과 가지치기는 같은 개념은 아니다.

백트래킹
= 탐색 후 이전 상태로 돌아가는 것

가지치기
= 가능성이 없는 경로를 탐색하지 않는 것

4. 백트래킹 알고리즘 절차

백트래킹은 일반적으로 다음과 같은 과정으로 진행된다.

1. 상태 공간 트리를 DFS 방식으로 탐색한다.
2. 현재 선택이 유망한지 확인한다.
3. 유망하다면 다음 단계로 탐색한다.
4. 유망하지 않다면 해당 경로의 탐색을 중단한다.
5. 탐색이 끝나면 이전 상태로 돌아가 다른 선택지를 탐색한다.

여기서 유망하다는 것은 현재 선택을 계속 이어갔을 때 정답이 될 가능성이 있다는 의미이다.

5. 대표 문제 - N-Queen

N-Queen은 N × N 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제이다.

퀸은 다음 방향으로 이동할 수 있다.

• 같은 열
• 왼쪽 대각선
• 오른쪽 대각선

따라서 새로운 퀸을 놓을 때 이 세 방향에 다른 퀸이 존재하는지 검사해야 한다.

8-Queen

N = 8인 경우 가능한 배치의 개수는 92개이다.

# 입력 8을 줌
n = int(input())

vertical = [0] * n
seven = [0] * (2 * n)
five = [0] * (2 * n)

count = 0

def backtracking(level):
    global count

    if level == n:
        count += 1
        return

    for j in range(n):

        # 같은 열 확인
        if vertical[j] == 1:
            continue

        # 대각선 확인
        if seven[level + j] == 1 or five[level - j + n] == 1:
            continue

        vertical[j] = 1
        seven[level + j] = 1
        five[level - j + n] = 1

        backtracking(level + 1)

        # 이전 상태로 복구
        vertical[j] = 0
        seven[level + j] = 0
        five[level - j + n] = 0

backtracking(0)

print(count)

출력

6. 코드에서 각 개념 구분하기

N-Queen 코드에는 완전탐색, DFS, 가지치기, 백트래킹이 모두 들어 있다.

완전탐색

for j in range(n):

현재 행에서 퀸을 놓을 수 있는 모든 열을 하나씩 확인한다.

즉, 가능한 선택지를 전부 시도한다.

DFS

backtracking(level + 1)

현재 행에 퀸을 놓은 뒤 다음 행으로 넘어가 깊게 탐색한다.

가지치기

if vertical[j] == 1:
    continue

if seven[level + j] == 1 or five[level - j + n] == 1:
    continue

이미 다른 퀸의 공격 범위에 있는 위치라면 해당 경우는 정답이 될 수 없으므로 탐색하지 않는다.

백트래킹

vertical[j] = 0
seven[level + j] = 0
five[level - j + n] = 0

현재 선택에 대한 탐색이 끝나면 퀸을 놓기 전 상태로 원상복구한다.

이후 반복문에서 다음 위치를 선택해 다시 탐색한다.

이번에는 완전탐색에서 자주 사용하는 부분집합, 조합과 현재 상황에서 가장 좋은 선택을 하는 Greedy 알고리즘을 정리한다.

1. 부분집합

• 주어진 집합에서 일부 원소를 선택하여 만든 집합이다.
• 아무것도 선택하지 않은 공집합도 포함한다.
• 원소가 N개라면 부분집합의 개수는 2^N개이다.

예를 들어 {A, B, C}의 부분집합은 다음과 같다.

{}
{A}
{B}
{C}
{A, B}
{A, C}
{B, C}
{A, B, C}

재귀를 이용한 부분집합

각 원소마다 선택하거나 선택하지 않는 2가지 경우를 만든다.

Branch = 2
Level = 원소의 개수

arr = ['O', 'X']
path = []

def run(level):
    if level == 3:
        print(path)
        return

    for i in range(2):
        path.append(arr[i])
        run(level + 1)
        path.pop()

run(0)

O는 선택, X는 선택하지 않는 경우이다.

Binary Counting

부분집합은 이진수를 이용해서도 표현할 수 있다.

000
001
010
011
100
101
110
111

• 0 : 선택하지 않음
• 1 : 선택

예를 들어 101이라면 {A, C}가 선택된 것이다.

arr = ['A', 'B', 'C']
n = len(arr)

def get_sub(target):
    for i in range(n):
        if target & 0x1:
            print(arr[i], end=' ')
        target >>= 1

target & 0x1로 마지막 비트가 1인지 확인하고,
target >>= 1로 다음 비트를 확인한다.

2. 조합

• 서로 다른 N개의 원소 중 R개를 순서 없이 선택한다.
• 순열과 다르게 선택한 순서는 고려하지 않는다.

예를 들어 A, B, C 중 2개를 선택하면

AB
AC
BC

가 된다.

AB와 BA는 같은 경우이다.

순열 : 순서가 중요하다.
조합 : 순서가 중요하지 않다.

조합 구현

조합에서는 이미 확인한 원소를 다시 확인하지 않기 위해 start를 사용한다.

arr = ['A', 'B', 'C', 'D', 'E']
path = []

def recur(cnt, start):
    if cnt == 3:
        print(*path)
        return

    for i in range(start, len(arr)):
        path.append(arr[i])
        recur(cnt + 1, i + 1)
        path.pop()

recur(0, 0)

핵심은 다음 재귀에서 i + 1부터 확인하는 것이다.

A 선택 → B, C, D, E 확인
B 선택 → C, D, E 확인
C 선택 → D, E 확인

이렇게 하면 AB를 선택한 뒤 BA를 다시 만드는 중복을 막을 수 있다.

3. 탐욕 알고리즘 Greedy

• 현재 상황에서 가장 좋아 보이는 선택을 반복하는 알고리즘이다.
• 모든 경우를 확인하는 완전탐색과 달리 하나의 기준을 정해서 선택한다.
• 현재의 최선이 전체의 최선이 되는 문제에서 사용할 수 있다.

동전 문제

동전이 다음과 같이 있다고 하자.

500원
100원
50원
10원

1730원을 최소 개수의 동전으로 거슬러 준다면 큰 동전부터 사용한다.

500원 × 3 = 1500원
100원 × 2 = 200원
10원 × 3 = 30원

총 8개

coin_list = [500, 100, 50, 10]
target = 1730
cnt = 0

for coin in coin_list:
    possible_cnt = target // coin
    cnt += possible_cnt
    target -= coin * possible_cnt

print(cnt)

target // coin으로 현재 동전을 최대 몇 개 사용할 수 있는지 구한다.

Greedy가 항상 정답은 아니다

동전이 다음과 같이 있다고 하자.

70원
50원
10원

100원을 만들어야 할 때 큰 동전부터 선택하면

70 + 10 + 10 + 10 = 4개

가 필요하다.

하지만 실제 최소 동전은

50 + 50 = 2개

이다.

따라서 Greedy는 단순히 가장 큰 값이나 가장 작은 값을 선택하는 것이 아니라,
문제에 맞는 선택 기준이 성립하는지 확인하는 것이 중요하다.

4. Greedy 대표 문제

Knapsack

정해진 무게 안에서 최대 가치를 만드는 문제이다.

예를 들어 최대 30kg까지 담을 수 있고 다음 물건들이 있다고 하자.

일반적인 0-1 Knapsack에서는 물건을 통째로 넣거나 넣지 않아야 한다.

따라서 단순히 가치가 높은 물건이나 kg당 가치가 높은 물건부터 선택한다고 해서
항상 정답이 되는 것은 아니다.

Fractional Knapsack

Fractional Knapsack은 물건을 필요한 만큼 잘라서 넣을 수 있는 문제이다.

이 경우에는

가치 / 무게

즉, 단위 무게당 가치가 높은 물건부터 선택하는 Greedy 방식을 사용할 수 있다.

0-1 Knapsack
→ 물건을 나눌 수 없음

Fractional Knapsack
→ 물건을 나눌 수 있음

활동 선택 문제

여러 개의 회의가 있을 때 서로 겹치지 않으면서
최대한 많은 회의를 선택하는 문제이다.

이 문제에서는

종료 시간이 가장 빠른 회의부터 선택한다.

진행 과정은 다음과 같다.

1. 종료 시간이 빠른 순서로 정렬한다.
2. 가장 빨리 끝나는 회의를 선택한다.
3. 선택한 회의가 끝난 뒤 시작할 수 있는 회의를 찾는다.
4. 그중 다시 가장 빨리 끝나는 회의를 선택한다.
5. 반복한다.

정리

부분집합
→ 각 원소를 선택 / 선택하지 않음
→ 경우의 수는 2^N

Binary Counting
→ 0과 1로 부분집합 표현

조합
→ 순서 없이 선택
→ start를 이용해서 중복 방지

Greedy
→ 현재 가장 좋아 보이는 선택을 반복
→ 선택 기준이 전체 최적해로 이어지는지 확인

0-1 Knapsack
→ 물건을 나눌 수 없음

Fractional Knapsack
→ 물건을 나눌 수 있음
→ 단위 무게당 가치가 높은 순서로 선택

활동 선택 문제
→ 종료 시간이 가장 빠른 활동부터 선택

• 반복과 재귀는 유사한 작업을 수행할 수 있다.
• 반복은 수행하는 작업이 완료될 때 까지 계속 반복한다.
  • 루프 for , while
• 재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법이다.
  • 하나의 큰 문제를 해결할 수 있는 더 작은 문제로 쪼개고 결과들을 결합한다.

재귀함수 예시

# 0 1 2 3 2 1 0
def recursive(level):
      # 현재 level 출력
    print(level, end=" ")
    # level이 3이면 더 이상 재귀 호출하지 않고 종료
    if level == 3:
        return
        # level이 3이 될때까지 +1
    recursive(level + 1)
    print(level, end=" ")
# recursive(0)으로 재귀 시작
recursive(0)  

출력

위 처럼 함수 내부에서 자기 자신을 계속 호출시키는 것이 재귀함수 이다.

Branch, Level을 먼저 파악하고, 이후 코드를 직접 구현한다.

2. 순열

서로 다른 N개에서, R개를 중복 없이, 순서를 고려하여 나열하는 것 이다.

ex) 0, 1, 2로 구성된 3장의 카드 중 2장을 뽑아 순열을 나열한다. → 모든 경우의 수

중복 순열 구현 원리

서로 다른 N개에서 R개를 중복을 허용하고, 순서를 고려하여 나열하는 것 이다.

1. 재귀호출을 할 때마다, 이동 경로를 흔적으로 남긴다.
2. 가장 마지막 레벨에 도착했을 때, 이동 경로를 출력한다.

중복 순열 구현

1. 먼저 Path 라는 전역 리스트를 준비한다.
2. 그리고 Level2, Branch3 으로 동작하는 재귀 코드를 구현한다.
3. 재귀호출을 하기 직전에 이동할 곳의 위치를 path 리스트에 기록한다.
4. 재귀호출이 모두 끝나 바닥에 도착했으면 출력하는 코드를 작성한다.
5. 함수가 리턴 되고, 함수가 즉시 종료되었을때, 이후 path 에 적은 마지막 기록이 삭제되어야 한다.

path = []

def perm(x):
    # x가 2가 되면 더 이상 재귀 호출하지 않고 종료
    if x == 2:
        print(path)
        return
    # i가 0, 1, 2 순서로 반복
    for i in range(3):
        # 현재 선택한 i를 path에 추가
        path.append(i)
        # x를 1 증가시켜 자기 자신을 다시 호출
        perm(x + 1)
        # 재귀가 끝나고 돌아왔으면 방금 선택했던 숫자를 제거해서 이전 상태로 복구
        path.pop()

perm(0)

[]
 ↓ append(0)
[0]
 ↓ append(0)
[0, 0] → 출력
 ↓ pop()
[0]
 ↓ append(1)
[0, 1] → 출력
 ↓ pop()
[0]
 ↓ append(2)
[0, 2] → 출력

출력

3. 완전 탐색

모든 가능한 경우를 시도해서 정답을 찾아내는 알고리즘이다.

완전 탐색의 기본 구조

1. 현재 Level에서 선택할 수 있는 모든 경우를 확인한다.
2. 하나를 선택한 뒤 dfs(level + 1, ...)로 다음 Level로 이동한다.
3. 마지막 Level에 도착하면 원하는 조건을 만족하는지 확인한다.
4. 조건을 확인한 뒤 return하여 이전 Level로 돌아간다.
5. 아직 확인하지 않은 다른 경우를 다시 탐색한다.

현재 코드는 DFS를 이용하여 모든 경우의 수를 탐색하고, 불필요한 경우는 가지치기하는 방식이다.

arr = [3, 4, 7, 1, 6]
count = 0

def dfs(level, sum_value):
    global count

    # 합이 10을 넘으면 더 볼 필요가 없으므로 가지치기
    if sum_value > 10:
        return

    # 숫자 3개를 선택한 상태
    if level == 3:
        # 합이 정확히 10이면 경우의 수 증가
        if sum_value == 10:
            count += 1
        return

    # arr의 5개 원소를 각각 선택해봄
    for i in range(5):
        dfs(level + 1, sum_value + arr[i])

dfs(0, 0)
print(count)

dfs(0, 0)
 ↓ 숫자 1개 선택
dfs(1, 지금까지의 합)
 ↓ 숫자 1개 더 선택
dfs(2, 지금까지의 합)
 ↓ 숫자 1개 더 선택
dfs(3, 세 숫자의 합)
 → 합이 10인지 검사
 → return
 ↑ 이전 dfs(2)로 돌아감
 → for문의 다음 숫자를 선택

출력

그래프를 탐색하는 방법에는 두가지가 있다. 너비 우선탐색과 깊이 우선 탐색이 있다.

너비 우선 탐색 (BFS, Breadth First Search)

탐색 시작 정점에 인접한 정점들을 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식이다.

BFS 탐색 순서

BFS 알고리즘

• 입력 파라미터: 그래프 G와 탐색 시작점 v

def bfs(G, v, n):             # 그래프 G, 탐색 시작점 v
    visited = [0] * (n + 1)     # n: 정점의 갯수
    queue = []                  # 큐 생성
    queue.append(v)             # 시작점 v를 큐에 삽입

    while queue:                # 큐가 비어있지 않은 경우
        t = queue.pop(0)          # 큐의 첫 번째 원소 반환
        visited(t)                # 정점 t에서 할 일

            for i in G[t]:          # t와 연결된 모든 정점에 대해
                if not visited[i]:    # 방문하지 않은 곳이면
                    queue.append(i)     # 큐에 넣는다
                    visited[i] = visited[t] + 1 # n으로부터 1만큼 이동

즉 아래와 같이 요구사항에 맞게 코드를 짜자

시작점 큐에 넣기
→ 시작점 방문 처리
→ 큐에서 하나 꺼내기
→ 연결된 곳 확인
→ 방문 안 했으면 큐에 넣기 + 방문 처리
→ 큐가 빌 때까지 반복

1. 비선형 자료구조이다.
2. 원소들 간에 1:N 관계를 가지는 자료구조이다.
3. 원소들 간에 계층관계를 가지는 계층형 자료구조이다.
4. 상위 원소에서 하위원소로 내려가면서 확장되는 트리모양의 구조이다.

용어정리

1. 노드 (node): 트리의 원소
2. 간선 (edge): 노드를 연결하는 선, 부모 노드와 자식 노드를 연결한다.
3. 루트 노드 (root node): 트리의 시작 노드
4. 형제 노드 (sibling node) : 같은 부모 노드의 자식들
5. 조상 노드: 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
6. 서브 트리 (subtree): 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
7. 자손 노드: 서브 트리에 있는 하위 레벨의 노드들
8. 노드의 차수 : 노드에 연결된 자식 노드의 수
9. 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
10. 단말 노드 (리프 노드) : 차수가 0인 노드, 자식 노드가 없는 노드
11. 노드의 높이 : 루트에서 노드에 이르는 간선의 수, 노드의 레벨
12. 트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값, 최대 레벨

2. 이진 트리

모든 노드들이 2개 이내의 서브 트리를 갖는 특별한 형태의 트리이며, 각 노드가 자식 노드를 최대한 2개까지만 가질 수 있다.

자식은 보통 왼쪽 자식 / 오른쪽 자식으로 구분한다.

이진 트리의 특성

1. 한 노드가 가질 수 있는 자식은 최대 2개이다.
2. 아래 레벨로 내려갈수록 들어갈 수 있는 노드의 수가 많아진다.
3. 한쪽으로만 계속 이어질 수도 있고, 양쪽으로 가득 찰 수도 있다.

포화 이진 트리

모든 레벨의 노드가 빈자리 없이 꽉 차 있는 이진 트리이다.

특징

1. 모든 부모 노드가 자식을 2개씩 가지고 있다.
2. 마지막 레벨까지 모든 자리가 채워져 있다.
3. 같은 높이의 이진 트리 중 노드가 가장 많다.

핵심 단어

모든 레벨이 꽉 참

완전 이진 트리

노드가 위에서 아래로, 왼쪽부터 차례대로 채워진 이진 트리이다.

특징

1. 마지막 레벨을 제외한 위쪽 레벨은 모두 채워져 있다.
2. 마지막 레벨은 전부 차 있지 않아도 된다.
3. 마지막 레벨의 노드는 반드시 왼쪽부터 채워져 있어야 한다.
4. 중간에 빈자리가 있으면 완전 이진 트리가 아니다.

핵심 단어

왼쪽부터 빈자리 없이 채움

편향 이진 트리

노드들이 한쪽 방향으로만 계속 연결된 이진 트리이다.

특징

1. 대부분의 노드가 자식을 1개만 가지고 있다.
2. 한쪽으로 길게 늘어진 형태이다.
3. 왼쪽으로만 이어지면 왼쪽 편향 이진 트리이다.
4. 오른쪽으로만 이어지면 오른쪽 편향 이진 트리이다.

핵심 단어

한쪽으로만 계속 이어짐

3. 이진 트리 표현

배열을 이용해 이진 트리를 표현

이진 트리는 각 노드에 번호를 붙이고, 노드 번호를 배열의 인덱스처럼 사용해서 표현할 수 있다.

• 루트 노드 번호는 1
• 위에서 아래로, 왼쪽에서 오른쪽 순서로 번호를 붙인다.
• 배열의 0번 인덱스는 보통 사용하지 않는다.

노드 번호의 규칙

현재 노드 번호가 i일 때

부모 노드       → i // 2
왼쪽 자식 노드  → i * 2
오른쪽 자식 노드 → i * 2 + 1

예를 들어 5번 노드의 부모는 2번, 왼쪽 자식은 10번, 오른쪽 자식은 11번이다.

배열 표현의 특징

• 포화 이진 트리와 완전 이진 트리는 노드 번호가 연속적으로 배치되어 배열로 표현하기 좋다.
• 반면 편향 이진 트리는 한쪽으로만 노드가 이어지기 때문에 배열 중간에 빈 공간이 많이 생겨 비효율적이다.

완전 이진 트리 → 배열 표현에 적합
편향 이진 트리 → 빈 공간이 많이 발생

부모·자식 관계를 배열에 저장

부모 번호를 인덱스로 자식 저장

트리의 관계 자체를 배열에 저장할 수도 있다.

부모 번호를 배열의 인덱스로 사용하고, 해당 부모의 자식 번호를 저장한다.

부모 1 → 자식 2, 3
부모 2 → 자식 4
부모 3 → 자식 5

즉, 부모를 알고 있을 때 자식을 찾기 편한 방식이다.

자식 번호를 인덱스로 부모 저장

반대로 자식 번호를 배열의 인덱스로 사용하고, 해당 자식의 부모 번호를 저장한다.

자식 2 → 부모 1
자식 3 → 부모 1
자식 4 → 부모 2
자식 5 → 부모 3

즉, 자식을 알고 있을 때 부모를 찾기 편한 방식이다.

부모를 계속 따라 올라가면 조상과 루트도 찾을 수 있다.

5 → 3 → 1

여기서 1이 루트 노드가 된다.

배열 표현의 단점

배열을 이용한 이진 트리는 구현이 간단하지만 다음과 같은 단점이 있다.

• 편향 이진 트리는 사용하지 않는 배열 공간이 많이 생김
• 노드를 추가하거나 삭제할 때 배열 크기 변경이 불편함

이러한 단점을 보완하기 위해 연결 리스트를 이용한 표현을 사용할 수 있다.

연결 리스트를 이용한 이진 트리 표현

각 노드는 다음 세 가지 정보를 가진다.

왼쪽 자식 | 데이터 | 오른쪽 자식

• left : 왼쪽 자식 노드
• data : 현재 노드의 값
• right : 오른쪽 자식 노드

자식이 없는 경우에는 해당 위치를 null로 둔다.

배열처럼 공간을 미리 만들어두는 것이 아니라 필요한 노드끼리 직접 연결하는 방식이다.

3. 순회

트리의 각 노드를 중복되지 않게 전부 방문하는 것 이다.

3가지의 기본적인 순회 방법

1. 전위 순회 VLR

• 부모 노드 방문 후, 자식 노드를 좌,우 순서로 방문한다.

  • 현재 노드 n을 방문해 처리한다. → V

  • 현재 노드 n의 왼쪽 서브트리로 이동한다 → L

  • 현재 노드 n의 오른쪽 서브트리로 이동한다. → R

    preorder_traversr(T):   # 전위 순회
      if T:                 
          visit(T)
          preorder_traverse(T.left)
          preorder_traverse(T.right)

    

2. 중위 순회 LVR

• 왼쪽 자식 노드, 부모 노드, 오른쪽 자식 노드 순으로 방문한다.

  • 현재 노드 n의 왼쪽 서브트리로 이동한다. → L

  • 현재 노드 n을 방문해 처리한다. → V

  • 현재 노드 n의 오른쪽 서브트리로 이동한다 → R

    inorder_traverse(T):           # 중위 순회
      if T:
          inorder_traverse(T.left)
          visit(T)
          inorder_traverse(T.right)        

3. 후위 순회 LRV

• 자식 노드를 좌,우 순서로 방문 후, 부모 노드로 방문한다.

  • 현재 노드 n의 왼쪽 서브트리로 이동한다. → L

  • 현재 노드 n을 오른쪽 서브트리로 이동한다. → R

  • 현재 노드 n을 방문해 처리한다. → V

    postorder_traverse(T):            # 후위 순회
      if T:
          postorder_traverse(T.left)
          postorder_traverse(T.right)
          visit(T)

    

4. 이진 탐색 트리 (BST, Binary Search Tree)

탐색 작업을 효율적으로 하기 위한 자료구조이며, 모든 원소는 서로 다른 유일한 키를 가진다.

• key (왼쪽 서브트리) < key (루트 노드) < key (오른쪽 서브트리)
• 중위순회를 하면 오름차순으로 정렬된 값을 얻을 수 있다.

이진 탐색 트리의 성능

• 탐색 / 삽입 / 삭제 시간은 트리 높이에 비례한다.
• 평균의 경우: 트리가 적당히 균형 잡혀 있어서 빠르다
• 최악의 경우: 편향 트리가 되어 한쪽으로 길게 늘어지면 느리다.

탐색 연산

1. 루트에서 시작
2. 탐색할 키 값 x를 루트 노드의 키 값과 비교한다.
3. 서브트리에 대해서 순환적으로 탐색 연산을 반복한다.

삽입 연산

1. 먼저 탐색 연산을 수행한다.
2. 탐색 실패한 위치에 원소를 삽입한다.

5. 힙 (Heap)

완전 이진 트리에 있는 노드 중에서 키 값이 가장 크거나, 작은 노드를 찾기 위해서 만든 자료구조이다.

1. 최대 힙
   • 키 값이 가장 큰 노드를 찾기 위한 힙이다.
   • 항상 부모 노드의 키 값 > 자식 노드의 키 값 조건을 만족한다.
   • 루트 노드: 키 값이 가장 큰 노드이다.
2. 최소 힙
   • 키 값이 가장 작은 노드를 찾기 위한 힙이다.
   • 항상 부모 노드의 키 값 < 자식 노드의 키 값 조건을 만족한다.
   • 루트 노드: 키 값이 가장 작은 노드이다.

먼저 들어온 데이터가 먼저 나가는 선형 자료구조

큐의 구조

선입선출, FIFO (First In First Out), 가장 먼저 넣은 자료가 가장 먼저 나오는 것이다.

큐의 기본 연산

• 삽입은 enqueue() , 삭제는 dequeue() 라고 한다.

2. 선형 큐 (Linear Queue)

데이터를 일렬로 저장하며, 앞에서 꺼내고 뒤에 넣는 기본 큐 구조이다.

상태표현

1. 초기 상태: front = rear = -1
2. 공백 상태: front == rear
3. 포화 상태: rear == n-1 (배열의 크기 n, 배열의 마지막 인덱스 n-1)

구현

1. 배열이나 연결 리스트로 구현한다.
2. 배열로 구현한 경우 큐의 크기는 배열의 크기와 같다.
3. front : 가장 최근에 삭제된 원소의 인덱스다.
4. rear : 마지막에 저장된 원소의 인덱스다.

# 초기 공백 큐 생성
# create_queue()
q = [0] * n
front = -1
rear = -1

# 삽입 enqueue
def enqueue(item):
    global rear
    if is_full():
        print("Queue_Full")
    else:
        rear = rear + 1
        q[rear] = item

# 삭제 dequeue
def dequeue():
    global front
    if is_empty():
        print("Queue_Empty")
    else:
        front = front + 1
        return q[front]

# 공백 상태 및 포화 상태 검사 is_empty(), is_full()
def is_empty():
    return front == rear

def is_full():
    return rear == len(q) - 1

# 검색 qpeek()
def fqpeek():
    if is_empty():
        print("Queue_Empty")
    else:
        return q[front + 1]

선형 큐 사용시 문제점

선형 큐를 이용해 원소 삽입과 삭제를 계속할 경우, 배열의 앞부분에 활용할 수 있는 공간이 있음에도 불구하고, rear == n-1 인 상태, 포화상태로 인식해 더 이상 삽입을 수행하지 않게 된다.

해결 방법

1. 매 연산이 이루어질 때마다 저장된 원소들을 배열의 앞부분으로 모두 이동한다.
   • 많은 시간이 소요되어 큐의 효율성이 떨어진다.
2. 1차원 배열을 사용한다.
   • 배열의 처음과 끝이 연결되어 원형 형태를 이룬다고 가정하고 사용한다. → 원형 큐

3. 원형 큐 (Circualr Queue)

선형 큐의 공간 낭비를 막기 위해 처음과 끝이 연결된 구조이다.

원형 큐의 구조

원형 큐 구현

# 초기 공백 큐 생성
cq = [0] * n
front = rear = 0

# 삽입 enqueue(item)
def enqueue(item):
    global rear
    if is_full():
        print("Queue_Full")
    else:
        rear = (rear + 1) % len(cq)
        cq[rear] = item

# 삭제 dequeue()
def dequeue():
    global front
    if is_empty():
        print("Queue_Empty")
    else:
        front = (front + 1) % len(cq)
        return cq[front]

# 공백상태 및 포화상태 검사 is_empty(), is_full()
def is_empty():
    return front == rear

def is_full():
    return (rear + 1) % len(cq) == front

4. 연결 큐 (Linked Queue)

연결 리스트를 이용해 구현한 큐 이다.

상태 표현

1. 초기 상태: front == rear == NULL
2. 공백 상태: front == rear == NULL

연결 큐의 구조

단순 연결 리스트를 이용한 큐

1. 큐의 원소: 단순 연결 리스트의 노드이다.
2. 큐의 원소 순서: 노드의 연결 순서, 링크로 연결되어 있다.
3. front : 첫번째 노드를 가리키는 링크이다.
4. rear : 마지막 노드를 가리키는 링크이다.

구현

deque (덱) : 이미 구현되어 있는 자료구조를 가져와서 append(), popleft()만 사용한다.

from collections import deque

q = deque()
q.append(1)     # enqueue()
t =q.popleft()  # dequeue()

class Node:
    def __init__(self, item, n=None):
        self.item = item
        self.next = n
front = None
rear = None

# 연결 큐 삽입 연산
def enqueue(item):
    global front, rear
    newNode = Node(item)   # 새 노드 생성
    if front == None:      # 큐가 비어 있으면
        front = newNode
    else:
        rear.next = newNode
    rear = newNode

# 연결 큐가 비어 있는지 검사
def is_empty():
    return front == None

# 연결 큐 삭제 연산
def dequeue():
    global front, rear
    if is_empty():
        print("Queue_Empty")
        return None
    item = front.item      # 맨 앞 데이터 저장
    front = front.next     # front를 다음 노드로 이동
    if front == None:      # 마지막 원소까지 삭제했다면
        rear = None
    return item

5. 우선 순위 큐 (Priority Queue)

우선순위를 가진 항목들을 저장하는 큐 이다.

배열을 이용한 우선순위 큐

1. 배열을 이용해 자료를 저장한다.
2. 원소를 삽입하는 과정에서 우선순위를 비교하여 적절한 위치에 삽입하는 구조이다.
3. 가장 앞에 최고 우선순위의 원소가 위치한다.

문제점

1. 배열을 사용하므로, 삽입이나, 삭제 연산이 일어날 때 원소의 재배치가 발생한다.
2. 소요되는 시간이나 메모리 낭비가 크다.

6. 큐의 활용

버퍼 (Buffer)

데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리 영역이다.

버퍼의 자료구조

• 일반적으로 입출력 및 네트워크와 관련된 기능에서 이용된다.
• 순서대로 입/출력/전달이 되야하므로 FIFO 방식의 자료구조인 큐가 활용된다.

실습) 마이쮸 나눠주기

마이쮸를 받기 위해 사람들이 한 줄로 줄을 선다.

처음에는 1번 사람이 줄을 서서 마이쮸 1개를 받는다.

마이쮸를 받은 사람은 다시 줄의 맨 뒤로 이동하며, 다음번 자신의 차례에는 이전에 받은 개수보다 1개 더 많은 마이쮸를 받는다.

또한 한 사람이 마이쮸를 받고 다시 줄을 설 때마다 새로운 사람이 1명씩 줄의 맨 뒤에 들어온다.

진행 과정은 다음과 같다.

1번이 줄을 선다.
1번이 마이쮸 1개를 받는다.

1번이 다시 줄을 선다.
새로운 2번이 줄을 선다.

1번이 마이쮸 2개를 받는다.
1번이 다시 줄을 선다.
새로운 3번이 줄을 선다.

2번이 마이쮸 1개를 받는다.
2번이 다시 줄을 선다.
새로운 4번이 줄을 선다.

1번이 마이쮸 3개를 받는다.
1번이 다시 줄을 선다.
새로운 5번이 줄을 선다.

3번이 마이쮸 1개를 받는다.

...

from collections import deque

next_person = 1              # 새로 줄을 설 사람 번호
queue = deque()              # 대기 줄

total_candy = 1000000        # 전체 마이쮸 개수
given_candy = 0              # 지금까지 나눠준 마이쮸 개수

current_person = 0           # 현재 마이쮸를 받는 사람 번호

while given_candy < total_candy:

    # 새로운 사람이 처음 줄을 선다.
    # 처음 받을 개수는 1개, 지금까지 받은 개수는 0개
    queue.append((next_person, 1, 0))

    # 가장 먼저 줄을 선 사람을 꺼낸다.
    current_person, candy_count, received_candy = queue.popleft()

    # 현재 사람에게 마이쮸를 나눠준다.
    given_candy += candy_count

    # 받은 사람은 다시 줄의 맨 뒤로 간다.
    # 다음에는 이전보다 1개 더 받는다.
    queue.append((
        current_person,
        candy_count + 1,
        received_candy + candy_count
    ))

    # 다음에 새로 줄을 설 사람 번호
    next_person += 1

print(f'마지막 받은 사람 : {current_person}')

코드 흐름

1. deque를 이용해 사람들의 대기 줄을 만든다.
2. 새로운 사람은 항상 처음에 마이쮸 1개를 받을 상태로 큐의 뒤에 들어간다.
3. popleft()로 줄의 맨 앞 사람을 꺼낸다.
4. 그 사람이 받을 마이쮸 개수만큼 given_candy에 더한다.
5. 마이쮸를 받은 사람은 다음에 받을 개수를 1 증가시켜 다시 큐의 뒤에 들어간다.
6. 새로운 사람 번호를 1 증가시킨다.
7. 전체 마이쮸가 모두 나눠질 때까지 위 과정을 반복한다.
8. 반복이 끝났을 때 current_person이 마지막으로 마이쮸를 받은 사람이다.

핵심은 아래 두 줄이다.

queue.append(...)# 줄의 맨 뒤에 들어감queue.popleft()# 줄의 맨 앞 사람이 나옴

즉, 먼저 줄을 선 사람이 먼저 마이쮸를 받는 FIFO 구조를 deque로 구현한 시뮬레이션 문제이다.

대표적인 선형 자료 구조 중 하나로 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조

Stack은 후입선출이다. LIFO, Last-In-First-Out

스택을 프로그램에서 구현하기 위해서 필요한 자료구조와 연산

1. 배열을 이용해 구현할 수 있다.
   • 파이썬에서는 리스트 를 이용해서 구현할 수 있다.
2. 저장소 자체를 스택이라고 부르기도 한다.
   • 용도에 따라 메모리 일부를 스택으로 부른다.
3. 스택에서 마지막 삽입된 원소의 위치이다.
   • 스택 포인터, top으로 부르며, 데이터를 넣거나 뺄 때 기준이 되는 위치다.

스택의 연산

1. 삽입 (Push)
   • 저장소에서 자료를 저장하는 연산으로 push라고 부른다.
2. 삭제 (Pop)
   • 저장소에서 삽입한 자료의 역순으로 꺼내는 연산으로 보통 pop이라고 부른다.
3. 스택이 공백인지 아닌지 확인하는 연산 (isEmpty)
   • 스택이 비어 있으면 True, 아니면 False이다.
4. 스택의 top에 있는 item을 반환하는 연산
   • 삭제는 하지 않는다.

Push 연산

• append 를 이용해 리스트 마지막에 데이터 삽입

# append 를 이용해 리스트 마지막에 데이터 삽입
stack = []

def my_push(item):
    stack.append(item)

• 인덱스 연산을 활용한 구현

def my_push(item, size):
    global top
    top += 1
    if top == size:
        print("Overflow")
    else:
        stack[top] = item

• 크기가 정해진 리스트와 인덱스 연산을 활용한 구현

size = 10
stack = [0] * size
top = -1

my_push(10, size)
top += 1
stack[top] = 20

Pop 연산

• 남은 데이터 중 가장 늦게 저장된 데이터를 삭제하는 연산

def my_pop() :
    if len(s) == 0:
        print("Underflow")
        return
    else:
        return s.pop       # 리스트 s의 마지막 원소 삭

• 크기가 정해진 리스트와 인덱스 활용한 구현

def my_pop():
    global top
    if top == 1:
        print("Underflow")
        return 0
    else:
        top -= 1
        return stack[top+1]

print(my_pop())

스택 구현 시 고려 사항

1. 1차원 배열을 사용하여 구현할 경우
   • 장점: 구현이 용이하다.
   • 단점: 스택의 크기를 변경하기가 어렵다.
2. 해결 방법: 저장소를 동적으로 할당하여 스택을 구현하는 방법 (동적 연결 리스트를 이용해 구현하는 방법)
   • 장점: 메모리를 효율적으로 사용한다.
   • 단점: 구현이 복잡하다.

2. 스택의 응용

괄호 검사

조건

1. 왼쪽 괄호 개수와 오른쪽 괄호의 개수가 같아야 한다.
2. 같은 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.
3. 괄호 사이에는 포함 관계만 존재한다.

• 스택을 이용한 괄호 검사

알고리즘 개요

1. 문자열에 있는 괄호를 차례대로 검사하면서 왼쪽 괄호를 만나면 스택에 삽입하고, 오른쪽 괄호를 만나면 스택에서 top 괄호를 삭제한 후 오른쪽 괄호와 짝이 맞는지 검사한다.
2. 스택이 비어있으면 조건 1 또는 조건 2 에 위배되고, 괄호의 짝이 맞지 않으면 조건 3에 위배 된다.
3. 마지막 괄호까지 조사한 후에도 스택에 괄호가 남아 있으면 조건 1에 위배된다.

3. Function call

프로그램에서의 함수 호출과 복귀에 따른 수행 순서를 관리한다.

가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 후입 선출 구조이므로, 후입선출 구조의 스택을 이용해 수행 순서를 관리한다.

시스템 스택

• 함수 수행에 필요한 지역 변수, 매개변수 및 수행 후 복귀할 주소 등의 정보를 저장한다.
• 함수 호출이 발생하면 스택 프레임에 저장해 시스템 스택에 삽입한다.

4. 재귀호출

함수가 자신과 같은 작업을 반복해야 할 때 자기 자신을 다시 호출하는 것 이다.

팩토리얼 (factorial)

• 1부터 n까지 모든 자연수를 곱해 구하는 연산이다.

피보나치 수열

• 0과 1로 시작하고, 이전 두 수의 합을 다음 항으로 하는 수열이다.

# 수열의 i번 항을 반환하는 함수를 재귀 함수로 구현 가능하다.
def fibo(n):
    if n < 2:
        return n
    else:
        return fibo(n-1) + fibo(n-2)

재귀함수의 기본형

• 현재 호출 단계와 목표 단계를 인자로 사용한다.

def recursive(i, N):
    if i == N:        # 중단 조건
        return
    else:             # 재귀 호출
        frecursive(i + 1, N)

5. Memoization

피보나치 재귀호출의 문제점

• 피보나치 수를 구하는 함수를 재귀 함수로 구현한 알고리즘은 엄청난 중복 호출이 존재한다 라는 문제가 발생한다.

메모이제이션 (Memoization)

컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술이다.

• Memoization 을 적용한 피보나치

def fibo(n):
    if n >= 2 and memo[n] == 0:
        memo[n] = fibo(n-1) + fibo(n-2)
    return memo[n]

memo = [0] * (n+1)
memo[0] = 0
memo[1] = 1

6. DFS

깊이 우선 탐색 DFS , 한 방향으로 가능한 한 깊게 탐색한 후, 더 이상 갈 곳이 없으면 되돌아와 다른 방향을 탐색

DFS의 동작원리

1. 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 나간다.
2. 더 이상 갈 곳이 없게되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 탐색 방법이다.
3. 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색 반복해야 하므로 후입선출(LIFO) 구조의 스택을 사용한다.

DFS 알고리즘
1. 시작 정점 v를 결정해 방문한다.

2. 정점 v에서 인접한 정점 중
    a. 방문하지 않은 정점 w가 있으면 정점 v를 스택에 push, 정점 w를 방문하고, w를 v로 해 다시 2를 반복한다.
    b. 방문하지 않은 정점이 없으면 탐색 방향을 바꾸기 위해 스택을 pop, 가장 마지막 방문 정점을 v로 해 다시 2를 반복한다.

3. 스택이 공백이 될 때까지 2를 반복한다.

def dfs(v):
    visited = [False] * (N + 1)   # 방문 여부
    stack = []                    # 스택 초기화

    visited[v] = True             # 시작 정점 방문
    print(v, end=' ')

    while True:
        # 현재 정점 v와 인접한 정점 중
        # 아직 방문하지 않은 정점 w 찾기
        for w in graph[v]:

            if not visited[w]:
                stack.append(v)   # 현재 위치 저장

                v = w             # 다음 정점으로 이동
                visited[v] = True
                print(v, end=' ')

                break

        # 방문할 정점이 없는 경우
        else:
            if stack:
                v = stack.pop()   # 이전 정점으로 되돌아감

            else:
                break             # 스택도 비었으면 DFS 종료

목차

1. 코드 체계
2. 문자열
3. Python 문자열 입력과 기본 처리
4. 문자열 연산
5. 패턴 매칭
6. 고지식한 패턴 검색 (Brute Force)
7. KMP 알고리즘
8. 보이어-무어 알고리즘
9. 문자열 암호화
10. 문자열 압축

1. 코드 체계

코드체계는 문자에 대응되는 숫자를 정한 것이다.

• 바이트(Byte): 주소가 부여되는 최소 단위
• 컴퓨터는 문자를 그대로 저장하는 것이 아니라 숫자로 바꾸어 저장한다.

코드 체계의 개선

지역마다 서로 다른 코드체계를 사용하면 같은 숫자를 서로 다른 문자로 해석할 수 있다. 이런 혼동을 줄이기 위 해 표준 문자 인코딩 체계가 만들어졌다.

ASCII

• 미국에서 제정된 문자 인코딩 표준이다.
• 7-bit 인코딩으로 128 개의 문자를 표현한다.
• 영문 대소문자, 숫자, 기호, 제어 문자 등을 포함한다.

# 문자와 코드 값 확인 예시
print(ord('A')) # 65
print(chr(65)) # A

확장 아스키 (Extended ASCII)

• 표준 ASCII 문자 외에 악센트 문자, 도형 문자, 특수 문자 등을 128 개 추가한 형태이다.
• 1Byte의 8-bit 를 모두 사용하여 최대 256 개의 값을 표현한다.
• 확장 영역은 프로그램이나 환경에 따라 문자 대응이 다를 수 있다.

유니코드 (Unicode)

• 다국어 처리를 위한 표준 코드체계이다.
• 각 나라의 문자 체계가 달라 생기는 호환 문제를 줄이기 위해 만들어졌다.
• 이모지(Emoji)도 유니코드 문자에 포함된다.

자료에서는 유니코드 Character Set 으로 UCS-2 와 UCS-4를 소개하고, 저장 변수의 크기와 바이트 순서 문제 를 함께 설명한다.

바이트 단위 저장 순서 (Endian)

• Big-endian: 상위 바이트(MSB)를 가장 낮은 주소에 저장한다.
• Little-endian: 하위 바이트(LSB)를 가장 낮은 주소에 저장한다.

핵심 같은 여러 바이트 데이터라도 저장 순서를 서로 다르게 해석하면 전혀 다른 값으로 읽힐 수 있다.

유니코드 인코딩 (UTF)

줄바꿈 문자와 OS

• Windows: CR(13) + LF(10)
• Unix / macOS: LF(10)

강의자료는 PyCharm 등의 상태 표시줄에서 파일 인코딩과 줄바꿈 형식을 확인할 수 있음을 예로 든다.

Python 인코딩

• 자료에서는 Python 2.x에서 UTF-8 사용 시 코드 첫 줄에 인코딩 주석이 필요하다고 설명한다.

-- coding: utf-8 --

• Python 3.x 에서는 UTF-8 방식이 기본이므로 표시를 생략할 수 있다고 설명한다.

2. 문자열

문자열(String)은 문자들이 순서대로 나열된 데이터이다. 문장, 단어, 기호 등의 텍스트를 표현하거나 처리할 때사용한다.

문자열의 분류

1. Length-Controlled 문자열
   • 문자열의 길이 정보를 함께 저장하고, 그 길이만큼 문자 데이터를 읽는 방식이다.
   • Java, Python, 네트워크 패킷 등에 사용된다.
2. Delimited 문자열
   • 문자열 끝을 나타내는 특정 구분자(Delimiter)가 나올 때까지 문자열로 인식한다.
   • C 언어에서는 널 문자(null, ‘W0’)를 사용한다.

언어별 문자열 표현

Python 에서 문자열

• 문자열은 데이터의 순서가 구분되는 시퀀스 자료형이다.
• 인덱싱과 슬라이싱을 사용할 수 있다.
• replace(), split(), isalpha(), find() 등의 메서드를 제공한다.
• 문자열은 튜플처럼 요소 값을 직접 변경할 수 없는 immutable 자료형이다.

s = "abc"
print(s[1]) # b
print(s[0:2]) # ab
# s[0] = "A" # TypeError: 문자열 요소는 직접 변경할 수 없음

문자열 생성과 기본 연산

• 작은따옴표(’‘), 큰따옴표(““), 삼중따옴표(”’ ““,”“” “““)로 문자열을 만들 수 있다.
• +: 문자열 연결(Concatenation)
• : 문자열 반복

print('ab' + 'c') # abc
print('ab' * 3) # ababab

3. Python 문자열 입력과 기본 처리

문자열 한 줄 입력

text = input()

input()은 입력된 한 줄을 문자열로 읽어 들인다. 공백이 포함되어 있어도 한 줄 전체가 문자열에 저장된다.

문자를 리스트로 입력

text = list(input())
# 예: Hello -> ['H', 'e', 'l', 'l', 'o']

각 문자를 리스트의 원소로 따로 다루고 싶을 때 사용할 수 있다.

여러 줄 문자열 입력

N = int(input())
arr = [input() for _ in range(N)]

각 줄을 문자열 한 개로 저장한다.

문자 단위 2 차원 리스트

N = int(input())
arr = [list(input()) for _ in range(N)]

$\mathrm{N} \times \mathrm{N}$ 문자 지도처럼 각 칸의 문자를 직접 확인하거나 변경해야 할 때 사용하기 편하다.

특정 문자 존재 여부 확인

text = input()
for char in text:
    if char == "Z":
        print("Z 가 존재합니다.")

4. 문자열 연산

문자열 뒤집기 문자열을 역순으로 재정의하는 것이다.

s = "Reverse this strings"
s = s[::-1]
print(s) # sgnirts siht esreveR

리스트로 변환한 뒤 reverse()를 사용하고 다시 문자열로 합칠 수도 있다.

s = "abcd"
s = list(s)
s.reverse()
s = "".join(s)
print(s) # dcba

회문 (Palindrome)

기러기, 토마토처럼 앞에서 읽어도 뒤에서 읽어도 같은 문자열을 회문이라고 한다. 문자열 길이의 절반만 비교하면 된다.

def is_palindrome(txt):
    # 앞쪽 절반만 확인
    for i in range(len(txt) // 2):
        # 앞쪽 문자와 뒤쪽 문자가 다르면 회문이 아님
        if txt[i] != txt[len(txt) - 1 - i]:
            return False
    return True

인덱스 핵심 앞쪽 $\mathrm{txt}[\mathrm{i}]$ 와 뒤쪽 $\mathrm{txt}[\operatorname{len}(\mathrm{txt})-1$ - i]를 짝지어 비교한다.

문자열 비교: == 와 is

• == : 두 값(value)이 같은지 비교한다. 내부적으로 eq()를 호출한다.
• is : 두 변수가 같은 객체(identity), 즉 같은 메모리 객체를 가리키는지 비교한다.

str1 = "abc"
str2 = "abc"
str4 = str1
str5 = str1[:2] + "c"
print(str1 = str2) # True
print(str1 is str2) # 실행 환경에 따라 같은 객체로 재사용 될 수 있음
print(str4 == str5) # True
print(str4 is str5) # False 가 될 수 있음

주의 문자열 내용 비교에는 ==를 사용한다. is 는 값 비교용이 아니라 객체 동일성 비교용이다.

사전 순서 비교 문자열은 <, > 연산자로 사전 순서를 비교할 수 있으며 자료에서는 유니코드 값을 기준으로 비교한다고 설명한다.

def my_strcmp(str1, str2):
    if str1 < str2:
        return -1
    elif str1 > str2:
        return 1

else: return 0

• 예: ‘Apple’ < ‘apple’ 은 True
• 예: ‘Zebra’ < ‘apple’ 은 True

문자열 ↔︎ 숫자 변환

# 문자열 -> 숫자
a = int("123")
b = float("3.14")
c = int("A0", 16) # 문자열 A0를 16진법으로 해석
# 숫자 -> 문자열
d = str(123)
e = str(3.14)

5. 패턴 매칭

패턴 매칭은 본문 문자열(Text) 안에서 찾고 싶은 문자열(Pattern)이 존재하는지, 존재한다면 어느 위치에 있는지 찾는 과정이다.

강의자료에서는 고지식한 패턴 검색, KMP, 보이어-무어 알고리즘을 비교한다.

6. 고지식한 패턴 검색 (Brute Force)

본문 문자열의 처음부터 끝까지 순회하면서 패턴의 문자들을 일일이 비교하는 가장 단순한 방법이다.

• 문자가 같으면 본문 인덱스 i 와 패턴 인덱스 j 를 함께 증가시킨다.
• 실패하면 비교를 시작했던 위치의 다음 칸으로 돌아가고, 패턴 인덱스는 처음부터 다시 시작한다.

def brute_force(p, t):
    # p: 찾을 패턴, t: 본문 문자열
    i = 0
    j = 0
    M = len(p)
    N = len(t)
    while j < M and i < N:
        if t[i] != p[j]:
            # 시작 위치의 다음 칸으로 이동하도록 복원
            i = i - j
            j = -1
        i += 1
        j += 1
    if j = m:
        return i - M # 검색 성공: 시작 인덱스
    else:
        return -1 # 검색 실패

시간 복잡도

• 최악의 경우 본문의 거의 모든 위치에서 패턴 전체를 비교할 수 있다.
• 본문 길이 N, 패턴 길이 M 일 때 O(MN)

자료의 예에서는 길이 10,000 인 문자열에서 길이 80 인 패턴을 찾는 경우 최악 약 800,000 번 비교가 필요할수 있다고 설명한다.

7. KMP 알고리즘

KMP 는 Knuth, Morris, Pratt 세 사람의 이름에서 유래한 문자열 검색 알고리즘이다.

핵심 아이디어

• 패턴의 각 위치에서 매칭에 실패했을 때 돌아갈 위치를 미리 계산한다.
• 불일치가 발생하기 전까지 이미 일치했던 정보를 버리지 않고 재사용한다.
• 따라서 불일치한 앞부분을 다시 처음부터 비교하는 일을 줄일 수 있다.

LPS 배열

LPS 는 Longest Prefix which is also Suffix 의 약자로, 패턴의 각 위치까지 보았을 때 접두사(prefix)와 접미사 (suffix)가 같은 최대 길이를 저장한다. 자료에서는 next 또는 pi 배열이라고도 설명한다.

패턴: a b c d a b c e f
LPS : 0 0 0 0 1 2 3 0 0

역할 비교 중 실패했을 때 패턴 인덱스를 무조건 0 으로 되돌리지 않고, LPS 값을 이용해 다음 비교 위치를 정한 다.

시간 복잡도

• 패턴 전처리: $\mathrm{O}(\mathrm{M})$
• 본문 검색: $\mathrm{O}(\mathrm{N})$
• 전체: $\mathrm{O}(\mathrm{M}+\mathrm{N})$
• 자료에서는 패턴 길이 M 이 매우 짧고 고정된 경우 평균적으로 $\Theta(\mathrm{N})$ 에 가깝다고 설명한다.

8. 보이어-무어 알고리즘

보이어-무어(Boyer-Moore)는 실제 문자열 검색 소프트웨어에서도 채택되는 빠른 검색 알고리즘으로 소개된다.

핵심 특징

• 패턴의 오른쪽 끝에서부터 비교한다.
• 오른쪽 끝에서 불일치가 발생하면 한 칸씩만 이동하지 않고 여러 칸을 한 번에 건너뒬 수 있다.

불일치 문자 휴리스틱 (Bad-Character Heuristic)

패턴의 오른쪽 끝 문자와 본문의 문자가 불일치할 때, 그 본문 문자가 패턴 안에 존재하는지 확인해서 이동 거리 를 정한다.

• 불일치 문자가 패턴에 없으면 패턴 길이만큼 크게 이동할 수 있다.
• 패턴 안에 있으면 해당 문자가 오른쪽 끝과 일치하도록 패턴을 이동한다.

Skip 배열 예

자료의 ‘rithm’ 패턴 예에서는 다음과 같은 이동 값을 사용한다.

문자열 매칭 알고리즘 비교

기억법 Brute Force = 처음부터 / KMP = 앞에서 얻은 정보 재사용 / Boyer-Moore = 오른쪽부터 보고 크게 점프

9. 문자열 암호화

시저 암호 (Caesar Cipher) 율리우스 시저가 사용했다고 알려진 암호 방식으로, 평문에 사용된 알파벳을 일정한 문자 수만큼 평행 이동시켜암호화한다.

키 = 1
A -> B
B -> C
C -> D
...

자료의 예에서는 “SAVE PRIVATE RYAN”을 일정한 키 값으로 이동한 암호문을 보여준다. 암호화할 때 사용한이동 값을 키(Key)라고 한다.

전사 공격 (Brute Force Attack) 시저 암호는 가능한 키의 수가 적기 때문에 키 값을 하나씩 모두 적용해 원문이 나오는지 확인할 수 있다.

키 1 2 적용
키 25 적용

• 가능한 모든 경우를 하나씩 시도하는 방식이 전사 공격이다.

단일 치환 암호 각 알파벳 하나를 다른 고정된 알파벳 하나로 대응시키는 방식이다. 시저 암호처럼 일정한 거리로 이동하는 것이아니라 문자 변환표 자체를 사용한다.

A -> Q
B -> H
C -> C
D -> B
...

가능한 키의 수 알파벳 26 개를 서로 다르게 배치하는 경우의 수는 다음과 같다.

26 x 25 × 24 × ... × 1 = 26!

자료에서는 초당 매우 많은 키를 적용하더라도 전부 확인하는 데 매우 긴 시간이 걸린다고 설명한다. 빈도 분석 전사 공격이 어려워도 언어의 통계적 특성을 활용할 수 있다. 영어 평문에서 자주 나오는 문자를 추정해 암호문에서 빈도가 높은 문자와 대응시키는 방식이다.

• 자료에서는 영어에서 많이 쓰이는 글자 예로 E, T, A 등을 든다.

1. 문자열 압축

Run-Length Encoding (RLE) 같은 값이 몇 번 반복되는지를 나타내는 방식이다. 반복이 많은 데이터에서 효과적이다. 원본: ABBBBBBBBA 압축: A1B8A1

• 자료에서는 이미지 파일 포맷 중 BMP 의 압축 방식 중 하나로 사용된다고 설명한다.

허프만 코딩 (Huffman Coding)

대표적인 압축 방법으로, 등장 빈도에 따라 서로 다른 길이의 코드를 부여한다.

• 자주 나오는 문자 -> 짧은 코드
• 드물게 나오는 문자 -> 긴 코드

결과적으로 전체 데이터의 평균 코드 길이를 줄이는 방식이다.

자주 쓰는 Python 코드 모음

문자열 뒤집기
s[::-1]
회문 간단 확인
s == s[::-1]
문자열 찾기
s.find("abc")
문자열 치환
s.replace("a", "b")
문자열 분리
s.split()
리스트 → 문자열
"".join(arr)
문자 코드
ord('A')
chr(65)
문자열 → 숫자
int("123")
float("3.14")
int("A0", 16)
숫자 → 문자열
str(123)

복습 체크

• UTF-8은 가변 길이 인코딩이며 자료에서는 최대 4Byte 까지 사용한다고 설명한다.
• 문자열은 ordered 시퀀스 자료형이며 immutable 이다.
• find()는 특정 문자가 처음 등장하는 인덱스를 찾는 데 사용할 수 있다.
• count()는 특정 문자열/문자의 등장 횟수를 셀 때 사용할 수 있다.
• upper()는 문자열을 대문자로 변환한 새 문자열을 반환한다.
• strip()은 문자열의 앞뒤 공백을 제거한다.
• join()은 리스트 등의 문자열 원소를 특정 구분자로 이어 붙인다.

1. 정렬(Sort)

2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값 순서 또는 그 반대 순서로 재배열하는 것이다.

오름차순(ascending)
= 작은 값 → 큰 값

내림차순(descending)
= 큰 값 → 작은 값

교재에서 소개하는 대표적인 정렬:

• 버블 정렬(Bubble Sort)
• 카운팅 정렬(Counting Sort)
• 선택 정렬(Selection Sort)
• 퀵 정렬(Quick Sort)
• 삽입 정렬(Insertion Sort)
• 병합 정렬(Merge Sort)

2. 버블 정렬

인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식이다.

1. 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동한다.
2. 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.
3. 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블 정렬이라고 한다.

시간 복잡도

O(n²)

정렬 과정 예시

55  7  78  12  42

첫 번째 패스
55와 7 비교  → 교환
55와 78 비교 → 유지
78과 12 비교 → 교환
78과 42 비교 → 교환

결과
7  55  12  42  78

한 번의 패스가 끝나면 가장 큰 값이 맨 뒤에 위치한다.

정렬 과정의 의사코드

BubbleSort(a, N)             # 정렬할 배열과 배열의 크기
    for i : N - 1 -> 1       # 정렬할 구간의 끝
        for j : 0 -> i - 1   # 비교할 왼쪽 원소의 인덱스
            if a[j] > a[j + 1]
                a[j] <-> a[j + 1]

정렬 과정의 코드

def bubble_sort(a, N):                       # 정렬할 List, N 원소의 수
    for i in range(N - 1, 0, -1):            # 정렬할 구간의 끝
        for j in range(i):                   # 비교할 왼쪽 원소 인덱스
            if a[j] > a[j + 1]:              # 왼쪽 값이 더 크면
                a[j], a[j + 1] = a[j + 1], a[j]  # 자리 교환

핵심

if a[j] > a[j + 1]:

인접한 두 값을 비교한다.

a[j], a[j + 1] = a[j + 1], a[j]

왼쪽 값이 더 크면 서로 자리를 바꾼다.

3. 카운팅 정렬

항목들의 순서를 결정하기 위해 각 항목이 몇 개씩 있는지 세는 작업을 하여 정렬하는 방식이다.

비교와 교환을 반복하는 버블 정렬과 달리, 각 값의 등장 횟수를 이용한다.

시간 복잡도

O(n + k)

• n : 리스트의 길이
• k : 정수의 최댓값

카운팅 정렬의 제한 사항

1. 정수나 정수로 표현할 수 있는 자료에 대해서만 적용할 수 있다.
2. 정수 항목을 인덱스로 사용하는 카운트 배열이 필요하다.
3. 카운트 배열을 위한 충분한 공간을 확보하려면 집합 내의 가장 큰 정수를 알아야 한다.

4. 카운팅 정렬 과정

예:

DATA = [0, 4, 1, 3, 1, 2, 4, 1]

1. 각 숫자의 발생 횟수 세기

처음:

INDEX   0  1  2  3  4
COUNTS  0  0  0  0  0

개수를 세면:

INDEX   0  1  2  3  4
COUNTS  1  3  1  1  2

코드:

COUNTS = [0] * 5

for x in DATA:
    COUNTS[x] += 1

핵심:

COUNTS[x] += 1

= 숫자 x가 등장할 때마다 x번 인덱스의 값을 1 증가시킨다.

2. COUNTS 누적

기존 COUNTS
1  3  1  1  2

누적 후
1  4  5  6  8

코드:

for i in range(1, k + 1):
    COUNTS[i] += COUNTS[i - 1]

누적값을 이용하면 해당 숫자가 정렬된 배열에서 어느 위치까지 들어가는지 알 수 있다.

3. TEMP에 실제 위치대로 저장

DATA를 뒤에서부터 확인하면서:

1. 해당 숫자의 COUNTS 값을 1 감소시킨다.
2. 감소한 값을 TEMP의 인덱스로 사용한다.
3. 해당 위치에 숫자를 저장한다.

for i in range(len(DATA) - 1, -1, -1):
    COUNTS[DATA[i]] -= 1
    TEMP[COUNTS[DATA[i]]] = DATA[i]

최종 결과:

TEMP = [0, 1, 1, 1, 2, 3, 4, 4]

5. 카운팅 정렬 의사코드

CountingSort(DATA, TEMP, k)

    COUNTS = [0] * (k + 1)

    # 1. 각 숫자의 등장 횟수 기록
    for i : 0 -> len(DATA) - 1
        COUNTS[DATA[i]] += 1

    # 2. 누적
    for i : 1 -> k
        COUNTS[i] += COUNTS[i - 1]

    # 3. 정렬된 위치에 저장
    for i : len(DATA) - 1 -> 0
        COUNTS[DATA[i]] -= 1
        TEMP[COUNTS[DATA[i]]] = DATA[i]

6. 카운팅 정렬 코드

def counting_sort(DATA, TEMP, k):
    # DATA   : 입력 배열
    # TEMP   : 정렬된 배열
    # COUNTS : 카운트 배열

    COUNTS = [0] * (k + 1)

    # 1. 각 숫자의 등장 횟수 기록
    for i in range(len(DATA)):
        COUNTS[DATA[i]] += 1

    # 2. COUNTS 누적
    for i in range(1, k + 1):
        COUNTS[i] += COUNTS[i - 1]

    # 3. TEMP에 정렬된 위치대로 저장
    for i in range(len(DATA) - 1, -1, -1):
        COUNTS[DATA[i]] -= 1
        TEMP[COUNTS[DATA[i]]] = DATA[i]

7. 카운팅 정렬 간단한 코드

정렬된 숫자만 필요하다면, 각 숫자의 개수를 센 뒤 그 개수만큼 append()하는 방식으로 이해할 수 있다.

def counting_sort(arr):
    max_value = max(arr)

    count = [0] * (max_value + 1)

    # 숫자별 등장 횟수
    for num in arr:
        count[num] += 1

    result = []

    # 작은 숫자부터 개수만큼 추가
    for i in range(len(count)):
        for _ in range(count[i]):
            result.append(i)

    return result

예:

arr = [0, 4, 1, 3, 1, 2, 4, 1]

결과:

[0, 1, 1, 1, 2, 3, 4, 4]

8. 버블 정렬 vs 카운팅 정렬

구분

버블 정렬
= 옆의 값을 비교해서 자리 바꿈

카운팅 정렬
= 각 숫자가 몇 개인지 먼저 셈

완전 검색

9. 완전 검색(Exhaustive Search)

문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해 보고 확인하는 기법이다.

다른 표현:

Brute-force
Generate-and-test

특징

• 모든 경우를 확인하기 때문에 해답을 찾을 가능성이 높다.
• 경우의 수가 많아질수록 수행 속도가 느려질 수 있다.
• 문제를 처음 접했을 때 우선 완전 검색으로 접근한 뒤, 필요하면 더 효율적인 알고리즘을 고민할 수 있다.

10. Baby-gin과 완전 검색

6장의 카드가 주어질 때:

run

연속된 번호 3장이 존재하는 경우

예:

2 3 4

triplet

같은 번호 3장이 존재하는 경우

예:

7 7 7

6장의 카드가 run과 triplet만으로 구성된 경우 Baby-gin이라고 한다.

완전 검색 방식에서는:

가능한 순열 모두 생성
↓
앞 3장 검사
↓
뒤 3장 검사
↓
run / triplet 여부 확인

11. 순열(Permutation)

서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것이다.

표현:

nPr

계산:

nPr = n × (n-1) × (n-2) × ... × (n-r+1)

모두 뽑는 경우:

n! = n × (n-1) × ... × 2 × 1

12. 1, 2, 3의 모든 순열 만들기

for i1 in range(1, 4):
    for i2 in range(1, 4):
        if i2 != i1:
            for i3 in range(1, 4):
                if i3 != i1 and i3 != i2:
                    print(i1, i2, i3)

핵심은 이미 선택한 숫자를 다시 선택하지 않도록 조건을 검사하는 것이다.

탐욕 알고리즘

13. 탐욕 알고리즘(Greedy)

여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식이다.

각 단계에서 당장 가장 좋아 보이는 선택을 계속 이어가 최종 해답을 만든다.

14. 탐욕 알고리즘의 특징

1. 해를 구하는 데 사용되는 근시안적인 방법이다.
2. 각 선택 시점에서는 지역적으로 최적인 선택을 한다.
3. 이러한 선택을 계속 모아 최종 해답을 만든다.
4. 각 순간의 최적 선택이 항상 전체 문제의 최적해를 보장하는 것은 아니다.

15. 탐욕 알고리즘 과정

1. 해 선택

현재 상태에서 부분 문제의 최적해를 구하고 이를 부분 해 집합에 추가한다.

2. 실행 가능성 검사

새로운 부분 해 집합이 실행 가능한지 확인한다.

문제의 제약 조건을 위반하면 해당 선택을 버린다.

3. 해 검사

새로운 부분 해 집합이 문제의 해가 되는지 확인한다.

아직 전체 해가 완성되지 않았다면 다시 선택 단계부터 반복한다.

16. Baby-gin을 카운트 배열로 접근

6자리 숫자를 하나씩 분리해 COUNTS 배열에 개수를 저장한다.

num = 456789
c = [0] * 12

for i in range(6):
    c[num % 10] += 1
    num //= 10

핵심

num % 10

가장 오른쪽 숫자 하나를 가져온다.

num //= 10

가장 오른쪽 숫자를 제거한다.

17. triplet / run 검사

i = 0
tri = 0
run = 0

while i < 10:

    # triplet 확인
    if c[i] >= 3:
        c[i] -= 3
        tri += 1
        continue

    # run 확인
    if c[i] >= 1 and c[i + 1] >= 1 and c[i + 2] >= 1:
        c[i] -= 1
        c[i + 1] -= 1
        c[i + 2] -= 1
        run += 1
        continue

    i += 1

if run + tri == 2:
    print("Baby Gin")
else:
    print("Lose")

흐름

숫자별 개수 기록
↓
triplet이 있으면 3개 제거
↓
run이 있으면 연속된 3개 제거
↓
run + triplet 개수가 2인지 확인

18. Baby-gin에서 주의할 점

정렬한 뒤 앞의 3자리와 뒤의 3자리만 단순하게 잘라 확인하면 모든 경우를 해결하지 못할 수 있다.

따라서:

• 완전 검색으로 가능한 모든 경우를 확인하거나
• 카운트 배열을 활용하여 run과 triplet을 직접 검사하는 방법을 사용할 수 있다.

문제를 해결하기 위한 절차나 방법이다.

컴퓨터가 어떤 일을 수행하기 위한 단계적인 방법을 의미한다.

알고리즘을 표현하는 방법

• 의사코드(Pseudocode)
• 순서도(Flowchart)

의사코드 예시

CalcSum(n)
    sum = 0
    for i : 1 -> n
        sum = sum + i
    return sum

2. 알고리즘의 성능

좋은 알고리즘인지 판단할 때 다음 기준을 볼 수 있다.

1. 정확성
   • 얼마나 정확하게 동작하는가
2. 작업량
   • 얼마나 적은 연산으로 원하는 결과를 얻어내는가
3. 메모리 사용량
   • 얼마나 적은 메모리를 사용하는가
4. 단순성
   • 얼마나 단순한가
5. 최적성
   • 더 이상 개선할 여지없이 최적화되어 있는가

3. 시간 복잡도

알고리즘의 작업량을 표현할 때 사용하는 방법이다.

실제 실행 시간을 직접 측정하기보다 실행되는 명령문의 개수를 이용해 비교할 수 있다.

예시 — 1부터 n까지의 합

반복문 방식

def calc_sum(n):
    total = 0

    for i in range(1, n + 1):
        total = total + i

    return total

n이 커질수록 반복 횟수도 증가한다.

공식 이용

def calc_sum(n):
    return n * (n + 1) // 2

반복문 없이 일정한 수의 연산으로 계산한다.

4. Big-O 표기법

시간 복잡도 함수에서 가장 큰 영향을 주는 항만 남겨 표현하는 방법이다.

상수 계수는 생략한다.

O(3n + 2)
→ O(3n)
→ O(n)

O(2n² + 10n + 100)
→ O(n²)

O(4)
→ O(1)

대표적인 시간 복잡도

O(1)
O(log n)
O(n)
O(n log n)
O(n²)
O(n³)
O(2ⁿ)

일반적으로 입력 크기가 커질수록 뒤쪽의 복잡도는 실행 시간이 매우 빠르게 증가한다.

배열

5. 배열(Array)

일정한 자료형의 변수들을 하나의 이름으로 여러 개 사용하기 위한 자료구조이다.

파이썬에서는 list를 이용하여 배열처럼 사용한다.

예:

num = [0, 1, 2, 3, 4, 5]

각 값에는 인덱스(index) 로 접근한다.

인덱스 : 0  1  2  3  4  5
값     : 0  1  2  3  4  5

첫 번째 원소의 인덱스는 0이다.

6. 배열이 필요한 이유

여러 개의 변수를 각각 선언하면 관리가 어렵다.

num0 = 0
num1 = 1
num2 = 2
num3 = 3

배열을 사용하면 하나의 이름으로 관리할 수 있다.

num = [0, 1, 2, 3]

7. 1차원 배열 선언

빈 리스트

arr = list()

또는

arr = []

같은 값으로 초기화

arr = [0] * 10

값을 직접 저장

arr = [1, 2, 3]

8. 배열 입력 받기

첫 번째 줄에 정수 N, 두 번째 줄에 공백으로 구분된 N개의 정수가 들어오는 경우:

N = int(input())
arr = list(map(int, input().split()))

9. 배열 원소의 합 구하기

배열의 값을 처음부터 끝까지 하나씩 누적한다.

코드

s = 0

for i in range(N):
    s += arr[i]

같은 의미로 다음처럼 작성할 수도 있다.

s = 0

for x in arr:
    s += x

흐름

s = 0
↓
arr[0] 더하기
↓
arr[1] 더하기
↓
...
↓
마지막 값까지 더하기

10. 배열에서 최댓값 찾기

첫 번째 값을 최댓값이라고 가정한 뒤, 더 큰 값을 만나면 갱신한다.

코드

max_v = arr[0]

for i in range(1, N):
    if max_v < arr[i]:
        max_v = arr[i]

흐름

첫 번째 값 → max_v로 가정
↓
다음 값을 하나씩 비교
↓
더 큰 값 발견
↓
max_v 갱신

11. 최댓값의 인덱스 찾기

최댓값 자체가 아니라 최댓값이 들어있는 위치를 저장한다.

가장 왼쪽의 최댓값 인덱스

max_idx = 0

for i in range(1, N):
    if arr[max_idx] < arr[i]:
        max_idx = i

동일한 최댓값을 만나도 갱신하지 않기 때문에 가장 먼저 나온 최댓값의 인덱스가 남는다.

예:

arr = [2, 7, 5, 3, 1, 7]

결과:

max_idx = 1

12. 최댓값이 여러 개일 때 마지막 인덱스 찾기

비교 조건에 =을 포함한다.

max_idx = 0

for i in range(1, N):
    if arr[max_idx] <= arr[i]:
        max_idx = i

예:

arr = [2, 7, 5, 3, 1, 7]

결과:

max_idx = 5

차이

<     # 같은 값이면 갱신하지 않음 → 가장 왼쪽
<=    # 같은 값이어도 갱신 → 가장 오른쪽

13. 배열에서 특정 값 찾기

찾는 값이 있으면 해당 원소의 인덱스를 저장하고, 없으면 -1을 유지한다.

idx = -1

for i in range(N):
    if arr[i] == V:
        idx = i
        break

핵심

idx = -1

처음에는 찾는 값이 없다고 가정한다.

break

값을 찾으면 더 이상 반복할 필요가 없으므로 반복문을 종료한다.

1. EDA

데이터의 기본 상태를 확인하고 분포를 시각화

데이터 크기 확인
df.shape
    ↓
데이터 정보 확인
df.info()
    ↓
결측치 개수 확인
isnull().sum()
    ↓
score / label 값별 개수 확인
value_counts()
    ↓
인덱스 순서대로 정렬
sort_index()
    ↓
원본 데이터 복사
copy()
    ↓
리뷰 문자열 길이 계산
str.len()
    ↓
score / label 분포 시각화
sns.countplot()
    ↓
리뷰 길이 분포 시각화
sns.histplot()
    ↓
그래프 출력
plt.show()

2. Linear Regression

감정 점수를 이용해 별점(score)을 예측

입력값(X), 정답(y) 준비
    ↓
학습 / 테스트 데이터 분리
train_test_split()
    ↓
스케일러 생성
StandardScaler()
    ↓
학습 데이터 기준 학습 + 변환
fit_transform()
    ↓
테스트 데이터 변환
transform()
    ↓
선형 회귀 모델 생성
LinearRegression()
    ↓
모델 학습
fit()
    ↓
예측
predict()
    ↓
실제값과 예측값 비교
    ↓
MSE 계산
mean_squared_error()
    ↓
R² 계산
r2_score()

3. Logistic Regression

감정 점수를 이용해 긍정 / 부정(label)을 분류

입력값(X), 정답(y) 준비
    ↓
전체 데이터의 인덱스 생성
np.arange()
    ↓
학습 / 테스트 인덱스 분리
train_test_split()
    ↓
라벨 비율 유지
stratify
    ↓
인덱스를 이용해 학습 / 테스트 데이터 분리
    ↓
스케일러 생성
StandardScaler()
    ↓
학습 데이터 기준 학습 + 변환
fit_transform()
    ↓
테스트 데이터 변환
transform()
    ↓
로지스틱 회귀 모델 생성
LogisticRegression()
    ↓
모델 학습
fit()
    ↓
0 / 1 예측
predict()
    ↓
Accuracy 계산
accuracy_score()
    ↓
F1 계산
f1_score()

4. Embedding

리뷰 문장을 의미를 나타내는 숫자 벡터로 변환

임베딩 모델 생성
SentenceTransformer()
    ↓
리뷰 문장 입력
    ↓
문장을 임베딩 벡터로 변환
encode()
    ↓
임베딩 벡터 정규화
normalize_embeddings=True
    ↓
임베딩 크기 확인
shape

5. Embedding + Logistic Regression

리뷰 Embedding을 이용해 긍정 / 부정 분류

리뷰 Embedding 준비
encode()
    ↓
기존 학습 / 테스트 인덱스로 분리
    ↓
로지스틱 회귀 모델 생성
LogisticRegression()
    ↓
Embedding과 정답으로 모델 학습
fit()
    ↓
테스트 Embedding으로 0 / 1 예측
predict()
    ↓
Accuracy 계산
accuracy_score()
    ↓
F1 계산
f1_score()

6. Embedding + PyTorch MLP

Embedding을 신경망에 넣어 긍정 / 부정 분류

Embedding을 Tensor로 변환
torch.tensor()
    ↓
정답을 Tensor로 변환
torch.tensor()
    ↓
학습 / 테스트 데이터 분리
    ↓
MLP 모델 생성
ReviewMLP()
    ↓
손실함수 생성
nn.BCELoss()
    ↓
가중치 최적화 도구 생성
optim.Adam()
    ↓
여러 Epoch 반복
range()
    ↓
이전 가중치 기울기 초기화
zero_grad()
    ↓
학습 데이터로 예측
MLP에 데이터 입력
    ↓
예측값과 정답의 손실 계산
BCELoss()
    ↓
가중치 기울기 계산
backward()
    ↓
가중치 업데이트
step()
    ↓
테스트 데이터로 예측
MLP에 데이터 입력
    ↓
불필요한 차원 제거
squeeze()
    ↓
예측 확률을 0 / 1로 변환
>= 0.5
    ↓
Accuracy 계산
accuracy_score()
    ↓
F1 계산
f1_score()

PyTorch 학습 루프 핵심

기울기 초기화
zero_grad()
    ↓
예측
    ↓
Loss 계산
    ↓
기울기 계산
backward()
    ↓
가중치 업데이트
step()

7. Query Embedding

새로운 문장과 의미가 비슷한 기존 리뷰 Top 3 검색

검색할 Query 준비
    ↓
Query를 Embedding으로 변환
encode()
    ↓
Embedding 정규화
normalize_embeddings=True
    ↓
기존 리뷰 Embedding과 유사도 계산
@
    ↓
유사도 순서의 인덱스 구하기
argsort()
    ↓
큰 값부터 나오도록 순서 뒤집기
[::-1]
    ↓
상위 3개 선택
[:3]
    ↓
해당 위치의 리뷰 가져오기
iloc[]
    ↓
review / score / label / similarity 출력
print()

파운데이션 모델은 ****대량의 데이터를 기반으로 사전학습된 대규모 AI 모델로, 다양한 작업에 범용적으로 활용할 수 있는 기초 역할을 한다.

새로운 태스크를 해결할 때 자세한 설명(프롬프트)을 입력하는 것만으로도 별도의 학습 없이 다양한 작업을 수행할 수 있다.

파운데이션 모델의 3가지 구성요소

1. 빅데이터
   • 인터넷을 통해 활용 가능한 데이터가 크게 증가
   • 딥러닝 기반 AI 모델은 대규모 데이터를 학습하면서 다양한 패턴을 학습할 수 있음
2. 자가 학습 알고리즘
   • 사람이 모든 데이터에 직접 정답을 붙이지 않아도 학습 가능
   • 대량의 데이터 자체를 이용해 학습
3. 어텐션 기반 트랜스포머 모델
   • 어텐션을 통해 데이터 간의 관계와 문맥을 파악
   • 대규모 데이터를 효율적으로 학습할 수 있는 신경망 구조

2. 텍스트 파운데이션 모델이란?

대규모 텍스트 데이터를 사전학습해서 다양한 자연어 처리 작업에 활용할 수 있는 파운데이션 모델이다.

초기 언어 모델의 발전

• GPT-1, BERT
  • 대규모 텍스트로 사전학습
  • 새로운 태스크를 수행하려면 태스크별 Fine-Tuning이 필요했다.
• GPT-2
  • 별도의 추가 학습 없이도
  • 텍스트 지시나 문맥만으로 새로운 태스크를 어느 정도 수행 가능하다.

→ 사전학습 + Fine-Tuning 방식에서 프롬프트만으로도 다양한 태스크를 수행하는 방향으로 발전하였다.

텍스트 파운데이션 모델의 특이점

1. 규모의 법칙
   • 더 많은 데이터, 큰 모델, 긴 학습 → 더 좋은 성능
2. 창발성
   • 모델의 규모가 일정 수준 이상 커지면서 작은 모델에서는 나타나지 않던 새로운 능력이 나타나는 현상
   • 예: 추론, 복잡한 질문 해결 등

3. 거대 언어 모델의 학습

다음 토큰 예측 기반으로 학습된 거대 언어 모델의 한계는 사용자의 의도와 맞지 않거나, 잘못되거나 유해한 응답을 생성할 수 있다는 것이다.

이를 보완하기 위해 정렬 학습(Alignment Training)을 수행한다.

정렬 학습은 거대 언어 모델의 출력이 사용자의 의도와 인간의 가치에 더 잘 부합하도록 학습하는 과정이다.

• 지시 학습(Instruction Tuning)
  • 주어진 지시에 대해 적절한 응답을 생성하도록 학습한다.
• 선호 학습(Preference Learning)
  • 여러 응답 중 사람이 더 선호하는 응답을 생성하도록 학습한다.

1. 지시 학습

• 학습 방법 자체는 기존 언어 모델에서 사용하던 지도 추가 학습(Supervised Fine-Tuning)과 유사하다.
• 기존 언어 모델은 보통 각 태스크마다 별도의 데이터로 Fine-Tuning을 수행했다.
• 반면 지시 학습은 다양한 태스크의 지시문과 정답 예시를 함께 학습하여, 하나의 모델이 여러 지시를 수행할 수 있도록 한다.

기존 파인튜닝 방식

리뷰 → 감정 분석용 모델 → 부정적 (0)

지시 학습 방식

지시 + 리뷰 → 언어 모델 → "부정적으로 보입니다.”

지시 학습 데이터 구성

• 기존 NLP 태스크 데이터를 지시 + 입력 → 응답 형태로 변환하여 지시 학습에 사용한다.
• 같은 태스크도 여러 형태의 자연어 지시문(Template)으로 표현하여 학습 데이터의 다양성을 높인다.
• 이를 통해 표현 방식이 달라져도 지시의 의미를 이해하고 수행할 수 있도록 한다.
• 추론, 감정 분석, 질의응답, 번역, 요약 등 다양한 종류의 NLP 태스크 데이터를 함께 활용한다.
• 학습에서 보지 못한 지시에 대한 일반화 성능을 평가하기 위해 일부 태스크는 학습에서 제외하고 테스트에만 사용하기도 한다.
  • 예: 요약 태스크를 학습 데이터에서 제외한 뒤 테스트 단계에서 평가

2. 선호 학습

선호 학습(Preference Learning)은 여러 응답 중 사람이 더 선호하는 응답을 학습하여, 모델이 사용자의 의도와 가치에 더 잘 맞는 답변을 생성하도록 하는 학습 방식이다.

• 같은 질문에 대해 모델이 여러 개의 응답을 생성한다.
• 사람이 응답들을 비교하여 어떤 응답이 더 좋은지 선호도를 표시한다.
• 모델은 이러한 선호 데이터를 학습하여 더 선호되는 응답을 생성하도록 조정된다.

선호 학습 방식

질문 → 여러 응답 생성 → 사람이 더 좋은 응답 선택 → 선호 데이터로 학습

예를 들면,

질문: 파이썬 리스트를 설명해줘.

응답 A: 간단하고 정확하게 설명
응답 B: 틀린 내용이 포함된 설명

사람의 선택 → 응답 A 선호
                    ↓
              모델이 이를 학습

이를 통해 모델은 단순히 다음 토큰을 잘 예측하는 것을 넘어,

• 더 정확한 응답
• 사용자의 의도에 맞는 응답
• 유해하지 않은 응답
• 사람이 선호하는 형태의 응답

을 생성하도록 학습한다.

InstructGPT 학습 과정(RLHF)

1. 지시 학습(SFT): 사람이 작성한 좋은 답변으로 모델을 학습
2. 보상 모델(RM) 학습: 여러 응답을 사람이 비교·평가하여 선호도를 학습
3. 강화 학습: 보상 모델이 높은 점수를 주는 응답을 생성하도록 추가 학습

지시 학습 vs 선호 학습

• 지시 학습: 이 지시에는 어떤 답을 해야 하는가?
• 선호 학습: 여러 답 중 어떤 답이 더 좋은가?

3. 디코딩 알고리즘

1. 자동회귀 생성

앞에서 생성한 토큰들을 바탕으로 다음 토큰을 하나씩 예측해서 문장을 만들어가는 방식이다.

예시

나는
↓
나는 오늘
↓
나는 오늘 학교에
↓
나는 오늘 학교에 간다

• 모델은 이전 토큰들을 바탕으로 다음 토큰의 확률을 계산한다.
• 계산된 확률을 기반으로 다음 토큰을 선택하는 방법을 디코딩(Decoding) 알고리즘이라고 한다.
• 생성된 토큰을 다시 입력으로 사용하여 다음 토큰을 계속 예측한다.
• EOS(종료 토큰)가 생성되거나 최대 토큰 수에 도달하면 생성을 종료한다.

Greedy Decoding

매 순간 확률이 가장 높은 토큰 하나를 선택해서 다음 토큰으로 생성하는 방법이다.

• 장점: 간단하고 빠르다.
• 단점: 현재 단계에서 가장 높은 확률만 고려하므로 전체 문장 기준으로 최선의 결과가 아닐 수 있다.

Beam Search

확률이 높은 K개의 후보(Beam Size)를 동시에 유지하면서, 누적 확률이 높은 문장을 탐색하는 방식이다.

• Greedy와 달리 여러 후보 경로를 동시에 고려한다.
• 각 단계의 확률뿐 아니라 전체 후보 문장의 누적 확률을 고려한다.
• 장점: Greedy보다 더 좋은 문장을 찾을 가능성이 높다.
• 단점: 후보를 여러 개 유지하므로 계산 비용이 증가한다.

Sampling

모델이 계산한 다음 토큰의 확률 분포에 따라 무작위로 토큰을 선택하는 방식이다.

예

green 50%
red   30%
blue  10%
...

가장 높은 green만 고르는 것이 아니라 각 확률에 따라 랜덤하게 선택한다.

• 장점: 다양한 응답을 생성할 수 있다.
• 단점: 낮은 확률의 토큰도 선택될 수 있어 응답 품질이 떨어질 수 있다.

Temperature Sampling

Temperature(T)를 이용해 다음 토큰의 확률 분포를 조절하는 Sampling 방식이다.

• T < 1
  • 확률 분포가 더 뾰족해짐(Sharpen)
  • 확률이 높은 토큰에 더 집중
  • 안정적인 응답
  • 대신 다양성이 감소
• T > 1
  • 확률 분포가 더 평평해짐(Smooth)
  • 다양한 토큰이 선택될 가능성이 증가
  • 다양한 응답 생성
  • 대신 품질이 불안정해질 수 있음

Temperature 낮음 → 안정적 / Temperature 높음 → 다양함

Top-K Sampling

확률이 높은 상위 K개의 토큰만 후보로 남긴 뒤, 그 후보 중에서 확률에 따라 Sampling하는 방식이다.

전체 토큰
   ↓
확률 높은 상위 K개만 선택
   ↓
K개 중 확률에 따라 랜덤 선택

• 장점: 확률이 매우 낮은 이상한 토큰을 제외할 수 있다.
• 단점: 확률 분포의 모양과 관계없이 항상 고정된 K개의 후보만 사용한다.
  • 문맥마다 다음 토큰의 확률 분포가 다른데 이를 유연하게 반영하지 못할 수 있음.

디코딩 알고리즘 별 장단점 요약

4. 프롬프트 엔지니어링

• 어떻게 지시를 주는지, 어떤 예시를 보여주는지가 거대 언어 모델의 성능에 큰 영향을 미친다.
• 입력 프롬프트에는 지시, 예시, 사용자 입력(질문) 등이 포함될 수 있다.

프롬프트 엔지니어링이란 원하는 답변을 얻기 위해 모델에 주어지는 입력(프롬프트)을 설계하고 조정하는 기법이다.

프롬프트의 구성

프롬프트 = 시스템 프롬프트 + 유저 쿼리 (+ 예시, 문맥 등)

• 시스템 프롬프트(System Prompt)
  • 사용자의 개별 질문과 별개로 모델에게 미리 주어지는 기본 지시사항
  • 모델의 역할, 답변 방식, 규칙 등을 설정한다.
  • 모델을 다시 학습시키는 것이 아니라 답변 생성 시 모델의 행동을 제어한다.
• 유저 쿼리(User Query)
  • 사용자가 실제로 모델에게 입력하는 질문이나 요청을 입력한다.

예시

시스템 프롬프트:
"너는 Python을 초보자에게 쉽게 설명하는 선생님이다."

유저 쿼리:
"리스트가 뭐야?"

→ 그러면 모델은 Python 초보자에게 설명하는 선생님이라는 기본 지시를 따르면서 사용자의 질문에 답을 한다.

Chain-of-Thought(CoT) 프롬프팅

정답 예시만 보여주는 것이 아니라, 정답에 도달하는 추론 과정까지 예시에 포함하는 프롬프팅 방식이다.

일반 프롬프팅

질문
→ 정답

CoT 프롬프팅

질문
→ 풀이/추론 과정
→ 정답

0-shot CoT

별도의 추론 예시 없이, 단계적 추론을 유도하는 지시만으로 모델의 추론 능력을 끌어내는 프롬프팅 방식

예시

질문
→ "단계적으로 생각해보자" 같은 추론 유도 지시
→ 풀이/추론 과정
→ 정답

4. 거대 언어 모델의 평가

1. 평가

구축한 시스템이 실제로 잘 동작하는지 확인하는 단계이다.

• 평가의 3가지 요소
  • 목표: 시스템으로 무엇을 달성하고자 하는지
  • 평가 방법: 어떤 방법으로 평가할 것인지
  • 평가 지표: 어떻게 성공 여부를 판단할 것인지

거대 언어 모델 평가의 특징

특정 테스크에서 학습된 기존 AI 모델들과 달리, 거대 언어 모델은 하나의 모델로 다양한 태스크를 수행할 수 있다.

• 거대 언어 모델의 성능을 올바르게 평가하기 위해서는 많은 테스크에서의 성능을 종합적으로 판단 해야한다.
• 디코딩 알고리즘, 입력 프롬프트에 따라 같은 질문에 대해서도 예측이 바뀌므로, 공평한 비교를 위해서는 해당 부분도 고려해야한다.

평가 방법의 종류

1. 정답이 정해진 경우
   • 평가 방법: 예측과 정답을 비교해 일치도를 측정한다. → 정확도
2. 정답이 정해져 있지 않은 경우
   • 평가 방법 1: 사람이 임의의 정답을 작성 및 이와 예측을 비교한다.
   • 평가 방법 2: 정답과 무관하게 생성 텍스트 자체의 품질만을 측정한다.
   • 평가 방법 3: 생성된 텍스트의 상대적 선호를 평가한다.

언어 모델을 활용한 평가

LLM을 평가자(Judge)로 사용하여 생성된 답변의 품질을 평가하는 방법이다.

• LLM-as-Judge: LLM을 평가자로 쓰는 평가 방법이다.

  • 위치 편향: 특정 위치의 응답을 상대적으로 선호한다.

  • 길이 편향: 품질과 무관하게 길이가 긴 응답을 선호한다.

  • 자기 선호 편향: 생성 모델이 평가 모델과 같은 경우 선호한다.

    → 위와 같은 몇가지 한계점을 가지고 있다.

• G-Eval: LLM-as-Judge 계열의 구체적인 평가 방식/프레임워크다.

• LLaMA 3: 언어 모델

  • 학습 데이터 필터링 등에서 LLM 기반 평가 아이디어가 활용된 사례로 나온 것 이다.

    → 그러나 높은 평가 비용 및 시간을 필요로 한다.

2. 거대 언어 모델의 응용 및 한계

멀티 모달 파운데이션 모델

멀티모달 파운데이션 모델은 이미지·오디오·비디오 등 다양한 모달리티를 LLM이 이해할 수 있는 표현으로 변환해 함께 처리하도록 확장한 모델이다.

이미지와 텍스트를 LLM이 같이 처리하는 과정

이미지 Xᵥ
   ↓
Vision Encoder
   ↓
이미지 특징 Zᵥ
   ↓
Projection W
   ↓
LLM이 이해할 수 있는 이미지 표현 Hᵥ
                     ↘
                      Language Model
                     ↗
텍스트 질문 Xq → 텍스트 표현 Hq
                      ↓
                 최종 답변 Xa

합성 데이터 생성

실제 데이터를 직접 수집하지 않고, 모델이나 규칙을 이용해 인공적으로 새로운 학습 데이터를 생성하는 방법이다.

환각

사실과 다르거나 전적으로 지어낸 내용임에도 불구하고, 정확한 정보와 비슷한 자신감과 유창함으로 응답을 생성하는 현상이다.

• 사전학습 데이터에 최신 정보가 없거나, 학습 데이터가 부족·불완전한 경우 등이 환각의 원인이 될 수 있다.

탈옥

프롬프트 엔지니어링을 이용해 거대 언어 모델의 안전 규칙이나 정렬을 우회하여, 원래 제한된 응답을 생성하도록 유도하는 방법이다.

• 여러 단계의 학습 과정에서 기인한 근본적인 한계 때문에 발생했으며, 다양한 탈옥/방어 방법이 활발히 탐구 중 이다.

예시 (DAN 프롬프팅)

AI 텍스트 검출

거대 언어 모델의 무분별한 사용이 학교 및 회사에서 여러가지 새로운 문제를 만들고 있다.

실제 뉴스

사전학습은 대규모 데이터 셋을 이용해, 모델이 데이터의 일반적인 특징과 표현을 학습하도록 하는 과정이다.

2. Encoder 모델

• 양방향 문맥을 모두 활용하기 때문에, 전통적인 언어모델과는 차이점이 있다.

1. BERT의 학습 방법 - Masked LM

1. 입력 토큰의 15%를 무작위로 선택한다.
2. [MASK] 토큰 치환 (80%), 랜덤 토큰 치환 (10%), 그대로 두기 (10%)
3. 모델이 마스크 된 단어에만 집중하지 않고, 다양한 문맥 표현을 학습해 더 강건한 표현을 학습할 수 있도록 했다.

2. BERT의 학습 방법 - Next Sentence Prediction (NSP)

1. 입력을 두 개의 연속된 텍스트로 받아, 두번째 문장이 첫번째 문장의 실제 다음 문장인지 여부를 예측하는 NSP를 수행했다.

2. 예시

   • 자연어 추론

   • Paraphrase detection

   • 질의 응답

     문장 A + 문장 B
           ↓
     B가 A의 실제 다음 문장인가?
           ↓
     Yes / No

3. BERT의 다운스트림 태스크

BERT는 MLM과 NSP 두 가지 태스크를 이용해 사전학습한다.

1. MLM → 가려진 단어를 주변 문맥을 이용해 예측
2. NSP → 두 번째 문장이 첫 번째 문장의 실제 다음 문장인지 예측
3. [CLS] → 문장 전체의 정보를 대표하는 특수 토큰으로 사용

BERT의 다운스트림 태스크 - Sentence Level

• 두 문장 관계 분류 태스크
  • MNLI
    • 전제: 여러 남자들이 뛰고 있는 축구 경기
    • 가설: 몇몇 남자들이 스포츠를 하고 있다.
    • 분류: {함의, 모순, 중립}
  • QQP
    • Q1: 주식 투자 방법은 어디서 배울 수 있나요?
    • 주식에 대해 더 배우려면 어떻게 해야 하나요?
    • 분류: {중복, 비중복}
• 단일 문장 분류 태스크
  • SST2
    • 문장: 이 영화에는 재미있는 요소들이 풍부하다.
    • 분류: {긍정, 부정}
• QA 태스크
  • SQuAD
    • 질문: 두산 베어스와 LG 트윈스는 서울시의 어느 경기장에서 경기를 하나요?
    • 문맥: 두 팀은 서울 송파구의 잠실야구경기장에서 홈 경기를 합니다.
    • 정답: 잠실야구경기장

4. BERT의 한계

1. 인코더 기반 모델인 BERT는 주어진 입력을 잘 이해하도록 학습되지만, 시퀀스를 생성해야 하는 태스크에는 적합하지 않다.
2. 생성 태스크에서는 autoregressive하게, 즉 한번에 한 단어씩 생성해야 하는데, 이를 자연스럽게 수행하지 못하기 때문에, 생성 태스크엔 디코더 기반 모델을 주로 사용한다.

3. Encoder - Decoder 모델

1. T5

1. T5는 Google Research에서 공개한 모델로 Transformer Encoder - decoder 구조 기반의 모델이다.
2. 모든 태스크를 Text - to - Text 포맷으로 변환해 하나의 모델로 학습했다.

T5의 학습 방법 - Span Corruption

1. Encoder - Decoder 구조에서는 Encoder가 입력 문장을 모두 보고, 그 정보를 바탕으로 Decoder가 출력을 생성한다.
2. 따라서 학습을 위해 Span Corruption이라는 과정을 수행한다.

즉, Span Corruption = 한 단어씩 가리는 것이 아니라 연속된 여러 토큰 구간(Span)을 가리고, Decoder가 그 내용을 생성하도록 학습하는 방법이다.

T5의 다운스크림 태스크

1. T5는 NLU, QA, 요약, 변역 등의 태스크에서 모두 좋은 성능을 보여 범용적으로 활용될 수 있는 모델임을 입증하였다.

4. Decoder 모델

1. Decoder의 Fine-tuning

Transformer의 Decoder는 사전학습 단계에서 다음 단어 예측(Next Token Prediction) 을 학습한다.

즉,

나는 오늘 학교에 → 간다

처럼 현재까지의 단어를 보고 다음 단어를 예측하는 방식으로 학습한다.

생성 태스크에서 활용

• 사전학습에서 사용한 것과 동일하게 다음 단어를 계속 생성하는 방식으로 Fine-tuning한다.
• 따라서 출력이 문장이나 시퀀스 형태인 태스크에 자연스럽게 적합하다.

예시)

• 대화
• 질의응답(QA)
• 문장 생성

분류 태스크에서 활용

분류 문제에서는 Decoder의 출력 위에 새로운 Linear Layer를 연결해 Classifier로 사용한다.

Decoder
   ↓
Hidden State
   ↓
Linear Layer
   ↓
분류 결과

• 새로 추가한 Linear Layer는 처음부터 학습한다.
• Fine-tuning 과정의 Gradient는 Decoder 전체에도 전달되어 함께 학습된다.

2. GPT-1

GPT-1은 Transformer의 Decoder 구조를 기반으로 만든 사전학습 언어 모델이다.

• 2018년 OpenAI에서 공개하였다.
• Autoregressive Language Model 방식으로 사전학습되었다.
• 왼쪽에서 오른쪽으로 이전 단어들을 보고 다음 단어를 예측한다.

예시)

나는 → 오늘 → 학교에 → 간다
                     ↑
               다음 단어 예측

GPT-1 = Transformer Decoder + Autoregressive Next Token Prediction

3. GPT-1의 Fine-tuning

GPT-1은 다운스트림 태스크를 학습할 때도

기존의 다음 단어 예측 학습 목표를 최대한 유지하면서 Fine-tuning한다.

분류 태스크 예시 - NLI

NLI(Natural Language Inference)는 두 문장의 관계를 분류하는 문제이다.

예시)

• 전제(Premise): The man is in the doorway.
• 가설(Hypothesis): The person is near the door.
• 분류: Entailment(함의)

분류 종류:

• Entailment : 함의
• Contradiction : 모순
• Neutral : 중립

GPT-1에서는 입력 문장 사이에 특수 토큰을 추가한다.

[START] 문장1 [DELIM] 문장2 [EXTRACT]

• [START] → 입력 시작
• [DELIM] → 두 문장을 구분
• [EXTRACT] → 분류에 사용할 위치

[EXTRACT] 위치의 Hidden State에 Classifier를 연결하여 최종 분류를 수행한다.

5. 정리

• Decoder → 이전 단어를 보고 다음 단어를 예측
• 생성 태스크 → 다음 단어를 계속 생성하는 방식이라 자연스럽게 적합
• 분류 태스크 → Decoder 위에 Classifier를 추가하여 Fine-tuning
• GPT-1 → Transformer Decoder 기반의 Autoregressive 언어 모델
• GPT-1 Fine-tuning → 다음 단어 예측 능력을 유지하면서 다양한 태스크에 적용

1. 왜 RNN 없이 Attention을 사용하는가?

RNN은 이전 시점의 hidden state를 다음 시점으로 전달하면서 단어를 순서대로 처리한다.

단어1 → 단어2 → 단어3 → 단어4
  h1  →  h2  →  h3  →  h4

하지만 Attention을 사용하면 멀리 떨어진 단어의 정보도 직접 참고할 수 있다.

그렇다면 RNN처럼 정보를 순서대로 전달하지 않고, Attention만으로 단어 간 관계를 계산할 수 있지 않을까?

이러한 아이디어가 Self-Attention으로 이어진다.

2. RNN의 한계

장기 의존성

• RNN은 입력을 왼쪽에서 오른쪽으로 순차적으로 처리한다.
• 멀리 떨어진 두 단어의 관계를 파악하려면 여러 단계를 거쳐야 한다.
• 단어 사이의 거리가 멀어질수록 정보 전달과 학습이 어려워질 수 있다.
• 최대 상호작용 거리는 O(sequence length)이다.

예시)

The chef who ............... was
    ↑                        ↑
    여러 단계를 거쳐야 관계를 파악

병렬화가 어렵다.

• h2를 계산하려면 먼저 h1이 필요하다.
• h3를 계산하려면 먼저 h2가 필요하다.
• 따라서 모든 단어를 동시에 계산하기 어렵다.
• 대규모 데이터 학습에서 GPU를 효율적으로 활용하기 어렵다.

3. Self-Attention

Self-Attention은 같은 문장 안의 단어들이 서로를 직접 참고하여 단어 간 관계를 학습하는 방법이다.

기존 Seq2Seq Attention

Decoder가 단어를 생성할 때 Encoder의 단어들을 참고한다.

Encoder 입력 문장
↓
h1  h2  h3  h4  h5
 \   |   |   |   /
      ↓ 참고
   Decoder
      ↓
   출력 단어

즉,

Decoder → Encoder를 참고

하는 구조이다.

Self-Attention

Self-Attention에서는 같은 문장 안의 단어들이 서로를 참고한다.

단어1 ↔ 단어2 ↔ 단어3 ↔ 단어4
  ↖      ↕       ↕      ↗
      서로 관계 계산

예를 들어

어제 카페 갔었어 거기 사람 많더라

에서 거기라는 단어를 이해하기 위해 같은 문장 안의 카페와 같은 단어를 직접 참고할 수 있다.

즉, 문장 내부의 단어 ↔ 문장 내부의 다른 단어

사이의 관계를 계산하는 것이 Self-Attention이다.

4. Self-Attention의 장점

장기 의존성 처리에 유리

• 멀리 떨어진 단어끼리도 직접 관계를 계산할 수 있다.
• 여러 hidden state를 순서대로 거칠 필요가 없다.
• 최대 상호작용 거리는 O(1)이다.

병렬 처리가 가능

• RNN처럼 이전 단어의 계산이 끝날 때까지 기다릴 필요가 없다.
• 여러 단어의 Attention을 동시에 계산할 수 있다.

단어 간 관계를 직접 학습

• 각 단어가 문장 안의 다른 단어들을 직접 참고한다.
• 현재 단어와 관련성이 높은 단어에 더 집중할 수 있다.

5. Seq2Seq Attention vs Self-Attention

Attention = 다른 시퀀스를 참고

Self-Attention = 자기 자신이 속한 시퀀스 내부를 참고

6. Self-Attention의 Query, Key, Value

Self-Attention에서는 각 단어를 바로 서로 비교하는 것이 아니라, 각 단어를 Query(Q), Key(K), Value(V) 벡터로 변환한다.

Query, Key, Value

Query (Q)

현재 단어가 다른 단어에서 어떤 정보를 찾고 싶은지를 나타내는 벡터

쉽게 말하면:

"나는 지금 어떤 정보를 찾고 있지?"

Key (K)

각 단어가 자신이 어떤 정보를 가지고 있는지를 나타내는 벡터

쉽게 말하면:

"나는 이런 정보를 가지고 있어."

Value (V)

실제로 다른 단어가 참고하게 될 정보를 담고 있는 벡터

쉽게 말하면:

"나를 참고한다면 이 정보를 가져가."

따라서 각 단어마다

단어
 ↓
├─ Query
├─ Key
└─ Value

3개의 벡터가 만들어진다.

Self-Attention 계산 과정

1단계: 각 단어에서 Q, K, V 생성

각 단어를 Query, Key, Value 벡터로 변환한다.

단어 i
  ↓
┌─ qi : Query
├─ ki : Key
└─ vi : Value

2단계: Query와 Key를 비교

현재 단어의 Query와 다른 단어들의 Key를 비교해서 두 단어가 얼마나 관련 있는지 계산한다.

현재 단어의 Query
        ↓
다른 단어들의 Key와 비교
        ↓
    관련성 점수 계산

수식으로는

eᵢⱼ = qᵢᵀkⱼ

• 점수가 크다 → 두 단어의 관련성이 높다.
• 점수가 작다 → 관련성이 낮다.

이 점수에 Softmax를 적용하여 각 단어에 줄 Attention 가중치를 구한다.

αᵢⱼ = softmax(eᵢⱼ)

3단계: Value에서 필요한 정보를 가져온다.

Attention 가중치를 각 단어의 Value에 곱하여 필요한 정보를 가져온다.

oᵢ = Σ αᵢⱼvⱼ

즉,

Query로 필요한 정보 검색
        ↓
Key와 비교해서 관련성 계산
        ↓
관련성이 높은 Value를 많이 가져옴
        ↓
새로운 단어 표현 생성

이라고 이해하면 된다.

7. Self-Attention의 한계

Self-Attention은 단어 간 관계를 효율적으로 계산할 수 있지만 한계도 존재한다.

순서 정보 부족

• Self-Attention은 기본적으로 단어 간 유사도를 계산한다.
• 따라서 단어가 문장에서 몇 번째 위치에 있는지에 대한 순서 정보를 자체적으로 고려하지 않는다.

즉, RNN처럼

단어1 → 단어2 → 단어3

의 순서가 구조 자체에 포함되어 있지 않다.

비선형성 부족

• Attention 계산은 본질적으로 여러 Value를 가중 평균하는 형태이다.
• 따라서 Attention 계산만으로는 복잡한 패턴이나 깊은 표현을 학습하는 데 한계가 있다.

미래 참조 문제

언어 모델은 문장을 왼쪽에서 오른쪽으로 생성해야 한다.

나는 → 오늘 → 학교에 → ?

현재 시점에서는 아직 생성되지 않은 미래 단어를 보면 안 된다.

하지만 Self-Attention은 기본적으로 모든 단어를 동시에 보기 때문에 아직 생성되지 않은 미래 단어까지 참고할 수 있는 문제가 발생한다.

Self-Attention 한계 해결

1. 순서 정보 부족
   • Positional Encoding을 사용하여 각 단어에 위치 정보를 추가한다.
2. 비선형성 부족
   • Feed Forward Network(FFN)와 활성화 함수를 사용하여 복잡한 패턴을 학습한다.
3. 미래 참조 문제
   • Masking(Causal Mask)을 사용하여 현재 시점 이후의 단어를 보지 못하게 한다.

2. Transformer

Transformer는 RNN 없이 Attention을 중심으로 문장의 단어 관계를 처리하는 신경망 아키텍처이다.

1. Multi-Headed Attention

• 문장에서 같은 단어라도 여러 이유 (문법적 관계, 의미적 맥락 등)로 다른 단어에 주목할 수 있다.
• 단일 Self-Attention Head 로는 한가지 관점에서의 단어 간 관계 밖에 파악할 수 없다

→ 따라서 여러 Attention Head를 두어 다양한 관점에서 동시에 정보를 파악한다.

2. Scaled Dot-Product Attention

Self-Attention에서는 Query(Q)와 Key(K)의 내적으로 단어 간 관련성을 계산한다.

하지만 Q와 K의 차원이 커지면 내적값도 너무 커질 수 있고,

Softmax 값이 한쪽으로 지나치게 몰려 학습이 불안정해질 수 있다.

따라서 내적값을 √d_k로 나누어 크기를 조절한다.

Q와 K 내적
    ↓
√d_k로 나눔
    ↓
Softmax
    ↓
Attention 가중치 계산
    ↓
Value에 적용

Scaled Dot-Product = Attention 점수가 너무 커지지 않도록 크기를 조절하는 방법

3. Residual Connection

신경망이 깊어질수록 기울기 소실이나 폭주로 인해 학습이 어려워질 수 있다.

Residual Connection은 Layer를 통과한 결과에 원래 입력값을 다시 더해주는 방법이다.

입력 x
 ├──────────┐
 ↓          │
Layer       │
 ↓          │
결과 + x ←──┘

• 원래 정보를 계속 유지할 수 있다.
• 깊은 신경망에서도 정보와 기울기가 잘 전달되도록 돕는다.

Residual Connection = Layer 결과 + 원래 입력

4. Layer Normalization

신경망의 층이 깊어지면 각 Layer에서 값의 크기가 달라져 학습이 불안정해질 수 있다.

Layer Normalization은 각 Layer의 값을 정규화하여 학습을 안정적으로 만들어준다.

Transformer에서는 Residual Connection과 Layer Normalization을 함께 사용한다.

Add & Norm = Residual Connection + Layer Normalization

5. Transformer Encoder

Encoder에서는 입력 문장이 처음부터 전부 주어진다.

예를 들어

나는 오늘 학교에 간다

라는 문장이 들어오면 모든 단어를 이미 알고 있기 때문에

각 단어가 앞뒤의 모든 단어를 참고할 수 있다.

따라서 Encoder의 Self-Attention에는 Masking을 사용하지 않는다.

• 모든 입력 단어를 서로 참고할 수 있다.
• 앞뒤 문맥을 모두 활용하는 양방향 문맥을 사용한다.

Encoder = Masking 없이 전체 입력 문장을 참고

6. Transformer Decoder

Decoder는 현재까지 생성된 단어를 이용해 다음 단어를 예측한다.

예를 들어

나는 오늘 학교에 ?

에서 다음 단어를 예측할 때 정답인 미래 단어를 미리 보면 안 된다.

따라서 Decoder에서는 Masked Self-Attention을 사용한다.

• 아직 생성되지 않은 미래 단어를 가린다.
• 현재까지 생성된 단어만 이용해 다음 단어를 예측한다.

Decoder = Masking을 이용해 미래 단어를 보지 못하게 함

Decoder 내부에는 Feed-Forward Network도 존재하며,

Attention을 거친 각 단어의 표현을 한 번 더 변환한다.

7. Encoder와 Decoder의 차이

8. Cross-Attention

번역에서는 Decoder가 자기 문장만 봐서는 입력 문장의 내용을 알 수 없다.

따라서 Decoder가 Encoder에서 처리한 입력 문장의 정보도 참고해야 한다.

이때 사용하는 것이 Cross-Attention이다.

Encoder의 출력
      ↓
Cross-Attention
      ↑
   Decoder

Cross-Attention에서는

• Query(Q) → Decoder에서 가져온다.
• Key(K) → Encoder에서 가져온다.
• Value(V) → Encoder에서 가져온다.

즉,

Decoder가 Q를 이용해 Encoder의 K와 비교하고, 필요한 V 정보를 가져오는 방식이다.

9. Transformer의 결과

Neural Machine Translation task에서 당시 최고 성능을 달성했을 뿐 아니라, 가장 효율적인 학습으로 비용까지 절감할 수 있었다.

💡Transformer의 등장은 대부분 최신 모델들이 성능 향상을 위해 사전학습을 결합하도록 했다. 또한 뛰어난 병렬 처리 능력 덕분에 대규모 사전학습에 적합해 NLP 표준 아키텍처로 자리 잡았다.

언어 모델은 인간의 두뇌가 자연어를 생성하는 능력을 모방한 모델이다.

• 앞의 문맥을 바탕으로 다음 단어(토큰)를 예측한다.
• 이러한 예측을 반복하여 자연스러운 문장을 생성한다.

예시

나는 맛있는 사과를
-> 여기까지 들어오면 언어모델은 다음 단어 후보에 점수나 확률을 준다.
...
먹는다   0.70
샀다     0.15
좋아한다 0.08
...

위와 같이 가장 가능성이 높은 단어를 골라서 문장을 이어갈 수 있다.

N-gram 언어모델은?

N-gram은 문장에서 연속된 N개의 단어(또는 문자)를 하나의 묶음으로 보는 방법이다.

예시로

나는 맛있는 사과를 먹는다

• Unigram(1-gram): 한 단어씩
  • 나는, 맛있는, 사과를, 먹는다
• Bigram(2-gram): 두 단어씩
  • 나는 맛있는
  • 맛있는 사과를
  • 사과를 먹는다
• Trigram(3-gram): 세 단어씩
  • 나는 맛있는 사과를
  • 맛있는 사과를 먹는다

언어 모델에서는 이걸 이용해서 앞의 몇 개 단어를 보고 다음 단어를 예측한다.

SMT의 한계

SMT(Statistical Machine Translation)는 대규모 번역 데이터를 바탕으로

단어 또는 구(phrase)의 번역 확률과 언어 모델의 확률을 조합하여 가장 적절한 번역을 선택하는 방식이다.

입력 문장
↓
단어/구 단위 번역 후보 생성
↓
번역 모델 + 언어 모델로 점수 계산
↓
가장 점수가 높은 문장 선택

하지만 다음과 같은 한계가 있다.

1. 긴 문맥을 반영하기 어렵다.
   • 단어나 짧은 구 단위의 통계에 많이 의존하기 때문에 문장 전체의 의미를 파악하기 어렵다.
2. 언어 간 어순 차이를 처리하기 어렵다.
   • 한국어와 영어처럼 문장 구조와 단어 순서가 크게 다른 언어에서는 자연스러운 번역이 어려울 수 있다.
3. 자연스러운 문장 생성에 한계가 있다.
   • 번역 모델과 언어 모델을 따로 사용하기 때문에 문장 전체를 하나의 모델에서 통합적으로 학습하지 않는다.

→ 이러한 한계를 개선하기 위해 신경망을 이용해 문장 전체의 정보를 학습하는 NMT가 등장하였다.

→ NMT의 대표적인 구조가 Seq2Seq(Encoder-Decoder)이다.

2. Seq2Seq

1. NMT (Neural Machine Translation)

NMT는 인공 신경망을 이용해 기계 번역을 수행하는 방법이다.

• 대표적인 신경망 구조로 Seq2Seq(Sequence-to-Sequence)가 있다.
• Seq2Seq는 크게 Encoder와 Decoder로 이루어진다.
• 2014년 Google의 Sequence to Sequence Learning with Neural Networks 논문에서 소개되었다.

2. 번역에서의 문제점

언어마다 문장의 길이가 다를 수 있다.

예시)

• 영어: the black cat drank milk
• 프랑스어: le chat noir a bu du lait

→ 입력 문장과 출력 문장의 길이가 다를 수 있으므로,

NMT에서는 길이가 다른 시퀀스 간의 매핑을 처리할 수 있어야 한다.

3. Seq2Seq의 핵심 아이디어

Seq2Seq는 보통 2개의 LSTM을 이용한다.

Encoder

• 입력 시퀀스를 순서대로 읽는다.
• 입력 시퀀스를 고정된 차원의 벡터 표현으로 만든다.
• 즉, 문장의 정보를 하나의 벡터에 담는다.

Decoder

• Encoder가 만든 벡터를 입력으로 받는다.
• 이 정보를 바탕으로 출력 시퀀스를 생성한다.

4. Seq2Seq 구조

입력 문장
the → black → cat → drank → milk
                ↓
             Encoder
                ↓
        문장 정보 벡터
                ↓
             Decoder
                ↓
le → chat → noir → a → bu → du → lait

5. Seq2Seq의 다양한 적용

1. 요약
   • 긴 길이의 문서를 읽고, 짧은 길이의 문장으로 요약된 텍스트를 출력하는 태스크이다.
2. 대화
   • 사용자의 발화를 기반으로, 맥락에 맞는 대답을 생성하는 태스크이다.
3. 코드 생성
   • 자연어로 작성된 설명 혹은 명령어를 입력 받아, 그에 대응하는 프로그래밍 코드 혹은 쿼리를 출력하는 태스크이다.

6. Seq2Seq 학습 방법

• 인코더와 디코더가 하나의 통합 네트워크로 연결되어 있다.
• 디코더에서 발생한 오차는 역전파 과정을 통해 입력을 처리한 인코드까지 전달되어 전체 네트워크가 End-to-End로 동시에 최적화된다.
• 학습 초반에는 모델의 예측 능력이 떨어져서 학습이 불안정할 수 있다.
• Teacher Forcing 은 모델이 스스로 예측한 단어 대신 정답 단어를 디코더 입력으로 강제로 넣어줌으로써 훨씬 안정적이고 빠르게 학습을 수행하는 방법이다.

7. Seq2Seq의 토큰 출력 방법

• 토큰을 출력하는 방법 중 하나로, 각 단계에서 가장 확률이 높은 단어를 선택한다.
• 하지만 되돌리기가 불가능한 한계가 있다.

3. Attention

1. the bottleneck problem

• 인코더는 입력 문장 전체를 하나의 벡터로 요약하는데, 마지막 hidden state 에 문장의 모든 의미 정보가 담긴다.
• 고정 길이의 벡터 하나에 모든 문장의 의미를 압축하다 보니 정보 손실이 생길 수 있는데, 이것을 the bottleneck problem이라 한다.

2. Attention

Decoder가 출력 단어를 만들 때 Encoder의 마지막 hidden state 하나만 보는 게 아니라, 입력 문장의 여러 hidden state 중 지금 필요한 부분을 골라서 참고하는 방법이다.

기존 Seq2Seq에서는

the → black → cat → drank → milk
 ↓      ↓      ↓      ↓       ↓
h1     h2     h3     h4      h5
                       ↓
                 마지막 h5만 사용
                       ↓
                   Decoder

입력 문장의 정보를 마지막 hidden state 하나에 압축하여 Decoder에 전달하였다.

하지만 Attention은 출력할 단어와 관련 있는 Encoder의 hidden state에 더 높은 가중치를 주어 참고한다.

Encoder
h1   h2   h3   h4   h5
 \    |    |    |    /
  \   |    |    |   /
   ↓  ↓    ↓    ↓  ↓

Decoder에서 y1 만들기
→ h1~h5 중 필요한 곳에 가중치
→ y1 = "le"

Decoder에서 y2 만들기
→ 다시 h1~h5를 보고 다른 가중치
→ y2 = "chat"

Decoder에서 y3 만들기
→ 다시 h1~h5를 보고 다른 가중치
→ y3 = "noir"

그래서 기존 Seq2Seq와 비교하면:

Attention의 효과

1. NMT 성능 향상
   • 디코더가 Encoder의 전체 hidden state를 참고하면서, 현재 출력에 필요한 부분에 더 집중할 수 있다.
2. Bottleneck Problem 완화
   • 기존 Seq2Seq처럼 입력 문장 전체를 하나의 고정된 벡터에 압축할 필요가 없다.
   • Decoder가 Encoder의 여러 hidden states에 직접 접근할 수 있다.
3. Vanishing Gradient Problem 완화
   • 멀리 떨어진 입력 정보에도 Attention을 통해 직접 접근할 수 있다.
   • 정보와 기울기가 전달되는 경로가 짧아져 장기 의존성 학습에 도움이 된다.
4. 해석 가능성
   • Attention 가중치를 통해 Decoder가 특정 단어를 생성할 때 입력 문장의 어느 부분을 많이 참고했는지 확인할 수 있다.

4. 정리

• 언어 모델
  • 앞의 문맥을 바탕으로 다음 단어(토큰)를 예측하여 자연스러운 문장을 생성한다.
  • N-gram은 앞의 일정 개수 단어만 참고하여 다음 단어를 예측한다.
• SMT
  • 단어/구 단위의 번역 확률과 언어 모델을 이용해 가장 적절한 번역을 선택한다.
  • 긴 문맥, 언어 간 어순 차이, 자연스러운 문장 생성에 한계가 있다.
  • 이러한 한계를 개선하기 위해 NMT가 등장하였다.
• NMT
  • 인공 신경망을 이용한 기계 번역 방식이다.
  • 대표적인 구조로 Seq2Seq가 있다.
• Seq2Seq
  • Encoder가 입력 시퀀스를 읽고 문장 정보를 하나의 벡터로 표현한다.
  • Decoder가 Encoder의 정보를 바탕으로 출력 시퀀스를 생성한다.
  • 입력과 출력의 길이가 달라도 처리할 수 있다.
  • Teacher Forcing을 사용하면 학습 시 정답 단어를 Decoder 입력으로 넣어 안정적으로 학습할 수 있다.
• Seq2Seq의 한계
  • 입력 문장 전체 정보를 마지막 hidden state 하나에 압축한다.
  • 문장이 길어질수록 정보 손실이 발생할 수 있는데, 이를 Bottleneck Problem이라 한다.
• Attention
  • Encoder의 마지막 hidden state 하나만 사용하는 것이 아니라 여러 hidden state를 참고한다.
  • Decoder가 각 단어를 생성할 때 필요한 입력 부분에 더 높은 가중치를 준다.
  • Bottleneck Problem과 Vanishing Gradient Problem을 완화하고 NMT 성능을 향상시킨다.
  • Attention 가중치를 통해 모델이 입력 문장의 어느 부분에 집중했는지 확인할 수 있다.

전체 흐름

언어 모델

→ SMT

→ SMT의 한계

→ NMT

→ Seq2Seq(Encoder-Decoder)

→ Bottleneck Problem

→ Attention으로 필요한 입력 부분에 집중

1. 원 핫 인코딩이란?

문자로 된 범주형 데이터를 머신러닝이 이해할 수 있도록 0과 1로 바꾸는 방법이다.

원 핫 인코딩의 문제점

예시) 웹 검색

• 갤럭시 핸드폰 == 갤럭시 스마트폰

1. 차원의 저주
   • 차원이 커지면 커질수록 데이터가 점점 더 희소해져 활용이 어렵다.
   • 고차원의 희소 벡터를 다루기 위해서는 많은 메모리가 필요하다.
2. 의미적 정보 부족
   • 비슷한 단어라도 유사한 벡터로 표현되지 않는다.
   • 예시)
     • 은행 과 금융 은 의미적으로 비슷하지만, 원 핫 인코딩에서는 전혀 무관한 벡터이다.

2. 워드 임베딩

단어를 그냥 0과 1로 표현하는 게 아니라, 단어의 의미와 관계를 담은 여러 숫자의 벡터로 바꾸는 방법이다.

현대 통계적 자연어처리에서의 가장 성공적인 아이디어 중 하나이다.

원 핫 인코딩에서는 은행과 금융이 완전 독립적인 벡터로 표현되었지만, 워드 임베딩에서는 두 단어의 벡터가 서로 가깝게 위치하며, 이를 통해 의미적 유사성을 반영할 수 있다.

Skip-grams (SG)

• 중심 단어를 통해 주변 단어들을 예측하는 방법이다.
• 단어의 위치 (앞/뒤)에 크게 구애 받지 않는다.

Continuous Bag of Words (CBOW)

• 주변 단어들을 통해 단어를 예측하는 방법이다.
• 문맥 단어들의 집합으로 중심 단어를 맞춘다.

예시

예를 들어 문장이 나는 맛있는 사과를 먹었다 라고 해보자.

SG는 중심 단어 → 주변 단어 예측

      "사과를"
         ↓
맛있는, 먹었다 등 예측한다.

사과를이라는 단어 주변에는 어떤 단어들이 자주 나오지?

CBOW는 주변 단어 → 중심 단어 예측

나는, 맛있는, 먹었다
        ↓
     "사과를" 예측한다.

주변에 이런 단어들이 있는데 가운데 들어갈 단어가 뭐지?

2. 순차적 데이터

데이터가 입력되는 순서와 이 순서를 통해 입력되는 데이터들 사이의 관계가 중요한 데이터이다.

특징

1. 순서가 중요하다.
   • 데이터의 순서가 바뀌면 의미가 달라진다.
2. 장기 의존성
   • 멀리 떨어진 과거의 정보가 현재/미래에 영향을 준다.
3. 가변 길이
   • 순차 데이터는 길이가 일정하지 않고, 단어 수도 제각각이다.

따라서 순차적 데이터를 처리하려면 일반적인 모델들 (선형 회귀, MLP 등)로는 불가능하다.

그래서 Sequential Models 이 필요하다.

RNN, LSTM, Transformer 등등…..

3. RNN

전통적인 인공신경망 (MLP, CNN)들은 고정된 길이의 입력을 받아 가변 길이의 데이터를 처리하기에 적합하지 않다. 하지만

RNN은 가변 길이의 입력을 받을 수 있고, 이전 입력을 기억할 수 있기 때문에, 순차적 데이터 처리에 적합한 아키텍처이다.

RNN 처리 방식

x₁ = "나는"
↓
h₁ = "나는"까지 기억

x₂ = "맛있는"
↓
h₂ = "나는 맛있는"까지 기억

x₃ = "사과를"
↓
h₃ = "나는 맛있는 사과를"까지 기억

x₄ = "먹는다"
↓
h₄ = 문장 전체 정보 기억

RNN 아키텍처

• 전통적인 신경망과 달리 RNN은 이전 시점의 정보를 담는 hidden state 를 가지고 있다.
• 따라서, 입력 시퀀스 벡터 x를 처리할 때, 각 시점마다 recurrence 수식 을 적용하여 hidden state 를 업데이트한다.

RNN의 가장 기본적인 개념식

현재 기억 = 이전 기억 + 현재 입력을 이용해서 계산한 결과

• xt: 현재 입력
• ht: 현재 hidden state, 즉 현재까지 기억한 정보
• W: 가중치(weight), 입력이나 hidden state를 얼마나 반영할지 조절
• yt: 현재 출력

RNN의 특징

1. 한 번에 하나의 요소를 처리하고, 정보를 앞으로 전달한다.
2. 각 층이 하나의 시점을 나타내는 깊은 신경망처럼 보인다.
3. hidden state 를 유지하면서, 가변 길이 데이터를 처리할 수 있다.
4. 출력은 과거 입력에 영향을 받는다는 점에서 feedforward 신경망과 다르다.

RNN의 한계: 기울기 소실 문제

기울기 소실 문제란? 딥 러닝에서 역전파 시 앞쪽 층의 기울기가 0에 가까워져서 장기 의존성 학습이 어려워지는 현상

1. 역전파 과정에서 작은 값들이 계속 곱해진다.
2. 과거 시점에서 온 오차 신호는 갈수록 더 작은 기울기를 갖게 된다.
3. 결국 파라미터들이 장기 의존성은 학습하지 못하고, 단기 의존성만 포착하게 된다.

4. LSTM이란?

기울기 소실 문제를 해결하기 위해, 1997년에 제안된 RNN의 한 종류이다.

LSTM의 특징

1. RNN처럼 hidden state 만 두는 것이 아니라 cell state 도 가진다.
   • hidden state 는 외부로 보여주는 정보, 즉 현재 출력에 가까운 상태
   • cell state 는 여러 시점을 지나면서 유지되는 장기 기억 저장소
2. LSTM은 cell state에서 정보를 읽고, 지우고, 기록한다.

3가지 게이트를 통해 어떤 정보를 지우고, 쓰고, 읽을지 결정한다.

게이트의 동작은 매 시점마다 각 요소가 열림(1), 닫힘(0), 혹은 그 사이의 값으로 설정된다.

• Forget gate: 이전 cell state에서 무엇을 버리고 무엇을 유지할지 결정한다.
• Input gate: 새 정보 중 얼마나 cell state에 쓸지 결정한다.
• Output gate: cell state 중 얼마나 hidden state로 내보낼지 결정한다.

LSTM 처리 방식

x₁ = "나는"
↓
h₁ = 현재 사용할 기억
c₁ = 장기적으로 저장할 기억

x₂ = "맛있는"
↓
h₂ = "나는 맛있는"을 바탕으로 한 현재 기억
c₂ = 중요한 정보를 계속 저장

x₃ = "사과를"
↓
h₃ = 현재 시점에서 사용할 기억
c₃ = 앞의 중요한 정보 유지

x₄ = "먹는다"
↓
h₄ = 현재 기억
c₄ = 문장 전체에서 유지할 장기 기억

정리

• 원 핫 인코딩은 범주형 데이터를 0과 1로 표현하는 방법이다.
  • 차원이 커질수록 희소해지고 메모리 사용량이 커진다.
  • 단어 사이의 의미적 유사성을 표현하기 어렵다.
• 워드 임베딩은 단어의 의미와 관계를 반영해 숫자 벡터로 표현하는 방법이다.
  • 비슷한 의미의 단어는 벡터 공간에서도 가깝게 표현될 수 있다.
  • Skip-Gram: 중심 단어 → 주변 단어 예측
  • CBOW: 주변 단어 → 중심 단어 예측
• 순차적 데이터는 데이터의 순서와 앞뒤 관계가 중요한 데이터이다.
  • 순서가 중요하다.
  • 장기 의존성이 존재할 수 있다.
  • 입력 길이가 일정하지 않을 수 있다.
• RNN은 이전 시점의 정보를 hidden state에 저장하면서 순차 데이터를 처리하는 신경망이다.
  • 현재 입력과 이전 hidden state를 이용해 새로운 hidden state를 만든다.
  • 가변 길이 데이터를 처리할 수 있다.
  • 오래된 정보를 학습하기 어려운 기울기 소실 문제가 있다.
• LSTM은 RNN의 기울기 소실 문제를 완화하기 위해 만들어진 모델이다.
  • hidden state: 현재 시점에서 사용하는 정보
  • cell state: 장기적으로 유지하는 정보
  • Forget gate: 불필요한 정보를 버린다.
  • Input gate: 새로운 정보를 저장한다.
  • Output gate: 필요한 정보를 출력한다.

전체 흐름

원 핫 인코딩의 한계

→ 워드 임베딩으로 의미 표현

→ 순차 데이터 처리 필요

→ RNN 사용

→ RNN의 장기 의존성 문제

→ LSTM으로 개선

1. 비지도 학습이란?

• 정의: 레이블 (정답) 없이 데이터의 구조/패턴/집단을 찾아내는 학습이다.
• 대표 과제: 군집화, 차원축소, 밀도추정/이상치 탐지 등등
• 출력: 정답 예측이 아니라 구조/요약/표현이다.

2. 비지도 학습 vs 지도 학습

• 지도 학습: 입력 + 라벨 (정답)로 예측 모델을 학습한다.
  • 가격 예측, 악성 종양 예측 등
• 비지도 학습: 입력만으로 구조 학습을 한다.
  • 고객 세그먼트 등

2. 클러스터링

1. 클러스터링이란?

데이터 안에서 하위 집단 (클러스터)을 찾는 기법들의 총칭이다.

집단 내부는 유사, 집단 간은 상이하도록 데이터를 분할한다.

클러스터링 예시

• 마케팅 세그먼테이션
  • 다수의 지표 (가구 소득, 직업, 도심 거리 등)를 가진 많은 사람들에 대해 특정 광고/상품에 더 반응할 하위집단을 식별하고자 한다.
  • 시장 세분화 작업 자체가 클러스터링에 해당한다.

2. 두 가지 대표 클러스터링 기법

1. K-평균 (K-means): K (클러스터 수)를 미리 정해 분할한다.
2. 계층적 군집: K를 사전에 고정하지 않는다.

3. K-means 클러스터링

1. K-means 클러스터링

• 패널: K=2, 3, 4에서 각 K-means 결과 (점 색상 = 할당된 클러스터)
• 클러스터 결과에서 특정 색상은 의미가 없고, 점들이 다른 색이라는 것은 서로 다른 클러스터에 속해있다는 의미이다.

예시

2. K-means 표기 (군집 집합)

K-means는 전체 데이터를 K개의 군집으로 나누는 방법이다.

각 군집은 다음처럼 표현할 수 있다.

C₁, C₂, ..., Cₖ

• K: 만들 군집의 개수
• C₁, C₂, ..., Cₖ: 각각의 군집
• 모든 데이터는 반드시 하나의 군집에 속한다.
• 하나의 데이터가 여러 군집에 동시에 속할 수는 없다.
• 서로 다른 군집은 겹치지 않는다.
• 모든 군집을 합치면 전체 데이터가 된다.

3. K-means 알고리즘

1. 초기화: 관측치들에 무작위로 1...K 클러스터를 임시로 부여한다.
2. 반복 (할당이 더 이상 바뀌지 않을 때 까지)
   • 각 클러스터의 중심 계산
   • 각 관측치를 가장 가까운 중심의 클러스터에 재할당 (거리 예 = 유클리드)

K-means 알고리즘 특성

1. 중심점과의 평균 거리가 계속 줄어들기 때문에 매 반복마다 결과는 더 좋아진다.

2. 하지만 최적 해를 항상 찾는 건 아니다.

   → 초기값에 따라 지역 최솟값으로 수렴 가능하다. (지역 최소값문제라고 부른다.)

┌────────────────────────────┐
│ 1 무작위 클러스터 초기화  │
└────────────────────────────┘
              ↓
┌────────────────────────────┐
│ 2a 중심 계산               │◀──────────┐
└────────────────────────────┘           │
              ↓                          │ 반복
┌────────────────────────────┐           │
│ 2b 클러스터 재배정         │───────────┘
└────────────────────────────┘
              ↓
     클러스터 변화가 없으면 종료

4. K-means 클러스터링에서 초기값의 영향

서로 다른 초기 라벨에서 최종 분할과 목표값 (패널 상단 숫자)이 달라진다.

초기화의 중요성: 여러 번 시도를 권장한다.

4. 계층적 군집

1. K-means 클러스터링 vs 계층적 군집

• K-means는 클러스터 수 K를 미리 지정해야 하는 단점이 존재한다.
• 계층적 군집은 K를 고정하지 않고 전체 구조를 덴드로그램으로 제공한다.

2. 계층적 군집 예시

• 덴드로그램에서 수평선 높이 (거리)를 기준으로 가위질하여 K개 군집을 얻는다.

2. K-means 표기 (군집 집합)

K-means는 전체 데이터를 K개의 군집으로 나누는 방법이다.

각 군집은 다음처럼 표현할 수 있다.

C₁, C₂, ..., Cₖ

• K: 만들 군집의 개수
• C₁, C₂, ..., Cₖ: 각각의 군집
• 모든 데이터는 반드시 하나의 군집에 속한다.
• 하나의 데이터가 여러 군집에 동시에 속할 수는 없다.
• 서로 다른 군집은 겹치지 않는다.
• 모든 군집을 합치면 전체 데이터가 된다.

3. K-means 알고리즘

1. 초기화: 관측치들에 무작위로 1...K 클러스터를 임시로 부여한다.
2. 반복 (할당이 더 이상 바뀌지 않을 때까지)
   • 각 클러스터의 중심 계산
   • 각 관측치를 가장 가까운 중심의 클러스터에 재할당 (거리 예 = 유클리드)

K-means 알고리즘 특성

1. 중심점과의 평균 거리가 계속 줄어들기 때문에 매 반복마다 결과는 더 좋아진다.

2. 하지만 최적 해를 항상 찾는 건 아니다.

   → 초기값에 따라 지역 최솟값으로 수렴 가능하다. (지역 최소값 문제라고 부른다.)

┌────────────────────────────┐
│ 1 무작위 클러스터 초기화  │
└────────────────────────────┘
              ↓
┌────────────────────────────┐
│ 2a 중심 계산               │◀──────────┐
└────────────────────────────┘           │
              ↓                          │ 반복
┌────────────────────────────┐           │
│ 2b 클러스터 재배정         │───────────┘
└────────────────────────────┘
              ↓
     클러스터 변화가 없으면 종료

4. K-means 클러스터링에서 초기값의 영향

서로 다른 초기 라에서 최종 분할과 목표값 (패널 상단 숫자)이 달라진다.

초기화의 중요성: 여러 번 시도를 권장한다.

4. 계층적 군집

1. K-means 클러스터링 vs 계층적 군집

• K-means는 클러스터 수 K를 미리 지정해야 하는 단점이 존재한다.
• 계층적 군집은 K를 고정하지 않고 전체 구조를 덴드로그램으로 제공한다.

2. 계층적 군집 예시

• 덴드로그램에서 수평선 높이 (거리)를 기준으로 가위질하여 K개 군집을 얻는다.

!image.png

3. 계층적 군집 알고리즘 (상향식)

처음에는 각 데이터를 하나의 군집으로 보고, 가장 비슷한 군집끼리 하나씩 합쳐가는 방식이다.

┌──────────────────────────────────────┐
│ 1. 각 관측치를 하나의 군집으로 시작 │
│    총 n개의 군집 생성               │
└──────────────────────────────────────┘
                  ↓
┌──────────────────────────────────────┐
│ 2. 모든 군집 사이의 비유사도 계산   │
│    가장 비슷한 두 군집을 병합       │
└──────────────────────────────────────┘
                  ↓
┌──────────────────────────────────────┐
│ 3. 병합 후 남은 군집 사이의         │
│    비유사도를 다시 계산             │
└──────────────────────────────────────┘
                  ↓
          2번과 3번을 반복
                  ↓
┌──────────────────────────────────────┐
│ 최종적으로 하나의 군집이 될 때 종료 │
└──────────────────────────────────────┘

덴드로그램

• 군집이 병합되는 과정을 나무 모양으로 나타낸 그래프이다.
• 낮은 높이에서 합쳐질수록 서로 비슷하다.
• 높은 높이에서 합쳐질수록 서로 차이가 크다.
• 원하는 높이에서 잘라 군집 수를 결정할 수 있다.

4. 계층적 군집의 단계별 진행

처음에는 각 데이터를 하나의 군집으로 보고, 가장 가까운 군집끼리 순서대로 합쳐간다.

• 각 단계에서 가장 유사한 두 데이터 또는 군집을 병합한다.
• 병합이 진행될수록 군집의 개수는 하나씩 줄어든다.
• 먼저 합쳐지는 데이터일수록 서로 더 유사하다.
• 이러한 병합 과정을 덴드로그램으로 표현할 수 있다.

진행 예시

개별 데이터 → 가까운 데이터끼리 병합 → 작은 군집끼리 병합 → 최종적으로 하나의 군집

이 그림은 계층적 군집이 한 번에 결과를 만드는 것이 아니라, 단계적으로 군집을 합쳐가는 과정임을 보여준다.

5. 군집 간 거리 측정 방법(Linkage)

두 군집 사이의 거리를 어떤 기준으로 계산할지 결정하는 방법이다.

• Single Linkage(최소 거리)
  • 두 군집에 속한 데이터 쌍 중 가장 가까운 거리를 군집 간 거리로 사용한다.
• Complete Linkage(최대 거리)
  • 두 군집에 속한 데이터 쌍 중 가장 먼 거리를 군집 간 거리로 사용한다.
• Average Linkage(평균 거리)
  • 두 군집에 속한 모든 데이터 쌍의 거리 평균을 군집 간 거리로 사용한다.

5. 클러스터링 시 주의점

1. 스케일링
   • 클러스터링은 거리 기반이므로 변수의 단위와 크기가 결과에 영향을 준다.
   • 변수 간 크기 차이가 크면 표준화 또는 정규화가 필요하다.
2. 적절한 클러스터 개수
   • 클러스터 개수가 너무 적으면 서로 다른 집단이 합쳐질 수 있다.
   • 너무 많으면 하나의 집단이 지나치게 세분화될 수 있다.
   • 데이터 구조와 분석 목적에 맞는 클러스터 개수를 선택해야 한다.

1. 훈련 오류 vs 테스트 오류

• 훈련 오류: 모델을 학습시킨 같은 데이터에 다시 적용해 계산한 오류이다.
• 테스트 오류: 학습에 쓰지 않은 새 관측치에 대해 모델을 적용했을 때의 평균 예측오류이다.

파란색 선 : 훈련 오류

빨간색 선 : 테스트 오류

모델의 복잡도가 증가할수록 훈련 오류는 일반적으로 계속 감소한다.

테스트 오류는 처음에는 감소하지만, 모델이 지나치게 복잡해지면 오버피팅으로 인해 다시 증가할 수 있다. 따라서 보통 U자형에 가까운 형태를 보인다.

궁극적인 목적은 테스트 오류가 가장 낮아지는 적절한 복잡도의 모델을 찾는 것이다.

2. 테스트 예측 오류 계산

• 이상적 케이스: 충분히 큰 별도의 테스트 데이터셋 → 현실에선 구하기 어렵다.
• 현실에서는 테스트만을 위한 데이터를 갖기에 데이터 자체가 부족할 수 있다.

3. 대안

재표본화를 통해 테스트 오류 추정

데이터를 나눠 여러번 훈련 → 평가 를 반복해 테스트 오류를 가늠한다.

2. 검증셋 접근

1. 검증셋 방법

검증셋 (홀드아웃) 방법

• 가용 샘플들을 무작위로 훈련셋과 검증셋으로 분할한다.
• 훈련셋으로 모델 적합, 검증셋으로 예측 후 검증 오류를 계산한다.
• 검증 오류는 보통 정량 반응은 MSE, 범주 반응은 오분류율 (F1-score)을 측정한다.

2. 검증셋 절차

• 데이터 순서 무작위 셔플링 후 두 부분으로 분할한다.
  • 파랑 → 훈련셋, 주황 → 검증셋
• 학습은 훈련셋에서, 성능평가는 검증셋에서 수행한다.

3. 검증셋 방법 예시

예시: 자동차 데이터

• 목표: 선형 모델부터 고차항 모델 비교
• 392개 데이터를 무작위로 196개 훈련셋 / 196개 검증셋으로 분할한다. (일반적으로 굳이 반으로 나눌 필요는 없다.)
• 좌측 패널: 단 한번 분할 시 MSE 곡선
• 우측 패널: 여러 번 셔플 후 다른 분할의 MSE 곡선들

4. 검증셋 접근 한계

• 어떤 표본이 훈련/검증에 들어가느냐에 따라 검증 기반 테스트 오류 추정치가 매우 가변적이다.
• 검증 접근에서는 훈련셋만으로 모델이 적합하므로, 전체 데이터로 학습했을 때보다 성능이 낮게 추정될 수도 있다.

3. K-겹 교차검증

1. K-겹 교차검증

전체 데이터를 크기가 비슷한 K개의 묶음으로 나눈 뒤, 각 묶음을 한 번씩 검증 데이터로 사용한다.

1. K개 중 1개 묶음은 검증에 사용한다.
2. 나머지 K-1개 묶음은 훈련에 사용한다.
3. 이를 K번 반복한다.
4. 각 검증 오류의 평균으로 모델 성능을 평가한다.

검증 단계

1. 데이터를 셔플한 뒤, 전체 n개의 데이터를 서로 겹치지 않는 K개 그룹으로 나눈다.
2. 각 그룹을 한 번씩 검증셋으로 사용하고, 나머지 그룹은 훈련셋으로 사용한다.
3. 각 반복에서 MSE를 계산한다.
4. K개의 MSE를 평균하여 새로운 데이터에 대한 예측 오류를 추정한다.

2. K-겹 교차검증 오류 계산

• CV(K) : K-겹 교차검증의 최종 평균 오류
• K : 폴드 개수
• MSEₖ : k번째 폴드에서 계산한 검증 오류
• nₖ : k번째 폴드의 데이터 개수
• n : 전체 데이터 개수
• Σ : 1번부터 K번 폴드까지 모두 더하라는 뜻

최종 오류
= 각 폴드의 MSE × 해당 폴드의 데이터 비율을 모두 더한 값

LOOCV와 10-Fold 교차검증 비교

두 방법 모두 테스트 오류를 추정하는 방법이지만, 보통 10-Fold CV가 계산 효율과 안정성 면에서 더 실용적이다.