최적화 문제 해결 : 브루트포스부터 탐욕 알고리즘

1. 최적화 문제란?

 

• 정의:
  조건을 만족하는 여러 후보 해답 중에서 최적(최대 또는 최소)의 해답을 찾는 문제.
• 예시:
  • 최단 경로 문제: 두 정점 사이의 가장 짧은 거리.
  • 배낭 문제(Knapsack):
    • 0-1 배낭 문제: 물건을 하나씩만 선택 (쪼갤 수 없음).
    • 연속 배낭 문제: 물건을 쪼개서 선택 가능 (fractional).
• 해법 종류:
  • 완전 탐색( brute-force search ): 모든 가능한 경우를 탐색 → 지수 시간 소요.
  • 효율적인 알고리즘 설계 기법:
    • 동적 프로그래밍(DP)
    • 탐욕적 알고리즘(Greedy)
    • 가능한 경우 다항 시간 알고리즘 사용.
• NP-완전 문제(NP-complete):
  • 아직 다항 시간 알고리즘 없음.
  • 예: 외판원 문제(TSP), 부분집합 합 문제 등.
  • 해결 방법:
    • 상태공간 트리 탐색: 백트래킹, 분기 한정법 등 → 시간이 오래 걸림.
    • 근사 알고리즘(휴리스틱): 정확한 해는 보장 못하지만, 실용적이고 빠름.

---

2. 탐욕적 알고리즘(Greedy Algorithm)

• 정의:
  공집합에서 시작해, 현재 상황에서 가장 좋은 선택을 반복하여 최적 해답을 만들어가는 알고리즘.
   문제를 풀 때 전체적인 최적을 고려하기보다는, "지금 당장 이 순간에 가장 좋은 선택"을 반복

• 절차:
  1. 선택(Selection):
     • 탐욕적 기준(Greedy Criterion)에 따라 현재 상황에서 가장 좋아 보이는 것을 선택 .
  2. 적정성 검정(Feasibility Check):
     • 선택한 것이 문제의 제약 조건을 만족하는지 확인. (예: 무게 초과 여부 등)
  3. 해답 점검(Solution Check):
     • 현재까지의 선택들이 해답 조건을 만족했는지 확인. (예: 배낭이 꽉 찼는지)
• 특징:
  • 동적 계획법보다 개발이 쉬움.
  • 하지만 항상 최적해를 보장하지 않음 → 수학적 증명 필요.
  • 보통 정렬이나 우선순위 큐와 함께 사용됨.

---

3. 탐욕적 기법으로 풀리는 문제들

1. 💰 거스름돈 문제

• 문제: 최소한의 동전 개수로 거스름돈을 줘야 함
• 전략: 가장 큰 동전부터 최대한 사용
• 조건: 동전 단위가 배수 관계여야 탐욕법 가능
  • ✔ 예: 500, 100, 50, 10 → 가능
  • ✘ 예: 25, 10, 1 → 동적 계획법 필요
• 예시: 870원 → 500(1개) + 100(3개) + 50(1개) + 10(2개) = 7개

2. 🎒 연속 배낭 문제 (Fractional Knapsack)

• 문제: 물건을 잘라서라도 담을 수 있을 때, 최대 가치를 구하기
• 전략: "무게당 가치"가 높은 것부터 담기
• 탐욕법 가능: 잘라서 담을 수 있기 때문 (0-1 배낭은 X)
• 예시:
  • 배낭 용량: 30kg
  • 물건: (무게, 가치): (5, 50), (10, 60), (20, 140)
  • 무게당 가치 순: 10, 7, 6
  • 결과: 5kg + 20kg + 5kg → 총 가치 $220

3. ⏱ 작업 스케줄링 문제

• 문제: 여러 작업을 순서대로 할 때, **총 시스템 시간(= 대기 + 작업시간)**을 최소화
• 전략: 작업 시간이 짧은 것부터 먼저 처리
• 탐욕법 가능: 짧은 작업이 먼저 끝나면, 다른 작업의 대기시간이 줄어듦
• 예시: [21, 10, 5, 20] → 정렬: [5, 10, 20, 21] → 총 시스템 시간 최소

4. 🏢 회의실 배정 문제 (Activity Selection)

• 문제: 회의 시간이 겹치지 않도록 최대한 많은 회의를 배치
• 전략: 종료 시간이 빠른 회의부터 선택 (중요!)
• 다른 전략들 (실패):
  • 시작이 빠른 순 → ❌
  • 사용 시간이 짧은 순 → ❌
  • 종료 시간이 빠른 회의부터 → O
• 예시: 회의 [(1,4), (3,5), (0,6), (4,7)]
  → 종료 시간 순 정렬 후 선택 → 최대 2개 가능

5. 파일 압축 – 허프만(Huffman) 코드

6. 최소 신장 트리(MST) – Prim, Kruskal 알고리즘

7. 단일 출발점 최단 경로 – Dijkstra 알고리즘

---

4. 우선순위 큐(priority queue)와 힙(heap)

우선순위 큐(Priority Queue) : 

✅ 개념

• 우선순위가 높은 아이템을 먼저 꺼내는 자료구조
• 일반 큐(FIFO)와 달리, 작업마다 가장 중요한 것부터 꺼냄
• 주로 **탐욕 알고리즘(Greedy)**에서 사용됨. 매 순간 **최적의 선택(가장 큰/작은 값)**을 반복해서 해야 하기 때문

방법 설명 단점

1. 정렬 안 된 배열	값 넣기 쉬움	꺼낼 때 느림 (O(n))
2. 정렬된 배열	꺼낼 땐 빠름	넣을 때마다 다시 정렬해야 함
✅ 3. 힙(Heap)	삽입도 O(log n), 삭제도 O(log n)	효율 최고

 

힙(Heap)

우선순위 큐를 효율적으로 구현하는 자료구조

 

 

힙의 특징

• 정렬된 상태까지는 아니지만, 부분 정렬(partially ordered) 상태 유지

힙의 구조	완전이진트리를 배열로 구현
힙의 목적	우선순위 큐를 빠르게 구현
핵심 연산	heapify, sift-up, sift-down
최대/최소 힙	루트가 가장 큰/작은 값
시간복잡도	삽입/삭제 O(log n), 전체 구성 O(n)