안녕하세요!
이번 포스팅에서는 Greedy 알고리즘과 분할 정복 알고리즘에 대해서 설명하도록 하겠습니다.
탐욕 알고리즘은 최적해를 구하는 데 사용되는 방법입니다.
일반적으로, 머리 속에 떠오르는 생각을 검증 없이 바로 구현하면 그리디적인 접근이 됩니다.
Greedy
에서 핵심은 한번 선택된 것을 번복하지 않는다는 것입니다.
항상 그 시점에서 최선의 선택만을 하므로 다시 되돌아가서 확인하는 절차가 없습니다.
따라서 최적성에 대한 검증을 알고리즘 로직을 생각할 때 체크해야 합니다.
탐욕 알고리즘의 필수 요소는 greedy choice property
와 optimal substructure property
가 있습니다.
greedy choice property
: 탐욕적 선택은 항상 최적해라는 것을 검증해야 한다.optimal substructure property
: 최적화 문제를 정형화해야 한다.분할 정복 기법은 크게 세 가지 부분으로 나뉩니다.
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)은 자료의 가운데에 있는 항목의 키 값과 비교해 다음 검색 위치를 결정하고 검색을 계속 진행하는 방법입니다.
목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여 보다 빠르게 검색을 수행합니다.
전제 조건은 자료가 반드시 정렬된 상태여야 한다는 것입니다.
검색 과정
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);
}
재귀로 구현한 이진 검색입니다.
기본적인 로직은 위의 반복문으로 구현한 코드와 동일합니다.
다른 점은 재귀호출 시에 매개변수로 start
, end
, key
값을 넘겨주고 있다는 것입니다.
Java
에서는 이진 검색을 API로 제공하고 있습니다.
java.util.Arrays.binarySearch
라는 API는 여기에서 확인하실 수 있습니다.
오랜만에.. 약 일주일만에 작성하는 TIL 입니다.
꾸준하게 블로그 글을 쓰려고 투두에는 항상 넣어놓고있는데,
스터디 준비와 프로젝트, 알고리즘까지 하다 보니까 정신이 하나도 없는 요즘입니다 @.@
요즘 투두메이트
라는 어플에 푹 빠져서 투두를 미친듯이 적고 있는데 빨리 해결이나 해야겠습니다 !
이번 포스팅도 읽어주셔서 감사합니다 :)