그리디
그리디 알고리즘
그리디 알고리즘은 해법을 단계적으로 계산한다. 각 단계마다 지역적으로(locally) 최적의 결정을 내리며, 이 결정은 절대 변경되지 않는다.
그리디 알고리즘이 늘 최적의 해법을 생성하는 것은 아니다. 때로는 문제에 대한 그리디 알고리즘이 여러 개 존재하며, 이들 중 일부만 최적의 해법을 제공하기도 한다.
알아야 할 내용
- 일반적인 형태의 동전 교환 문제는 NP-난해(hard) 문제이다.
- 일부 동전 교환 문제만 그리디 알고리즘으로 해결 가능하다.
- 동전의 단위가 1, r, $r^2$, $r^3$ … 인 경우
- 미국 동전같은 경우
- 1, 5, 10, 25, 50, 100
- 일부 동전 교환 문제만 그리디 알고리즘으로 해결 가능하다.
- 그리디 알고리즘은 보통, 각 단계에서 가장 최선의 선택을 할 수 있는 최적화 문제에 적합한 선택이다.
- 그리디 알고리즘을 재귀적으로 추상화한 뒤에, 성능 향상을 위해 반복문을 써서 구현하면 더 쉬운 경우가 많다.
- 그리디 방법이 최적 해법을 찾지 못하더라도, 최적 알고리즘을 찾는 통찰력 혹은 휴리스틱에 대한 힌트가 될 수 있다.
- 때로는 어떤 그리디 알고리즘을 선택해야 올바른지 명확하지 않은 경우도 있다.
불변식
- 불변식은 프로그램이 실행되는 동안 참인 조건을 말한다.
- 변수 값이나 제어 논리에 있을 수 있다.
예시
- 예를 들어 정렬된 숫자 배열에서 두 숫자를 골라 특정 숫자를 만든다고 해보자.
- 특정 구간의 가장 작은 값과 가장 큰 값을 더했을 때 원하는 숫자보다 작다면, 구간 내에서는 가장 작은 값과 다른 어떠한 값을 더하더라도 원하는 숫자보다 작을 수 밖에 없다.
- 이런 불변식을 이용해 풀어나갈 수 있다.
bool hasTwoSome(const vector<int> A, int t) {
int i=0, j = size(A) - 1;
while (i <= j) {
if (A[i] + A[j] == t) return true;
else if(A[i] + A[j] < t) ++i;
else --j; //A[i] + A[j] > t
}
return false;
}
알아야 할 내용
- 불변식 사용 여부를 결정하려면 먼저 작은 예제를 통해 가정한 불변식이 맞는지 확인해야 한다.
- 종종 불변식은 가능한 입력 집합의 부분 집합(부분 배열 등)이 된다.
1. 최적의 업무 할당 구하기
- 각 노동자는 정확히 두 개의 업무를 할당 받아야 한다.
- 모든 업무를 완료하는 데 걸리는 시간이 최소가 되도록 노동자에게 업무를 할당하라.
- 예를 들어 {5, 2, 1, 6, 4, 4} 시간이 걸리는 업무들이 주어졌을 때 최적은
- {5, 2}, {1, 6}, {4, 4} 로 업무를 할당하는 것이다.
풀이 방법
- 업무에 걸리는 시간순으로 정렬 한 뒤, 가장 짧게 걸리는 업무와 가장 길게 걸리는 업무를 묶어주면 된다.
2. 기다리는 시간을 최소화하기
- 각 쿼리를 처리하는 데 시간이 주어졌을 때, 총 대기 시간이 최소인 값을 구하라
- 예를 들어 각 쿼리를 처리하는 데 걸리는 시간이 {2, 5, 1, 3} 이라면,
- 순서대로 처리 시 0 + (2) + (2+5) + (2+5+1) = 17 이다.
풀이 방법
- 정렬하여 대기 시간이 최소인 쿼리먼저 처리해나가면 된다.
3. 모든 구간 커버하기
- 현장 감독이 공장을 방문하는 횟수를 최소화 하라.
- 현장 감독은 특정 시간에 방문하고, 이때 진행 중인 모든 업무를 확인할 수 있다.
- 모든 업무를 한번이상 확인한다고 할 때 가능한 최소 방문횟수를 구하라
풀이 방법
- [0,3],[2,6],[3,4],[6,9] 가 있을 때
- 오른쪽 끝 지점을 기준으로 정렬하면
- [0,3],[3,4],[2,6],[6,9]이다.
- 맨 왼쪽부터 시작해 오른쪽 끝 지점을 골라 나간다.
- 첨은 3이겠죠.
- 그러면 3을 포함하는 [0,3],[3,4],[2,6]을 지운다.
- 남은 [6,9]의 오른쪽 끝 지점을 고른다.
- 사실 뭘 골라도 상관은 없다.
struct Interval {
int left, right;
}
sort(A.begin(), A.end(),
[](const Interval& a, const Interval& b{return a.right < b.right;}));
4. 세 개의 원소를 합해 원하는 숫자를 얻을 수 있는 지 확인하기
- 배열과 숫자 하나가 주어졌을 때, 배열 안의 원소 세 개를 더해 주어진 숫자를 만들 수 있는지 확인하는 알고리즘을 설계하라
- 배열안의 숫자를 중복 사용가능하다.
풀이 방법
- 무식하게 $O(n^3)$ 으로 한다.
- 배열의 원소를 해시테이블에 저장해 시간 복잡도는 $O(n^2)$로 줄인다. 단, 공간 복잡도 가 O(n) 추가 필요
- 입력 배열을 정렬해 추가 공간 복잡도 사용 없이 할 수 있다.
- 한 원소를 탐색하며 나머지 두 원소를 이진 탐색으로 찾으면 $O(n^2)$으로 가능하다.
- A[i], A[j]를 골랐을 때, k-A[i]-A[j]를 이진 탐색으로 찾는다.
5. 다수 원소 찾기
- 문자열이 스트리밍 형태로 입력될 때, 한 번만 읽어 어떤 원소가 ‘다수 원소’인지 확인하는 프로그램을 작성하라.
- 특정 문자가 문자열의 절반 이상에서 등장하면 이 문자를 ‘다수(majority) 원소’ 라 한다.
풀이 방법
- 첫 원소를 다수 원소 후보자로 선택한다.
- 탐색하며 후보자와 같으면 +, 다르면 - 한다.
- 0이 되면 그 다음 원소를 다수 원소 후보자로 선택한다.
- 끝까지 탐색했을 때 남는 원소가 다수 원소이다.
증명
- n개의 엔트리에서 다수 원소가 m번 등장 했다고 가정했을 때, 다수 원소의 정의에 따라 다수원소의 비율은 m/n > 1/2 이다.
- 둘 중 하나가 다수 원소인 경우에 이 둘을 삭제했을 때 (m-1/n-2) 이고, 둘 모두 다수 원소가 아닐 때 둘을 삭제하면 다수 원소의 비율은 m/(n-2)이다.
- m/n > 1/2 일 때 (m-1/n-2), m/(n-2) 가 1/2 보다 큼을 증명하면 된다.
6. 주유소 문제
7. 수직선 쌍에 담을 수 있는 물의 최대 양 구하기
8. 스카이라인에서 가장 큰 직사각형 구하기
응용
- n/k 보다 많이 등장하는 원소 찾기도 이와 비슷하게 하면 된다.
‘266가지 문제로 정복하는 코딩 인터뷰 - 아다드 아지즈, 쭝시엔 리, 아트 프라카시 지음 - 이창현, 김현욱 옮김’ 책을 참고하여 작성한 포스트입니다.
Leave a comment