23일차 알고리즘 기초1

차지예·2025년 6월 16일

생성AI

목록 보기

19/56

1. 연결 리스트 (Linked List)

정의: 각 노드가 데이터와 다음 노드의 참조를 가지는 자료구조
종류:
- 단일 연결 리스트
- 이중 연결 리스트
- 원형 연결 리스트
특징:
- 삽입/삭제가 빠름 (O(1) 위치만 알면)
- 인덱스 접근은 느림 (O(n))

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

2. 스택 (Stack)

정의: 후입선출(LIFO) 구조의 자료구조
기능:
- push (데이터 추가)
- pop (데이터 제거)
- peek (맨 위 데이터 확인)
활용 예시: 되돌리기 기능, 괄호 검사, 함수 호출 스택 등

stack = []
stack.append(1)
stack.append(2)
stack.pop()  # 2 제거

3. 큐 (Queue)

정의: 선입선출(FIFO) 구조의 자료구조
기능:
- enqueue (삽입)
- dequeue (삭제)
활용 예시: 프린터 대기열, BFS, 작업 스케줄링

from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
queue.popleft()  # 1 제거

큐, 스택의 알고리즘 문제풀이

4. 결정트리(Decision Tree) 알고리즘

결정트리는 데이터를 분할하여 예측을 수행하는 지도학습(Supervised Learning) 알고리즘으로, 분류(Classification) 및 회귀(Regression) 문제에 모두 사용됩니다. 마치 질문을 따라가며 답을 찾는 과정과 비슷하여 직관적이고 해석이 쉬운 것이 큰 장점입니다.

결정트리란?

트리(Tree) 구조를 기반으로 한 모델로, "질문-답변-분기" 형태로 이루어집니다.
루트 노드(Root)에서 시작하여 조건에 따라 데이터를 분할(Split)해가며, 리프 노드(Leaf)에 도달했을 때 최종 예측값을 도출합니다.

용어	설명
루트 노드(Root Node)	트리의 시작점으로, 전체 데이터셋을 나타냅니다.
내부 노드(Internal Node)	분할 기준이 있는 노드 (조건 노드)
리프 노드(Leaf Node)	최종 결과가 나오는 노드 (예측값 or 클래스)
분할(Split)	조건에 따라 데이터를 나누는 것
가지(Branch)	조건 결과로 나뉘는 경로

과적합 방지 (Pruning)

결정트리는 너무 깊게 성장하면 훈련 데이터에 과적합(Overfitting)할 수 있습니다. 이를 방지하기 위해:

사전 가지치기 (Pre-pruning): 트리 성장을 조기에 멈춤
예) max_depth, min_samples_split 설정
사후 가지치기 (Post-pruning): 트리를 모두 만든 후 불필요한 노드를 제거

5. K-최근접 이웃 알고리즘 (K-Nearest Neighbors, KNN)

K-최근접 이웃(KNN, K-Nearest Neighbors)은 지도학습(Supervised Learning) 알고리즘 중 하나로, 분류(Classification)와 회귀(Regression) 모두에 사용됩니다.
이 알고리즘은 훈련 데이터를 사용해 모델을 학습하지 않고, 예측 시점에 가장 가까운 이웃을 기준으로 판단하기 때문에 비모수적(non-parametric)이고 게으른 학습(lazy learning)에 속합니다.

KNN의 원리

새로운 데이터 포인트가 주어졌을 때, 훈련 데이터 중에서 가장 가까운 K개의 이웃을 찾아서,
다수결(분류) 또는 평균(회귀) 으로 결과를 예측합니다.

예:
어떤 새로운 점이 주변에서 파랑: 3개, 빨강: 2개의 이웃이 있다면 → 예측 클래스는 파랑

거리 측정

KNN에서 가장 중요한 요소는 데이터 간의 거리(distance)입니다. 대표적인 거리 계산 방식은 다음과 같습니다:

유클리디안 거리 (Euclidean Distance)
$d(p, q) = \sqrt{ \sum_{i=1}^{n} (p_i - q_i)^2 }$
맨해튼 거리 (Manhattan Distance)
$d(p, q) = \sum_{i=1}^{n} |p_i - q_i|$
민코우스키 거리 (Minkowski Distance)
$d(p, q) = \left( \sum_{i=1}^{n} |p_i - q_i|^r \right)^{\frac{1}{r}}$
※ $r=1$ → 맨해튼 거리, $r=2$ → 유클리디안 거리

하이퍼파라미터: K 값 선택

K는 이웃의 수를 의미하며 모델의 성능에 큰 영향을 미칩니다.
너무 작으면 → 과적합 (노이즈에 민감)
너무 크면 → 과소적합 (전체 평균에 가까움)

📌 일반적으로 홀수 K값을 사용하여 동률 방지

KNN의 특징

항목	설명
학습 없음	데이터를 저장만 하고, 예측 시 계산함
계산량 큼	새로운 데이터마다 거리 계산이 필요
정규화 필수	거리 기반 알고리즘이므로 스케일 영향 큼
다차원에 취약	고차원 데이터에서는 희소해져 성능 저하 가능 (차원의 저주)