프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략
Algorithmic PRoblem Solving Strategies
Part02. 알고리즘 분석
개관
- 시간 : 알고리즘이 적은 시간을 사용한다는 것은 더 빠르게 동작한다는 이야기
따라서 알고리즘의 수행 속도와 특성을 분석하는 능력이 필요하다
- 공간 : 알고리즘이 더 적은 공간을 사용한다는 것은 더 적은 용량의 메모리를 사용한다는 것
이 두 기준은 서로 상충하는 경우가 많다
2부는 알고리즘의 속도를 분석하는 방법과 알고리즘의 정당성을 증명하는 기술들을 소개한다.
Chap4. 알고리즘의 시간 복잡도 분석
4.1 도입
직관적인 방법은 각각을 프로그램으로 구현한 뒤 같은 입력에대해 두 프로그램의 수행 시간을 측정하는 것이지만, 수행 시간은 언어는 물론 하드웨어, OS, 컴파일러에 이르기까지 수많은 요소에 의해 달라질 수 있다. 이런 외적 요인을 전부 통일하더라도 어떤 문자열 구현을 사용했는지, 함수 인자를 어떻게 넘겼는지 등의 사소한 문제에 따라 프로그램의 수행 시간이 크게 달라질 수 있다.
또한 수행 시간은 다양한 입력에 대한 실행 시간을 반영하지 못한다.
그렇다면 알고리즘 수행 시간을 어떤 기준으로 측정해야 할까?
* 반복문이 지배한다.
한 가지 항목이 전체의 대소를 좌지우지하는 것을 지배한다고 표현한다. (dominate)
알고리즘의 수행 시간을 지배하는 것은 바로 반복문. 대개 알고리즘의 수행 시간을 반복문이 수행되는 횟수로 측정. 이때 반복문의 수행 횟수는 입력의 크기에 대한 함수로 표현
ex. 주어진 배열에서 가장 많이 등장하는 수를 찾는 코드.
이 알고리즘의 수행 시간은 배열의 크기 N에 따라 변하다. N번 수행되는 반복문이 겹쳐져 잇으므로, 반복문의 가장 안쪽은 항상 N**2(pow(N, 2))번 실행된다. 따라서 이 알고리즘의 수행 시간은 pow(N, 2)이다.
int majority(const vector<int> &A) {
int N = A.size();
int majority = 1, majorityCount = 0;
for(int i=0; i<N; ++i) {
int V = A[i], count = 0;
for(int j = 0; j < N; ++j) {
if(A[j] == V) {
++count;
}
}
if(count > majorityCount) {
majorityCount = count;
majority = V;
}
return majority;
}
4.2 선형 시간 알고리즘
* 다이어트 현황 파악 : 이동 평균 계산하기
vertor <double> movingAverage1(const vector<double> & A, int M) {
vector<double> ret;
int N = A.size();
for(int i = M-1; i<N; ++i) {
double partialSum =0;
for(int j=0; j<M; ++j)
partialSum +=A[i-j];
ret.push_back(partialSum/M);
}
return ret;
}N개의 측정치가 주어질 때 매달 M달 간의 이동 평균을 계산하는 프로그램.
전체 반복문은 (M-N+1)*M번 반복된다.
어떻게 하면 좀 더 빠른 프로그램을 짤 수 있을까? 중복된 계산을 없애는 것이 중요한 아이디어.
측정한 몸무게 합을 일일이 구할 필요 없이 M-1까지 구했던 몸무게의 합에서 0일째에 측정한 몸무게를 빼고 M일 째에 측정한 몸무게를 더하는 것이다.
하나로 묶여있던 두 개의 반복문이 분리된다. 반복문 수행 횟수는 M-1 + (N-M+1) = N이 된다!
vector<double> movingAverage2(const vector<double> &A, int M) {
vector<double> ret;
int N = A.size();
double partialSum = 0;
for(int i = 0; i<M-1; ++i)
partialSum += A[i];
for(int i = M-1; i<N; ++i) {
partialSum += A[i];
ret.push_back(partialSum/M);
partialSum -= A[i-M+1];
}
return ret;
}위 프로그램의 수행시간은 N에 정비례. 이것을 선형 시간 알고리즘이라고 한다.
4.3 선형 이하 시간 알고리즘
* 사진 확인하기
사진 10000장을 시간 순서대로 나열해서, 두 개씩 분할을 거듭하여 가운데에 있는 것만을 비교해보는 것.
매번 절반씩 나노니 밑이 2인 로그가 된다. 대략 lgN만큼의 사진을 확인하면 되는 것이다.
이렇게 입력의 크기가 커지는 것보다 수행시간이 느리게 증가하는 알고리즘을 선형 이하 시간(sublinear time) 알고리즘이라고 한다.
* 이진 탐색
binsearch(A[], x) = 오름차순으로 정렬된 배열 A[]와 찾고 싶은 값 x가 주어질 떄 A[i-1] < x <= A[i]인 i를 반환한다. 이 때 A[-1] = -무한대, A[N]=무한대로 가정한다.
* 그래도 선형 시간이 아닌가요?
첫 번째로 A[]를 실제로 계산해서 갖고 있을 필요가 없다. 따라서 미리 계산할 것이 아니라 가운데 있는 것들에 대해서만 필요할 때 계산을 하면 된다. binsearch()에 A[]를 인자로 넘기는 것이 아니라 i가 주어질 떄 A[i]의 값을 직접 계산하는 콜백 함수를 제공한다거나 하는 방법으로 이 문제를 해결할 수 있다.
구현
5.2절에서 다시 살펴보겠다
4.4 지수 시간 알고리즘
* 다항 시간 알고리즘.
변수 N과 N**2, N의 거듭제곱들의 선형 결합으로 이루어지 식들을 다항식이라고 부른다.
선형 시간이나 선형 이하 시간과는 달리 다항 시간이라는 분류에 포함되는 알고리즘 간에는 엄청나게 큰 시간 차이가 날 수 있다.
* 알러지가 심한 친구들
* 모든 답 후보를 평가하기
N명의 친구를 초대하려고 할 때, 할 줄 아는 M가지 요리 중에서 메뉴를 고르려고 한다. 친구들은 알러지 때문에 못 먹는 음식들이 있어서 겹치는 메뉴로 최소 가짓수의 음식을 만드려고 한다.
만들 수 있는 음식의 모든 목록을 만드는 과정은 여러 개의 결정으로 나누면 자연스럽다. 이 알고리즘을 구현하는 가장 쉬운 방법은 재귀 호출이다.
const int INF = 987654321;
//이 메뉴로 모두가 식사할 수 있는지 여부 반환
bool canEverybodyEat(const vector<int> &menu);
//요리할 수 있는 음식의 종류 수
int M;
//food번째 음식을 만들지 여부를 결정
int selectMenu(vector<int> & menu, int food) {
//if(food==M) { //기저 사례 : 모든 음식에 대해 만들지 여부를 결정했을 때
if(canEnverybodyEat(menu)) return menu.size();
//아무것도 못 먹는 사람이 있으면 아주 큰 값 반환
return INF;
}
int ret = selectMenu(menu, food+1);
//이 음식을 만들지 않는 경우의 답
//이 음식을 만드는 경우의 답을 계산해 더 작은 것을 취한다.
menu.push_back(food);
ret = min(ret, selectMenu(menu, food+1));
menu.pop_back();
return ret;
}
* 지수 시간 알고리즘
모든 답을 한 번씩 다 확인했기 때문에 전체 걸리는 시간은 만들 수 있는 답의 수에 비례함.
M가지의 음식마다 만든다, 만들지 않는다 선택지가 있어 pow(2, M)가지의 답이 도출되는 것.
답을 하나 만들 때마다 canEverybodyEat()을 수행하니 pow(2, M)에 N*M번이 수행되어 전체 수행시간은 N*M*pow(2, M)이 된다.
N이 증가함에 따라 시간의 증가가 배로 되는 알고리즘을 지수 시간에 동작하낟고 한다.
* 소인수 분행의 수행 시간
입력으로 주어지는 숫자의 개수가 아닌 그 크기에 따라 수행시간이 달라지는 알고리즘들 또한 지수 수행 시간을 가질 수 있다.
N이 아무리 커져도 실제 입력은 1개 뿐일텐데 수행 시간이 달라지는 것은 우리의 직관과 맞지 않다. 이런 불일치를 이해하기 위해 알고리즘 수행 시간과 입력이 메모리에서 차지하는 공간의 관계를 생각해보자. 이진탐색, 이동 평균 계산 등 지금까지 다룬 알고리즘에선 입력의 값들이 일정 범위 내에 있다고 어렵지 않게 가정할 수 있다.
이 경우 입력개수와 메모리에서 차지하는 공간이 직접적으로 비례한다.
반면 소인수 분해 문제에선 입력으로 주어지는 숫자가 알고리즘의 동작에 직접적인 영향을 미치므로 숫자가 특정 범위 안에 있다고 가정할 수 없다. 이 때 입력이 차지하는 비트의 수에 따라 수행 시간이 증가한다고 생각하면 좀 설명할 수 있다.
4.5 시간 복잡도
시간 복잡도란 가장 널리 사용되는 알고리즘의 수행 시간 기준으로, 알고리즈이 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현하는 것.
기본적인 연산)
- 두 부호 있는 32비트 정수의 사칙연산
- 두 실수형 변수의 대소 비교
- 한 변수에 다른 변수 대입
아래는 기본 연산이 아니다.
- 정수 배열 정렬
- 두 문자열이 서로 같은지 확인
- 입력된 두 소인수 분해하기
입력의 크기가 충분히 작을 때는 시간 복잡도가 높은 알고리즘이 더 빠를 수도 있고, 시간 복잡도가 낮은 알고리즘이 입력이 커지면 커질수록 더 효율적이 될 수 있다.
* 입력의 종류에 따른 수행시간의 변화
입력이 어떤 형태로 구성되어 있는지도 수행시간에 영향을 미침.
이럴 경우, 최선, 최악 그리고 평균적인 경에 경우에 따른 시간을 따로 계산할 수 있다.
* 점근적 시간 표기 : O표기
Big-O 표기법은 알고리즘의 수행 시간을 표기한다. 간단하게 말해 주어진 함수에서 가장 빨리 증가하는 항만을 남기고 나머지를 다 버리는 표기법.
O(1)일 경우 상수 시간 알고리즘이라고 부른다.
* O표기법의 의미
계산하기 편하고 알아보기 쉽다. 대략적으로 함수의 상한을 나타낼 수 있다. f(N) = O(g(N))
아주 큰 N0와 C(N0, C>0)를 적절히 선택하면 N0 <= N인 모든 N에 대해 |f(N)|<=C * |g(N)|이 참이 되도록 할 수 있다.
O 표기법은 최악의 수행시간이 안리ㅏ 수행 시간을 간단히 나타내는 표기법일 뿐이다.
* 시간 복잡도 분석 연습
selectionSort() 예제.
void selectionSort(vector<int< &A) {
for(int i = 0; i<A.size(); ++i) {
int minIndex = i;
for(int j=i+1; j<A.size(); ++j)
if(A[minIndex] > A[j])
minIndex = j;
swap(A[i], A[minIndex]);
}
}선택 정렬은 모든 i에 대해 A[i...N-1]에서 가장 작은 원소를 찾은 뒤 이것을 A[i]에 넣는 것을 반복한다.
for문 내부의 if가 i=0일 때 N-1번, i=1일 때 N-2번... 실행된다고 보면 (N-1) + (N-2) + ... +1로 O(N**2)를 생각해볼 수 있다. 단순히는 최대 O(N)번 실행되는 for문이 두 개 겹쳐 있으므로 O(N**2)라고 생각되어도 괜찮다.
insertionSort
void insertionSort(vector<int> &A) {
for(int i=0; i<A.size(); ++i) {
int j=i;
while(i>0 && A[j-1] > A[j]) {
swap(A[j-1], A[j]);
--j;
}
}
}전체 배열 중 정렬되어 있는 부분 배열에 새 원소를 끼워넣는 일이 반복된다.
최선의 경우 처음음부터 정렬된 배열이 이미 주어진 경우, j에 대한 while문은 매번 즉시 종료된다. i에 대한 for문이 있으므로 O(N)이 된다. 반면 최악의 경우 역순으로 정렬된 배열이 주어지는 경우, while문의 시간 복잡도는 O(N)이 되고 최종 시간 복잡도는 O(N**2)이 된다.
* 시간 복잡도의 분할 상황 분석
N개의 작은 작업들을 순서대로 하는데 각 작업에 걸리는 시간이 모두 다르지만 전체 작업에 걸리는 시간이 일정한 경우 이런 방법을 적용할 수 있다.
4.6 수행 시간 어림짐작하기
* 주먹구구 법칙
프로그래밍 대회의 시간 제한은 알고리즘의 시간 복잡도가 아니라 프로그램의 수행 시간을 기준으로 한다.
따라서 입력의 최대 크기와 알고리즘의 시간 복잡도를 보고 수행 시간을 어림짐작할 수 잇어야 한다.
입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해 1초당 반복문 수행 횟수가 1억(10의 8승)이 넘어가면 시간 제한을 초과할 가능성이 있다.
* 주먹구구 법칙은 주먹구구일 뿐이다.
이 법칙은 맹신해선 안 된다.
시간 복잡도 외에 다른 요소들을 참조해 시간 안에 수행될지를 판단해야 한다
- 시간 복잡도가 프로그램ㄹ의 실제 수행 속도를 반영하지 못하는 경우 : O 표기법으로 시간 복잡도를 표현할 땐 상수나 최고차항 이외 항들을 모두 지워버린다.
- 반복문의 내부가 복잡할 경우
- 메모리 사용 패턴이 복잡한 경우 : 현대 CPU는 메모리에 있는 자료를 직접 접근하는 대신 캐시라고 부르는 작고 빠른 메모리로 옮겨온 뒤 처리한다. 메모리에서 캐시로 자료를 가져올 때는 인접한 자료를 함께 가져오므로 인접 자료들을 연속해서 사용하는 프로그램은 메모리에서 매번 자료를 가져올 필요 없이 캐시에 이미 저장된 자료를 사용하게 된다. 이런 차이는 실제 수행 속도에 영향을 미칠 수 있다.
- 언어와 컴파일러의 차이
- 구형 컴퓨터를 사용하는 경우
* 실제 적용해보기
1차원 배열에서 연속된 부분 구간 중 그 합이 최대인 구간을 찾는 문제를 풀어보자.
첫번째는 모든 부분 구간을 순회하며 합을 계산하는 알고리즘.
const int MIN = enumeric_limits<int>::min();
int inefficientMaxSum(const vector<int> &A) {
int N = A.size(), ret = MIN;
for(int i=0; i<N; ++i) {
int sum = 0;
for(int j=i; j<N; ++j) {
int sum = 0;
for(int k = i; k<=j; ++k)
sum+= A[k];
ret = max(ret, sum);
}
return ret;
}
O(N**2) 만큼의 후보 구간을 검사하고 각 구간의 합을 구하는데 O(N)이 걸리므로시간 복잡도는 O(N**3)이다.
int betterMaxSum(const vector<int> &A) {
int N=A.size(), ret = MIN;
for(int i=0; i<N; ++i) {
int sum = 0;
for(int j=i; j<N; ++j) {
sum+= A[j];
ret = max(ret, sum);
}
}
return ret;
}
위의 시간복잡도는 O(N**2)
7장에서 다루는 분할 정복 기법을 이용하면 빠른 시간에 동작하는 것을 설계할 수 있다.
이 방법대로는 O(NlgN)이 된다.
int fastMaxSum(const vector<int> &A, int lo, int hi) {
if(lo==hi) return A[lo];
int mid = (lo+hi)/2;
int left = MIN, right = MIN, sum=0;
for(int i=mid; i>=lo; --i) {
sum+=A[i];
left = max(left, sum);
}
sum = 0;
for(int j=mid+1; k<=hi; ++j) {
sum+=A[j];
right =max(right, sum);
}
int single =max(fastMaxSum(A,lo, mid), fastMaxSum(A, mid+1, hi));
return max(left+right, single);
}
마지막으로 동적 계획법을 사용하면 선형 시간 안에 풀 수 있따.
4.7 계산 복잡도 클래스 : P, NP, NP-완비
* 문제의 특성 공부하기
계산 복잡도 이론은 각 문제의 특성을 공부하는 학문
- 정렬 문제 : 주어진 N개의 정수를 정렬한 결과는 무엇인가?
- 부분 집합합 문제 : N개의 수가 있을 때 이 중 몇개를 골라 그들의 합이 S가 되도록 할 수 있는가?
이 두문제의 난이도는 어떻게 될까? 계산 복잡도 이론에서 문제의 난이도는 해당 문제를 해결하는 빠른 알고리즘이 있느냐를 나타낸다.
일반적으로 다항 시간 알고리즘이나 그보다 빠른 알고리즘들만을 빠르다고 말한다.
계산 복잡도 이론에선 이렇게 다항 시간 알고리즘이 존재하는 문제들의 집합을 P문제라고 한다. 예를 들어 정렬 문제에는 다항 시간 알고리즘이 수없이 많이 존재하므로 정렬 문제는 P문제이다.
P문제처럼 같은 성질을 갖는 문제들을 모아놓은 집합을 계산 복잡도 클래스라고 부른다.
* 난이도의 함정
다항 시간 안에 풀 수 있음을 증명하는 건 쉽지만 풀 수 없음을 보이기란 어렵다.
계산 복잡도에서 어려운 문제들이란
- 정말 어려운 문제를 골라 기준으로 삼는다
- 기준 문제만큼 어렵거나 그보다 어려운 문제들만을 어렵다고 한다.
계산 복잡도 이론에선 두 문제의 난이도를 비교하기 위해 환산이라는 기법을 사용한다.
B의 입력을 적절히 변형해 A의 입력으로 바꾸는 환산 알고리즘이 존재한다고 하자. 이 때 A를 푸는 가장 빠른 알고리즘을 가져오면 이것을 환산 알고리즘과 결합해 B를 푸는 알고리즘을 만들 수 있다. 환산 알고리즘이 무시할 수 있을 정도로 빠르다고 가정하면 결합된 알고리즘은 A를 푸는 가장 빠른 알고리즘과 같은 시간이 걸릴 것이다. B를 푸는 가장 빠른 알고리즘은 앞에서 결합된 알고리즘과 같거나 더 빠를 테니, 결국 B를 푸는 가장 빠른 알고리즘은 A를 푸는 가장 빠른 알고리즘과 같거나 더 빠를 수 밖에 없다. 이 경우 A가 B 이상으로 어렵다는 것을 알게 된다.
* NP 문제, NP 난해 문제
이제 어려운 문제의 기준을 정해보자. 이 어려운 문제의 기준이 되는 게 바로 SAT 문제satisfiability problem.
SAT문제란 N개의 불린 값 변수로 구성된 논리식을 참으로 만드는 변수 값들의 조합을 찾는 문제.
예를 들어 불린 변수 a, b, c의 다음 논리식은 세 변수의 값이 특정 조합을 이루어야 만족된다.
((a||b||!c) &&(!c||!a) && ((!a&&b)||(b&&!c))) && (!b||(!a&&!c))
SAT문제는 모든 NP 문제 이상으로 어렵다는 의미가 있다.
NP 문제란 답이 주어졌을 때 이것이 정답인지 다항 시간 내에 확인할 수 있는 문제이다. 부분 집합 합 문제도 NP. 또한 모든 P문제들은 모두 NP문제에도 포함된다.
SAT가 모든 NP문제 이상으로 어렵다는 말은 SAT를 다항시간에 풀 수 있으면 NP문제들은 모두 다항 시간에 풀 수 있다는 얘기. 이런 속성을 갖는 문제들의 집합을 NP-난해NP-Hard라고 부른다. 아직 아무도 NP-hard 문제를 다항 시간에 푸는 방법을 발견하지 못했다.
NP-난해 문제이며 NP인 문제들을 NP-완비Complete 문제라고 한다.
Chap5. 알고리즘의 정당성 증명
5.1 도입
* 알고리즘의 정당성 증명
5.2 수학적 귀납법과 반복문 불변식
수학적 귀납법은 반복적인 구조를 갖는 명제들을 증며하는데 유용하게 사용된다.
- 단계 나누기
- 첫 단계 증명
- 귀납 증명 : k번째가 성립하면 k+1번째도 성립한다.
* 반복문 불변식
귀납법으로 알고리즘 정당성을 증명할 때 반복문 불변식이라는 개념이 유용하다. 반복문의 내용이 한번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지 명시하는 조건. 반복문이 마지막에 정답을 계산하기 위해선 항상 이 식이 변하지 않고 성립해야 하는 것
- 반복문 진입시 불변식이 성립함을 보인다
- 반복문 내용이 불변식을 깨뜨리지 않음을 보인다. 반복문 내용이 시작할 때 불변식이 성립했다면 내용이 끝날 때도 불변식이 항상 성립함을 보인다
- 반복문 종료시 불변식이 성립하면 항상 우리가 정담을 구했음을 보인다.
//(*) 불변식은 여기에서 성립해야 한다
while(어떤 조건) {
//반복문 시작
...
//반복문 끝
//(**) 불변식은 여기에서도 성립
}
** 이진 탐색과 반복문 불변식
//필수조건 : A는 오름차순 정렬되어 있다
//결과 : A[i-1] < x <= A[i]인 i를 반환한다.
//이 때 A[-1] = 음의 무한대, A[n]=야으이 무한대라고 가정
int binsearch(const vector<int> &A, int x) {
int n= A.size();
int lo = -1, hi = n;
//반복문 불변식 1 : lo < hi
//2 : A[lo] < x <= A[hi];
// (*)
while(lo + 1< hi) {
int mid = (lo + hi) / 2;
if(A[mid]<x)
lo = mid;
else
hi = mid;
// (**)
}
return hi;
}
- lo+1 = hi : while문이 종료했으니 lo+1>=hi인데 불변식에 의해 lo<hi이니 lo+1 = hi일 수 밖에 없다
- A[lo] < x<= A[hi] : 애초에 불변식이 성립한다고 가정했으니 이것도 성립.
우리가 원하는 결과값 i는 A[i-1] <x <=A[i]인 i이므로 이때 우리가 원하는 답은 hi이다. 따라서 불변식이 while문 종료 시에 항상 성립한다는 걸 보일 수 있다면 이 알고리즘의 정당성은 증명한 셈이다.
- 초기 조건 : while문이 시작할 떄 lo와 hi는 초기값 -1과 n으로 초기화된 상태. 만약 n=0이면 while문은 아예 건너뛰므로 불변식1은 항상 성립. A[-1]=-무한대이고 A[n] = 무한대라고 가정하므로 2 또한 성립
- 유지조건 : while문 내부가 불변식을 깨뜨리지 않음을 보이면 된다
- 불변식 1 : while문 내부로 들어왔다는ㅁ ㅏㄹ은 hi와 lo의 차이가 2 이상이라는 의미이므로, mid는 항상 두 값의 사이. mid는 lo를 대입하건 hi를 대입하건 항상 불변식 1 유지
- 불변식 2 :
- A[mid]<x인 경우 : 반복문을 시작할 때 x<=A[ho]는 이미 알고 있고, 따라서 A[mid]<x<A[hi]이므로 lo에 mid를 대입해도 불변식 성립.
* 삽입 정렬과 반복문 불변식
void insertionSort(vector<int> &A) {
for(int i=0; i<A.size(); ++i) {
//불변식 : A[0...i-1]은 이미 정렬되어 있다.
//A[9...i-1]에 A[i]를 끼워넣는다.
int j=i;
while(j>0 && A[j-1]>A[j]) {
//불변식 b : A[j+1 ... i]의 모든 원소는 A[j]보다 크다.
//불변식 c : A[0...i]구간은 A[j]를 제외하면 정렬되어 있다
swap(A[j-1], A[j]);
--j;
}
}
}
* 단정문을 이용해 반복문 불변식 강제하기
5.3 귀류법
우리가 원하는 바와 반대되는 상황을 가정하고 논리를 전개해 결론이 잘못됐음을 찾아내는 증명 기법이 귀류법. 대개 어떤 선택이 항상 최선임을 증명하고자 할 때
* 책장 쌓기
상자 형태로 된 책장을 여러 개 쌓아올리려고 한다. 각 책장마다 버틸 수 있는 최대 무개 Mi와 자신의 무게 Wi가 주어진다. 이 때 책장을 어떻게 가장 높이 쌓을 수 있을까?
책장 위에 올라간 다른 책장들의 무게의 합이, 견딜 수 있는 최대 무게를 초과하면 안 될 것이다.
Wi + Mi가 큰 것부터 아래에 놓아야 한다.
귀류법을 사용해보자. 어떤 입력의 최적해를 구했는데 Mi + Wi가 더 큰 책장 A가 더 작은 책장 B위에 올라간 형태라면? 이때 A와 B의 위치를 항상 바꿀 수 있음을 증명해 보자.
Wa + Ma > Wb + wb
Ma > Wb + Mb - Wa
A위에 올라가 있는 무게의 합이 X라고 하자. 가장 좋은 답에서 A가 B위에 올라갔으니 Mb >= Wa + X임을 알 수 있다.
Ma > Mb + Wb - Wa >= (Wa + X) + Wb - Wa
맨 오른쪽의 Ma들이 더하고 빠지면,
Ma > X+Wb
A도 B와 나머지 모든 상자들을 지탱할 수 있다는 말.
5.4 다른 기술들
* 비둘기집의 원리
10마리의 비둘기가 9개의 비둘기집에 모두 들어갔다면 2마리 이상이 들어간 비둘기집이 반드시 하나는 있게 마련이다.
* 동전 뒤집기
100개의 동전이 깔려 있을 때 F개는 압면, 100-F개는 뒷면이 위로 놓여져 있다. 우리는 이 동전들의 앞면을 모두 위로 하게 하고 싶을 때, 한번 뒤집을 때 반드시 X개의 동전을 한꺼번에 뒤집어야 한다.
* 순환소수 찾기
순환 소수에서 a/b일 때 이것의 중간 중간 몫으로 나오는 숫자는 0...b-1 범위에 위치하게 된다.
* 구성적 증명
흔히 우리가 원하는 어떤 답이 존재한다는 사실을 증명하기 위해 사용된다. 구성적 증명은 "답이 존재하는가"에 대한 대답으로 "이렇게 만들면 된다"고 하는 것이므로 구성정 증명 내용이 사실상 알고리즘인 경우가 ㅁ낳다.
* 안정적 결혼 문제Stable marriage problem
'개발 공부 > Algorithm' 카테고리의 다른 글
| [LeetCode] 2390. Removing Stars From a String (0) | 2024.12.10 |
|---|---|
| [LeetCode] 338. Counting Bits (0) | 2024.12.10 |
| [LeetCode] 435. Non-overlapping Intervals (0) | 2024.12.08 |
| it 취업을 위한 알고리즘 문제풀이 - 1. 코드 구현력 기르기 (0) | 2020.09.16 |
| (New)알고리즘 문제해결전략 Part1-문제 해결 시작하기 (0) | 2020.07.06 |
