문제가 복잡해지면 알고리즘이 문제를 해결할 수 있는지 어떻게 알 수 있을까? 단위 테스트?
단위 테스트는 알고리즘에 문제가 있음을 증명할 수는 있지만, 알고리즘에 문제가 없음을 증명할 수는 없다
예전엔 이 말이 잘 이해가 안 됐다. 그런데 어려운 문제를 풀려고 이렇게 저렇게 코드를 짜다 보면
이 코드가 문제를 해결할 수 있을까?라거나
‘내가 짜는 알고리즘에 문제가 없어서 모든 테스트 케이스를 통과할 수 있다는 것을 어떻게 보장하지? 같은 의문이 들었다.
그러니, 내가 짜는 알고리즘이 1. 무엇을 목표로, 2. 어떻게, 3. 왜 그렇게 짜는지도 모른 채 되는대로 풀었던 셈이다.
풀면 다행이고, 못 풀면 그냥 그 시간 허탕친 셈이었고 남는 게 적었다.
고등학교 수학처럼 알고리즘을 유형에 따라 그냥 외우면 편할 수도 있고, 사실 선 암기 후 이해도 좋은 학습 방법이라 생각하지만, 머리가 굵어졌는지 이제는 그게 잘 안 된다.
코드를 짜면서도 ‘난 왜 이렇게 코드를 짜지?’ 같은 생각이 들면 잘 알지도 못하면서 푸는 척 하는 모습에 그냥 더이상 풀고 싶지가 않아진다.
결국 제대로 풀려면 증명에 대해 이해를 해야 하고, 그 과정에서 각종 수학적 기법이 동원되어야 한다고 한다.
당장 이해가 안 가더라도 정리를 할 필요성을 새삼 느낀다.
/* 불변식은 여기에서 성립 */
while(comeCondition){
/* 반복문 내용 시작 시 */
...
/* 반복문 내용 끝날 때 */
/* 불변식은 여기에서도 성립 */
}
/**
* A[-1]은 음의 무한대, A[n]은 양의 무한대 가정
* @param A 오름차순으로 정렬되어 있다
* @param x 찾고자 하는 값
* @return A[i-1] < x <= A[i]인 i를 반환
*/
public int binarySearch(List<Integer> A, int x) {
int low = 0, high = A.size();
/* 1. 반복문 불변식: low < high */
/* 2. 반복문 불변식: A[low] < x <= A[high] */
while (low < high) { /* 3. 반복문 종료 시: low >= high */
int mid = low + (high - low) / 2;
System.out.printf("mid: %d, (%d - %d) / 2: %d\n", mid, high, low, (high - low) / 2);
if (A.get(mid) < x) {
low = mid + 1; /* 책과 다른 부분. 책은 low를 -1로 초기화 */
} else {
high = mid;
}
}
return high;
}
이진 탐색 내부의 while문은 총 두 개의 반복문 불변식 유지
x는 작은 인덱스보다 크고 큰 인덱스보다 작거나 같은 인덱스에 위치한다애초에 불변식이 성립한다고 가정했으니 이것은 당연히 성립
x라는 값이 리스트 A의 low 인덱스와 high 인덱스 사이에 존재함을 가정했으니 당연히 성립한다는 게 무슨 말일까?
만약 x에 해당하는 값이 A에 존재하지 않는다면 어떻게 될까? 불변식이 깨진다.
불변식에 대해 다시 상기해보자면,
불변식은 반복문이 마지막에 정답을 계산하기 위해서는 항상 이 식이 변하지 않고 성립해야 하는 것이다
따라서 불변식이 성립하는 한, x는 A[log]와 A[high] 사이에 존재한다
삽입정렬?
public void insertionSort(List<Integer> A) {
/* 1. 반복문 불변식: A[0..i-1]은 이미 정렬되어 있다. */
for (int i = 0; i < A.size(); i++) {
/* 그렇다면 A[0..i-1]에 A[i]를 끼워넣는다. */
int j = i;
/* 2. 반복문 불변식: A[j + 1..i]의 모든 원소는 A[j]보다 크다 */
while (j > 0 && A.get(j - 1) > A.get(j)) { /* 불변식이 맞지 않는 데이터가 있다면? */
/* 불변식에 맞게 바꾼다 */
/* 3. 반복문 불변식: A[0..i] 구간은 A[j]를 제외하면 정렬되어 있다 */
Collections.swap(A, j - 1, j);
j--;
}
}
}
while (j > 0 && A.get(j - 1) > A.get(j)) 통해 모순되는 데이터를 찾는다2. 반복문 불변식: A[j + 1..i]의 모든 원소는 A[j]보다 크다가 유지되고 있기 때문A.get(j - 1) > A.get(j)인 경우가 있다면 while문 안에서 스왑이 이뤄지고 2번 불변식이 유지된다int j = i; 후 while문에서는 앞서 이미 검증된 j-2, j-3 등은 고려할 필요가 없다.Collections.swap이 다른 원소들의 정렬 상태를 건드리지 않음을 의미한다Collections.swap을 한다.Collections.swap으로 인해 이미 정렬된 것이 변경되면, 전체 정렬이 무효화 되도록 설정한다지금도 헷갈리지만, 처음보다는 조금 이해가 되는 거 같다.
처음에는 왜 혼자 가정하고 그게 성립하다고 하지?라고 생각했었다.
근데 이진 탐색 코드는 예제일 뿐이다. 실제로는 알고리즘을 푸는 사람이 반복문 불변식을 가정해야 한다.
즉,
따라서 정당성 검증에도 마법은 없다. 만약 귀납적인 추론이 잘못되어 잘못된 불변식을 가정하면 어떻게 될까?
불변식에 맞지 않는 데이터를 확인하게 되고, 불변식과 귀납 추론은 깨지게 되며, 불변식은 더이상 불변식이 아니게 된다.
따라서 어느 반복문에서 어떤 데이터가 어떻게 유지되어야 하는지가 이미 머릿속에 있어야 한다
그렇다면 불변식을 가정할 수 있다는 것 자체가 애초에 어느 정도 문제를 풀 능력이 된다는 것…으로 이해가 된다.
결국 귀납 추론을 잘해서 정확한 규칙을 찾고, 규칙에 따라 불변식을 만드는 연습을 해야 할 것 같다.
가령 아래와 같은 책장 4개가 있다고 해보자
[ C ]
[ A ]
[ B ]
이 경우 앞서 원하는 정렬 순서인 A, B, C와는 반대가 된다. 그럼 이 반대가 되는 사실이 잘못되었음을 찾아내면 정렬 순서가 증명된다.
A와 B의 위치는 항상 바꿀 수 있다. 바꾸는 것은 문제가 아니며, 바꾼 후 A가 B의 무게까지 견딜 수 있는지가 문제 된다.
$(\text{A가 견딜 수 있는 무게} + \text{A 책장의 무게}) \gt (\text{B가 견딜 수 있는 무게} + \text{B 책장의 무게})$가 된다. 이를 부등식으로 표현하면,
\[M_{A} + W_{A} \gt M_{B} + W_{B}\\\]
여기서 A가 버틸 수 있는 무게만 좌변에 남긴다
\[M_{A} \gt M_{B} + W_{B} - W_{A}\]
앞서 처음에 A 책장이 B 책장 위에 올라가 있었다.
[ C ]
[ A ]
[ B ]
여기서 B가 버틸 수 있는 무게는 $\text{A 책장의 무게} + \text{A 책장 위 책장들의 무게}$가 되며, 이에 따르면 다음 부등식이 성립한다.
\[X = \sum_{j \in above(A)}W_{j}\\ M_{B} \ge W_{A} + X\]
두 부등식을 정리하면
\[M_{A} \gt M_{B} + (W_{B} - W_{A}) \ge W_{A} + X + (W_{B} - W_{A})\\ M_{A} \gt X + W_{B}\]
X는 A 위에 올라가 있는 상자들의 무게의 합이고 $W_{B}$는 B 책장의 무게로, 두 합이 $M_{A}$보다 작으므로 A 책장도 B와 나머지 모든 책장을 지탱할 수 있다
따라서 $M_{i}$와 $W_{i}$ 합이 가장 큰 것부터 아래에 놓는다라는 정렬 순서로 쌓았을 때 가장 높은 탑을 얻지 못하는 경우는 존재하지 않는다.
나뭇잎이 1,000개에서 10,000개인 나무가 10만 그루 존재할 때, 나뭇잎 수가 같은 나무가 존재할까? 결론부터 말하면 반드시 존재한다.
여기서 중요한 것은 가능한 나뭇잎 수의 경우의 수와 총 나무의 개수다.
나뭇잎 수의 베리에이션은 1,000과 10,000 사이의 숫자가 가능하며, 가능한 나뭇잎 수의 경우는 1,000개, 1,001개, … 10,000개로 9,001가지가 있다.
\(\left \{ \text{나뭇잎} \in \mathbb{N}| 1,000 \le \text{나뭇잎} \le 10,000 \right \}\)
가능한 나뭇잎 수의 경우는 9,001개인데 10만 그루의 나무가 있다면, 반드시 나뭇잎 수가 같은 나무가 존재할 수밖에 없다.
9,001가지 경우의 수를 100,000개의 나무에 분배해야 하기 때문이다. 이를 비둘기집의 원리(Pigeonhole Principle)이라고 한다.
10마리의 비둘기가 9개의 비둘기집에 모두 들어갔다면, 2마리 이상이 들어간 비둘기 집이 반드시 하나는 있게 마련이다.
처음에 생각했을 때 나뭇잎 수가 같은 나무가 존재할까? 어떻게 알지? 수를 다 세봐야 하나? 같은 생각이 떠올랐다.
우선 1,000, 10,000, 100,000 같은 일일이 세기 어려운 큰 숫자를 어떻게 처리할지가 걱정됐다.
그리고 존재하는지 여부를 어떻게 true 또는 false로 증명할지가 막막했다.
그런데 이를 9,001가지 경우의 수를 100,000개의 나무에 분배라고 표현하니 단번에 이해가 됐다.
4개씩 있는 3종류 사탕 12개를 10명이 먹으면, 두 명 이상은 반드시 같은 사탕을 먹게 된다.
더 적은 종류의 데이터를 더 많은 수의 데이터에 분배할 경우, 같은 데이터를 돌려쓰는 경우가 생길 수밖에 없다.