[TIL] Greedy, 분할 정복

기면지·2021년 8월 18일

Java TIL algorithm

TIL

목록 보기

7/10

안녕하세요!
이번 포스팅에서는 Greedy 알고리즘과 분할 정복 알고리즘에 대해서 설명하도록 하겠습니다.

Greedy

탐욕 알고리즘은 최적해를 구하는 데 사용되는 방법입니다.
일반적으로, 머리 속에 떠오르는 생각을 검증 없이 바로 구현하면 그리디적인 접근이 됩니다.

Greedy 에서 핵심은 한번 선택된 것을 번복하지 않는다는 것입니다.
항상 그 시점에서 최선의 선택만을 하므로 다시 되돌아가서 확인하는 절차가 없습니다.
따라서 최적성에 대한 검증을 알고리즘 로직을 생각할 때 체크해야 합니다.

탐욕 알고리즘의 필수 요소는 greedy choice property 와 optimal substructure property 가 있습니다.

greedy choice property : 탐욕적 선택은 항상 최적해라는 것을 검증해야 한다.
optimal substructure property : 최적화 문제를 정형화해야 한다.

대표적인 Greedy 기법의 알고리즘들

Prim 알고리즘
N개의 노드에 대한 최소 신장 트리(MST)를 찾습니다.
서브트리를 확장하면서 MST를 찾습니다.
Kruskal 알고리즘
N개의 노드에 대한 최소 신장 트리(MST)를 찾습니다.
싸이클이 없는 서브 그래프를 확장하면서 MST를 찾습니다.
Dijkstra 알고리즘
주어진 정점에서 다른 정점들에 대한 최단 경로를 찾습니다.
주어진 정점에서 가장 가까운 정점을 찾고, 그 다음부터 정점을 반복해서 찾아갑니다.

분할 정복

분할 정복 기법은 크게 세 가지 부분으로 나뉩니다.
Divide , Conquer , Combine 입니다.

분할(Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다.
정복(Conquer) : 나눈 작은 문제를 각각 해결한다.
통합(Combine) : 필요하다면 해결된 답을 모은다.

이 분할 정복 기법은 거듭 제곱을 구할 때 시간적인 퍼포먼스를 줄여줍니다.
거듭 제곱을 반복적인 알고리즘을 사용한다면 아래와 같습니다.

void power(int x, int n) {
    int result = 1;
    
    for (int i = 0; i < n; ++i) {
    	result = result * x;
    }
    
    return result;
}

위 코드의 시간복잡도는 O(n) 이 될 것입니다.

void power(int x, int n) {
    if (n == 1) return x;
    
    int y = power(x, n/2);
    
    if (n%2 == 0) return y*y;
    else return x*y*y;
}

위의 코드는 분할 정복을 활용한 방법입니다.

계속 n을 2로 나누어서 재귀호출을 한 후에 n이 1일 경우는 x를 리턴합니다.
n이 짝수라면 그대로 재귀호출의 리턴값을 두번 곱해서 리턴하고,
n이 홀수라면 재귀호출의 리턴값을 두번 곱하고 자기 자신인 x까지 곱해서 리턴합니다.

위 코드의 시간복잡도는 O(logn) 으로 퍼포먼스가 훨씬 효율적으로 되었습니다.

Binary Search

이진 검색(Binary Search)은 자료의 가운데에 있는 항목의 키 값과 비교해 다음 검색 위치를 결정하고 검색을 계속 진행하는 방법입니다.
목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여 보다 빠르게 검색을 수행합니다.
전제 조건은 자료가 반드시 정렬된 상태여야 한다는 것입니다.

검색 과정

자료의 중앙 원소를 고른다.
중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
위의 두 값이 일치하면 탐색을 종료한다.
목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해 새로 검색을 수행하고,
크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다.
찾고자 하는 값을 찾을 때까지 위의 과정을 반복한다.

int binarySearch(int[] arr, int key) {
    int start = 0;
    int end = arr.length - 1;
    
    while (start <= end) {
    	int mid = (start+end) / 2;
        
        if (arr[mid] == key) return mid;
        else if (arr[mid] < key) start = mid+1;
        else end = mid-1;
     }
     
     return -1
}

반복문으로 구현한 이진 검색입니다.
start , end 변수로 검색할 처음과 끝의 범위를 정하고
mid 변수로 중앙 인덱스를 구해 처리합니다.
만약 해당 목표 값을 찾지 못했다면 -1을 리턴합니다.

int binarySearch(int[] arr, int start, int end, int key) {
    if (start > end) return -1;
    
    int mid = (start+end) / 2;
    if (arr[mid] == key) return mid;
    else if (arr[mid] < key) binarySearch(arr, mid+1, end, key);
    else binarySearch(arr, start, mid-1, key);
}