2025-09-13

오늘 배운 것

📘 알고리즘 정리 (DP / Heap / Greedy)

1. 동적 계획법 (Dynamic Programming, DP)6. DP

1.1 개념

• 귀납적 접근: 수학적 귀납법처럼 작은 문제의 해를 기반으로 큰 문제를 해결.
• Memoization: 이미 계산한 값을 저장하여 중복 연산 방지.
• 적용 조건
  1. 최적 부분 구조 (Optimal Substructure)
     • 어떤 문제의 최적 해는 작은 문제의 최적 해들로 구성된다.
  2. 중복 부분 문제 (Overlapping Subproblems)
     • 동일한 작은 문제를 여러 번 풀게 되는 구조여야 한다.

1.2 특징

• 최적화 문제(Optimization Problem) 해결에 적합.
• 재귀(recursion)와 점화식(formula)으로 문제를 표현 가능.

1.3 예시 문제

• 최장 공통 부분 수열 (LCS)
• 0/1 Knapsack

2. 힙 (Heap)7. 힙

2.1 개념

• 정의: 우선순위 큐를 위해 고안된 자료구조.
• 형태: 완전 이진 트리 구조.
• 종류
  • 최대 힙: 부모 ≥ 자식
  • 최소 힙: 부모 ≤ 자식

2.2 구현

• 배열 기반 구현
  • 루트 인덱스 1 기준
    • 부모: i / 2
    • 왼쪽 자식: i * 2
    • 오른쪽 자식: i * 2 + 1

2.3 연산

• 삽입 (Bubble Up): 마지막 노드에 삽입 후 부모와 교환하며 올라감.
• 삭제 (Bubble Down): 루트 제거 후 마지막 노드를 루트로 이동, 자식과 비교하며 내려감.

2.4 시간 복잡도

• 트리 높이 = O(log N)
• 삽입, 삭제 = O(log N)

2.5 예시 문제

• 힙 기본 문제
• 보급로
• 중간값 구하기
• 수 만들기

3. 완전탐색 & 그리디 (Brute Force & Greedy)8. 그리디

3.1 완전탐색

• 개념: 모든 경우의 수를 탐색하여 해를 찾는 방법.
• 특징
  • 구현이 간단하나 속도는 느림.
  • 작은 입력 크기 문제에 적합.
• 예시: 순차 탐색 (Sequential Search).

3.2 그리디 알고리즘

• 개념: 매 단계마다 “지금 당장 최선”을 선택.
• 조건
  1. 탐욕적 선택 속성 (Greedy Choice Property)
     • 각 선택이 최적 해로 이어질 수 있어야 한다.
  2. 최적 부분 구조 (Optimal Substructure)
     • 부분 문제의 최적 해들이 합쳐져 전체 최적 해를 구성해야 한다.
• 절차
  1. 해 선택
  2. 실행 가능성 검사
  3. 해 검사

3.3 예시 문제

• 최장 공통 부분 수열 (LCS)
• 0/1 Knapsack