그리디
그리디 개념
그리디는 '탐욕스러운', '욕심이 많은'이라는 뜻입니다. 문제 해결 과정에서 순간마다 눈앞에 보이는 최선의 선택을 하며 선택을 번복하지 않는 것을 말합니다.
그리디 알고리즘은 지역 최적해를 추구한다고 말하기도 합니다.
그리디 알고리즘이 최적해를 보장하려면?
그리디 알고리즘은 특정한 상황에서의 최적해를 보장합니다.
최적 부분 구조: 부분해를 푸는 과정이 최적해를 구하는 과정과 일치 그리디 선택 속성: 선택 과정이 다른 과정에 영향을 주지 않음 그리디 알고리즘은 최적 부분 구조를 가지지 않는 문제에서는 전체 해를 구하는 데 도움을 주지 않습니다. 그러나 알고리즘 문제의 특성과 알고리즘 선택 기준을 잘 이해하면 유용하게 활용할 수 있습니다.
최소 신장 트리
최소 신장 트리는 대표적인 트리 형태의 자료구조입니다.
신장 트리란?
모든 정점이 간선으로 연결되어 있고 간선 개수가 정점 개수보다 하나 적은 그래프를 말합니다.
최소 신장 트리란?
간선의 가중치 합이 최소면 최소 신장 트리라고 합니다. 항공기 운항 경로를 최적화할 때 이용하기도 합니다. 이를 MST라고 합니다.
최소 신장 트리를 구하는 그리디 알고리즘
프림 알고리즘과 크루스칼 알고리즘이 있습니다.
프림 알고리즘으로 최소 신장 트리 구하기
다음과 같은 과정으로 구할 수 있습니다.
임의의 정점을 하나 선택해 트리에 추가합니다. 최소 신장 트리와 연결되어 있는 정점 중 가장 가중치가 낮은 정점을 최소 신장 트리에 추가합니다. (단, 순환이 생기지 않도록 합니다.) 모든 정점이 연결될 때까지 2를 반복합니다. 크루스칼 알고리즘으로 최소 신장 트리 구하기
그래프의 모든 간선을 가중치 기준으로 오름차순 정렬합니다. 가중치가 낮은 간선부터 최소 신장 트리에 하나씩 추가합니다. (단, 순환이 생기지 않도록 합니다.) 모든 정점이 연결될 때까지 2를 반복합니다.
프림 | 크루스칼 | |
|---|---|---|
알고리즘 목적 | 최소 신장 트리 | 최소 신장 트리 |
시간 복잡도 (정점 V, 간선 E) | ||
탐색 방법 | 임의 정점에서 최소 인접 가중치를 가지는 정점을 찾아 확장하는 방식 | 최소 가중치를 가지는 간선부터 하나씩 추가하는 방식 |
배낭 문제
부분 배낭 문제 | 0/1 배낭 문제 | |
|---|---|---|
알고리즘 목적 | 배낭 속 짐 들의 가치 합의 최대 | 배낭 속 짐 들의 가치 합의 최대 |
문제 특징 | 짐을 쪼갤 수 있음 | 짐을 쪼갤 수 없음 |
시간 복잡도 (짐의 개수 N, 가치 W) | ||
그리디 적용 가능 여부 | O | X |