조건문과 반복문은 프로그래밍 언어를 단순한 계산기에서, 프로그래밍을 할 수 있는 도구로 만들어 주는 열쇠일 것이다. 오늘은 반복문을 사용할 때 많은 프로그래머들이 (익숙해서든, 익숙하지 않아서든) 잊어버리는, 루프 불변조건(Loop-invariant)에 대해 다뤄 보려고 한다. 최대한 이해하기 쉽게 작성하려고 했다.
프로그래밍을 하면서 가장 많이 만나는 것 중 하나는 반복문이다. 반복문은 C/C++과 Python에서 다음과 같은 꼴이다. (여기서 i++ 은 i += 1, i를 i의 다음숫자로 바꾼다.) 이다.
C, C++: for(int i=0; i<n; i++)
Python: for i in range(n):
이 글에서는 C, C++ 스타일의 반복문을 많이 사용하여 설명할 것이다. 이런 형태의 반복문을 보지 못한 사람들을 위하여, 그리고 다시 한번 반복문을 생각하기 위하여 C/C++ 스타일의 for문 부터 다시 한번 짚고 지나가자.
C/C++스타일의 반복문은 다음과 같이 생겼다.
for( init_statement; condition; iteration_expression )
{
statement;
}
이것을 풀어서 쓰면, 다음과 같은 모양이다. (실제로는 Scope가 달라진다.)
init_statement;
while(condition)
{
statement;
iteration_expression;
}
while(p)는, p를 만족할 동안 정해진 내용을 반복한다는 뜻이므로 (정해진 내용을 만족하면 빠져나오고, 만족하지 않으면 while문의 처음부터 다시 시작한다.)
for(int i = 0; i < n; i++) f(i);
라고 적힌 코드는,
int i = 0;
while(i < n)
{
f(i);
i++;
}
의 일을 하게 되고, 이는 실제로 반복을 해보면 이는 실제로 손으로 해보면, f(0)을 호출하고, i가 1 늘어서 f(1)을 호출하고... 이를
반복하여 f(0), f(1), ..., f(n-1)까지의 함수 호출을 하는 것을 알 수 있다. 그리고 이는 Python에서의 range를 사용한 루프와 같다. 한가지 차이점이 있다면, C, C++의 for loop에서는 statement가 i를 바꿔서는 안된다.
반복문을 이용해서 코드를 하나 작성해 보자. 반복문의 예제 코드 중 하나이다. 배열의 길이 N과 배열 A를 받아서 최댓값을 반환하는 함수를 만들어 보자. (여기서, N은 1 이상임이 보장되어 있고, A는 0번째 원소부터 N-1번째 원소까지 있다.)
int getMax(int N, int A[]) { int maxv = A[0]; for(int i=1; i<N; i++) if(maxv < A[i]) maxv = A[i]; return maxv; }
굉장히 평범하고 많은 사람이 작성할법한 코드이다. 그럼 이 코드가 맞다는 것을 설명해보자. 우리는 수학적 귀납법을 사용할 것이다.
코드를 while문을 이용하여 같은 코드로 작성하면 다음과 같이 된다.:
int getMax(int N, int A[])
{
int maxv = A[0];
int i = 1;
while(i < N)
{
if(maxv < A[i])
maxv = A[i];
i++;
}
return maxv;
}
증명할때, 루프 불변조건(loop-invariant)이라는 개념을 도입할 것이다. 이 루프 불변조건은 루프가 시작할때 유지되는 조건들을 의미한다. 이 문제에서의 루프 불변조건은, maxv의 값이 A[0]부터 A[i-1]까지의 최댓값을 가지고 있다는 것이다. 주석을 달아서 자세하게 확인해 보자.
int getMax(int N, int A[])
{
int maxv = A[0];
int i = 1;
// 1 - maxv의 값은 A[0]
while(i < N)
{
// 2 - maxv의 값은 A[0]부터 A[i-1]까지의 최댓값
if(maxv < A[i])
maxv = A[i];
// 3 - maxv의 값은 A[0]부터 A[i]까지의 최댓값
i++;
// 4 - maxv의 값은 A[0]부터 A[i-1]까지의 최댓값
}
// 5 - maxv의 값은 A[0]부터 A[N-1]까지의 최댓값.
return maxv;
}
1번 조건이 만족한다는 것은 maxv가 A[0]이고, 숫자가 하나만 있으면 그 숫자가 최댓값이라는것에서 알 수 있다.
2번 조건은, i = 1일때는 1번조건과 같다.
3번 조건은, 2번 조건에서 A[i]가 A[0]부터 A[i-1]까지의 최댓값보다 크면, A[i]가 다른 모든 수 보다 크므로 최댓값이다. 아닐 경우에는, A[0]부터 A[i-1]까지의 최댓값중에 A[i]보다 큰 값이 있으므로 최댓값이 유지될 것이다.
4번 조건은, 3번 조건에서 i값이 1커졌기 때문에 숫자를 맞춘 것이다.
이 4번 조건은, 만약에 루프를 빠져나가지 않는 다면, 다시 2번 조건에 들어가게 된다. 그리고 여기서 발견할 수 있는 흥미로운 사실은 i가 1이 커졌다는 것이다! 이것을 계속 반복되면, 루프를 빠져나올 때 i = N이기 때문에, 5번 조건 역시 만족하게 된다. 이 증명은 수학적 귀납법과 맥락을 같이한다.
루프 불변조건은 모든 루프문에서 다양하게 사용된다. 코딩을 하면서, 루프 불변조건은 루프를 분석하는데 굉장히 강력한 도구이고, 디버깅을 할 때도 강력하게 사용될 수 있다.(루프 불변조건을 assert하는 것으로, 논리단계를 제대로 밟고 있는지 아닌지 확인할 수 있다.)
그리고 루프가 포함된 함수를 분석하는데에 핵심이 된다.
루프 불변조건에 대해 글을 썼다. 수학적 귀납법과 같은 방식으로 생각을 해서, 증명을 한다고 생각하면 논리가 잡히기 시작할 것이다.
다음 게시글에는 동적 계획법에 대해 설명하려고 한다. 아래쪽에 풀어볼만한 연습문제들을 남겨 놓겠다. 풀이 등에 대한 질문이 있거나, 게시글에 개선할 사항은 덧글로 남겨줬으면 한다.
- 배열이 있을 때, 배열의 모든 원소의 합을 구하는 프로그램을 작성하고, 그 프로그램이 올바르다는 것을 증명하여라.
- O(n2)정렬로 유명한 삽입 정렬, 버블 정렬 그리고 선택 정렬이 올바르게 작동한다는 것을 증명하여라.
- 최대 힙(max heap)으로 작성된 우선순위 큐가 올바르게 동작한다는 것을 증명하여라.
- 다익스트라 알고리즘을 보고, 루프 불변조건을 이용하여 다익스트라 알고리즘이 올바르게 동작함을 증명하여라.
최대 힙, 우선순위 큐와 다익스트라 알고리즘에 대한 설명은 추가로 작성해서 게시글로 올리겠다.
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| [문제 제작 후기] BAEKJOON 15328 - 산타의 선물 (0) | 2017.12.28 |
|---|---|
| [Logical Thinking] 4. 시간복잡도 (0) | 2017.11.30 |
| [Logical Thinking] 현재까지의 포스트 모음 (0) | 2017.11.25 |
| [Logical Thinking] 3. 동적 계획법 (0) | 2017.11.25 |
| [Logical Thinking] 1. 수학적 귀납법 (0) | 2017.11.20 |
