혜아의 아무말

Logical Thinking 게시글의 현재까지의 제목과 게시물 링크를 모아놓고, 새로운 게시글이 생길 때 마다 업데이트 하도록 하겠다.

[Logical Thinking] 1. 수학적 귀납법

[Logical Thinking] 2. 루프 불변조건(Loop-invariant)

[Logical Thinking] 3. 동적 계획법

[Logical Thinking] 4. 시간복잡도

동적 계획법(Dynamic Programming)은 프로그래밍을 할 때 생기는 문제를 작은 문제들로 나눠서 풀고, 그것을 합치는 방법이다. 그 과정에서 이미 풀어봤던 문제가 발생하면, 문제를 다시 풀지 않고, 예전에 풀었던 정보를 가져오는 방법이다. 이것 때문에 분할 정복과는 다른 면이 있다. 글들은 최대한 이해하기 쉽게 작성하려고 했다.

동적 계획법

동적 계획법을 최대한 쉽게 설명해 보려고 노력 했고, 내가 할 수 있는 제일 쉬운 설명을 가져왔다. 숫자를 세어 보도록 하자, 첫번째 줄에는 1이 몇개 있는가?

1 1 1 1 1 1 1 1 1 1

아마 대부분이 세어 보지 않았을 거라고 생각하지만, 1이 10개가 있다. 그러면 여기서 1을 하나 더 그었다고 생각해 보자.

1 1 1 1 1 1 1 1 1 1 1

아래에서는 1이 몇개 있는가? 이것은 아마 이 문장을 보기 전에 답을 알고 있을 것이다. 11개이다. 우리는, 11개라는 답을 얻어낼 때, 처음부터 다시 세어본 것이 아니라 이전에 세었던 결과들을 미리 가져 온 것이다. 이것은 동적 계획법의 기본이 된다. 문제들을 비슷한 문제들로 바꾸고, 똑같은 문제에 대한 답을 미리 기억 해 놓는다.

최장 증가 부분 수열과 최적 부분구조(Optimal Substructure)

그림으로 그린 LIS문제, 3 4 5 6은 증가하는 수열이다.

동적 계획법의 예를 들어 보기 위해서, 우리는 간단한 하나의 문제를 가지고 올 것이다. 최장 증가 부분 수열(Longest Increasing Subsequence, LIS)이라는 문제는 굉장히 흔하게 알려진 문제이다.

임의의 수열을 하나 가지고 오자 예를들면 길이 10의 수열 "3 1 4 1 5 9 2 6 5 3"이 있다고 하자. 우리는 이 숫자들을 적당히 차례로 골라서 가장 길고, 증가하는 숫자들을 찾으려고 한다. 예를 들면 "3 1 4 1 5 9 2 6 5 3" 에서 굵게 표시된 "3 4 5 6"은, 증가하는 수열이고 순서를 보존한다. 이것 보다 더 큰 증가하는 부분 수열은 찾을 수 없기 때문에 "3 4 5 6"은 최장 증가 부분 수열이다. 이것이 유일하지는 않다. 예를들면 마지막 숫자만 9로 바꾼 "3 4 5 9"도 최장 증가 부분 수열이다. 하지만, 이 수열들의 길이는 4로 같다. 우리는 이 길이를 구하는 것에 초점을 맞추어 볼 것이다.

우리는 다음의 정리를 증명하려고 한다.

"(길이 2 이상의) i번째 수로 끝나는 증가 부분 수열중 가장 길이가 긴 것은, 1번째 수로 끝나는 증가 부분 수열 중 가장 길이가 긴 것 또는 2번째 수로 끝나는 증가 부분 수열 중 가장 길이가 긴 것 또는 ... i-1번째 수로 끝나는 증가 부분 수열을 포함하고 있다."

라는 것이다. 즉, "최장 증가 부분 수열"은, 더 작은 최장 증가 부분 수열을 포함하고 있다는 뜻이다.

증명은 간단하다. i번째 수로 끝나는 증가 부분 수열에 마지막에서 두번째 원소가 j번째 수라고 하자. (첫번째 원소를 x번째 수라고 해서, 수열을 a_x, ..., a_j, a_i로 나타내자.) 만약, 이 증가 부분 수열이 j번째 수로 끝나는 증가 부분 수열을 포함하고 있지 않다면 우리는 수열의 앞부분을 교체해서 더 길게 만들 수 있고, 우리가 "가장 길다"라고 말한 것에 모순이다. (j번째 수로 끝나는 최장 증가 부분 수열인 (a_y, ..., a_j)가 (a_x, ..., a_j)보다 더 길면, (a_y, ..., a_j, a_i)가 (a_x, ..., a_j, a_i) 보다 더 길다.) 그러므로, 본 명제가 증명되었다.

어쨌든 결론은 우리는 최장 증가 부분 수열을 문제를 풀 때, 큰 문제의 답에는 작은 문제의 답이 들어 있다는 것이다. 이것을 최적 부분 구조(Optimal Substructure)라고 말하고, 작은 문제를 풀고 그것을 이용할 수 있다는 것이다. 이것을 토대로 우리는 코드를 짜 볼 수 있다.

// 배열 A가 주어졌을 때, M번째 원소로 끝나는 최장 증가 부분수열의 길이를 구한다.
int solve(int M, const int A[])
{
    // 자기 자신이 유일한 최장 증가 부분 수열인 경우
    int ans = 0; 

    // 부분 문제를 답으로 가지고 있다.
    // i번째 수열을 사용하려면, A[M]을 덧붙일 수 있어야 한다.
    // 그래서 A[i] < A[M]일 경우에만, 문제의 답을 가져온다.
    for(int i=0; i<M; ++i)
        if(A[i] < A[M]) 
            ans = std::max(ans, solve(i, A) + 1);

    return ans; 
}

int LIS(int N, const int A[])
{
    // 모든 숫자에 대해서, 그 숫자로 끝나는 최장 증가 부분 수열의 길이를 구한다.
    // 그 중 최댓값이 전체에서의 최장 증가 부분 수열이다. 
    int ans = 0;
    for(int i=0; i<N; ++i)
        ans = std::max(ans, solve(i, A));
 
    return ans;
}

부분문제 반복(Overlapping Subproblem)

위의 코드를 실제로 실행 시켜 보면, 굉장히 느릴 것이다. 왜냐하면, 우리는 solve(1, A)를 호출 할 때도, solve(2, A)를 호출할 때에도 계속 solve(0, A)를 호출 할 수 있기 때문이다. 하지만, 우리는 여러번 실행 시켜봐도 답이 변하지 않는다는 사실을 알고 있다. (코드가 어떤 경우에도 결정적이고, 외부에 있는 변수를 바꾸지 않는다.) 그래서 우리는 몇가지 트릭을 써보려고 한다. 만약에 우리가 한번 계산한 값이면, 다시 계산할 필요가 없고, 이 값을 저장시켜 놓는 것이다. 우리는 그 배열의 이름을 dp라고 정할 것이다.: 코드는 다음과 같다.

int *dp;
int solve(const int M, const int A[])
{
    // 이미 계산된 값일 경우, 그 값을 그대로 쓴다.
    if(dp[M] != -1) return dp[M];
    int ans = 0; 
    
    // 부분 문제를 답으로 가지고 있다.
    for(int i=0; i<N; ++i)
        if(A[i] < A[N])
            ans = std::max(ans, solve(i, A) + 1);
 
    // 계산된 값을 저장해 놓는다.
    dp[M] = ans; 
    return ans; 
}

int LIS(const int N, const int A[])
{
    // dp배열을 -1로 채운다.
    // 여기서 -1은 우리가 아직 계산을 해 보지 않은 값이란 의미이다.
    dp = new int[N]; fill(dp, dp+N, -1);
    
    int ans = 0;
    for(int i=0; i<N; ++i)
        ans = std::max(ans, solve(i, A));
  
    delete[] dp;
    return ans;
}

이 방법을 쓰면, 우리는 여러번의 같은 코드가 실행되는 상황에서 한번만 그 문제를 계산하고, 나머지는 있는 값을 그대로 가져오는 것으로 풀 수 있다. 즉, 여러번의 문제가 반복되는 상황에서(부분문제 반복) 중복된 계산을 하지 않는다. 이 코드를, solve함수를 명시적으로 만들지 않고, 암시적으로 만들면 다음과 같은 코드가 된다.

int LIS(const int N, const int A[])
{
    int* dp = new int[N];
    int ans = 0; //LIS 함수에서의 ans 값이다.
    for(int i=0; i<N; ++i)
    {
        dp[i] = 0; //solve 함수에서의 ans 값이다.
        for(int j=0; j<i; ++j)
            if(A[j] < A[i])
                dp[i] = std::max(dp[i], dp[j] + 1);

        ans = std::max(ans, A[i]);
    }
    delete[] dp;
    return ans;
}

우리가 이런 코드를 만들 수 있는 이유는 위에서 solve(i, A)가 계산 될 시점에는, solve(0, A), solve(1, A), ..., solve(i-1, A)가 모두 계산 되어 있기 때문이다. 즉, 우리가 solve의 계산이 수행되는 순서를 알고 있기 때문이다. 그렇기 때문에, dp 배열의 값들을 안전하게 이용할 수 있다.

이 구역에 있는 두가지 코드는 동적 계획법을 계산하는 같은 역할을 하는 서로 다른 코드이다. 두 방법의 장단점이 모두 있으니, 상황에 따라 쓰면 좋다. 첫번째 방법의 좋은 점은, 필요 없는 dp값을 계산하지 않는 다는 점과, solve가 호출되는 순서를 알 필요가 없다는 것이다. 두번째 방법의 좋은 점은, 함수의 오버헤드가 없어서 실행 속도가 굉장히 빠르다는 점이다. 그리고 배열의 식을 그대로 사용하기 때문에 다양한 최적화를 하기 쉽다는 것이다.

동적계획법의 방법과 예제에 대해서 알아 보았다. 이 문제는, 현실의 문제를 푸는데도 굉장히 많이 이용된다. 대부분의 문제가 최적 부분구조와 부분문제 반복이라는 구조를 가지고, 문제를 변형하면 DP를 적용하기 쉬운 형태가 된다. 특히 bit-DP라는 방법이 현실의 문제를 푸는 방법과 많이 유사하다. 다양한 테크닉은 이 글의 범위를 초과하니 따로 포스트를 작성하는 것으로 하겠다. 다음에는 시간복잡도에 대한 포스트를 작성하도록 하겠다. 아래에 풀어볼만한 연습문제를 남겨 놓겠다. 풀이 등에 대한 질문이 있거나, 게시글에 개선할 사항은 덧글로 남겨줬으면 한다. 참고로 5번 문제는 Fenwick Tree라는 자료구조를 알고 있는 사람이 풀어 보았으면 좋겠다.

1. https://www.acmicpc.net/problem/1463

2. https://www.acmicpc.net/problem/11726

3. https://www.acmicpc.net/problem/1932

4. 그래프 문제중에, "단순 최장 경로"라는 문제가 있다. 이것은, 그래프에서 정점을 중복해서 지나지 않는 최장경로를 찾는 문제다. 이 문제는 정점에 대한 동적 계획법으로 풀리지 않는다. 왜 풀리지 않는가 설명하라.

5. 그런 반면에, 최단경로를 구하는 문제는 동적 계획법으로 매우 잘 풀린다. (모든 간선의 길이가 양수 일 때) 동적 계획법으로 그래프의 모든 정점쌍간의 최단거리를 구하는 알고리즘을 만들어라.

6. 가장 마지막의 LIS함수를 Fenwick Tree를 사용하여 O(n log n)으로 최적화 하여라.

이제까지의 모든 Logical Thinking 게시글 보기: http://blog.kyouko.moe/8

조건문과 반복문은 프로그래밍 언어를 단순한 계산기에서, 프로그래밍을 할 수 있는 도구로 만들어 주는 열쇠일 것이다. 오늘은 반복문을 사용할 때 많은 프로그래머들이 (익숙해서든, 익숙하지 않아서든) 잊어버리는, 루프 불변조건(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(n²)정렬로 유명한 삽입 정렬, 버블 정렬 그리고 선택 정렬이 올바르게 작동한다는 것을 증명하여라.
  
• 최대 힙(max heap)으로 작성된 우선순위 큐가 올바르게 동작한다는 것을 증명하여라.
• 다익스트라 알고리즘을 보고, 루프 불변조건을 이용하여 다익스트라 알고리즘이 올바르게 동작함을 증명하여라.

최대 힙, 우선순위 큐와 다익스트라 알고리즘에 대한 설명은 추가로 작성해서 게시글로 올리겠다.

예전에 트위터에 글을 쓰겠다고 말 해 놓고, 쓰지 않은 글들이 존재한다. 그 중 하나를 지금부터 다시 시작해보려고 한다.

블로그에 로지컬씽킹으로 논리적으로 생각하는 법에 대해서 써보려고 합니다. 아마 첫 글이 오늘 올라올 것 같네요 pic.twitter.com/h5Nk9c2QiI

— 이혜아@void (@mega_kina) August 28, 2017

아마 첫 두개는 이전 포스트의 내용을 다듬는 것이 될 것이다.

참고로 이 글에는 이해하기 어려울 수 있는 수학적인 내용이 들어있다. 이해하지 않고 읽기만 해도 되는 내용에는 ⁺표시를 해놓겠다. 이외의 내용은 최대한 이해하기 쉽게 작성하려고 했다.

프로그래머들은 대개로 셀 수 있는 것들을 다룬다. 그리고 객체에 번호를 붙이는 것에 익숙해져 있다. 예를들면 배열의 0번째 원소, 1번째 원소, 2번째 원소... 같은 식으로 하나 하나씩 배열의 원소와 자연수를 하나하나씩 대응을 해 준다.

우리는 이 "자연수"에 대해서 조금 더 알아보려고 한다. 여기서 말하는 자연수는 편의상 0을 포함하는 개념이다.

⁺자연수를 정의할 때, 가장 많이 쓰는 방법은 페아노 공리계이다. 페아노 공리계는 다음과 같이 9개의 조건을 만족하는 집합이다. (=과 S를 정의한다.)

1. 자연수 x에 대해, x = x
2. 자연수 x, y에 대해, x = y 이면 y = x
3. 자연수 x, y, z에 대해, x = y이고 y = z 이면 x = z
4. 자연수 x에 대해, x = y 이면 y도 자연수
5. 0은 자연수
6. 임의의 자연수 x에 대해, S(x)도 자연수
7. 임의의 자연수 x에 대해, S(x) ≠ 0
8. 임의의 자연수 x, y에 대해, S(x) = S(y) 이면 x = y
9. 0이 K의 원소이고, x가 K의 원소일 때, S(x)가 K의 원소이면 K는 자연수 집합

페아노 공리계를 처음 본 사람이 바로 이해를 하기는 힘들것이다. 페아노 공리계를 다시 쉽게 설명을 해보도록 하자.

0은 자연수이다. 0의 다음 수인 1도 자연수이고, 1의 다음 수인 2도 자연수이고, 2의 다음 수인 3도 자연수이고, ... 이렇게, 숫자들을 전부 다 모은 것이 자연수라는 것이다. (이것은 위의 페아노 공리계에서의 5와 9에 해당한다.) 그리고, 다양한 예외처리들이 되어 있다. 예를들면 어떤 수의 다음 수를 계속 따라가는 것으로 다시 되돌아오지 않는다는 등등...

좀 더 다른 비유를 해보면, 도미노가 있다. 도미노가 쭉 길게 있는데, 도미노는 한쪽 방향으로만 놓아져 있다. 그리고 도미노 하나를 쓰러뜨리면, 그 다음 도미노도 같이 쓰러진다. 쓰러진 도미노를 모두 모으면 자연수가 된다.

사실 굳이 이렇게 더 어려운 비유을 한 이유는, 이것이 수학적 귀납법의 핵심 아이디어이기 때문이다.

수학적 귀납법

귀납법은, 가설을 세우고, 경험적 사실로 참/거짓을 판단하는 방법이다. 다시 말하면, "내가 본것들은 다 ~~하더라."이다.

귀납법의 예를 들어보자면

• 내가 학교에서 본 모든 고양이는 검정색이다.
• 그러므로, 학교에 있는 모든 고양이는 검정색일 것이다.

귀납법은 뭔가 흔히 아는 "논리적"이라고 말하는 것과는 차이가 있어 보인다. 수학적 귀납법은 귀납법이라는 이름을 가지고 있지만, 사실 귀납법과는 많이 다르다.

수학적 귀납법을 설명하자. 수식을 사용해서 쓰면 다음과 같다.

P(0)이고, 모든 자연수 k에 대해 P(k)->P(k+1)이면, 모든 n에 대해 P(n)이다.

쉽게 설명을 하면, n에 대한 명제에 대해, n = 0일때 참이고, n = k+1이라는 것을, n = k가 참이라는 가정에서 증명할 수 있으면, 모든 n에 대해 명제가 참이라는 것이다. 이 설명은 어려워 보일 수 있어도, 이해를 하고 넘어갔으면 한다.

수학적 귀납법으로 많이 쓰이는 증명의 예시는 다음이 있다.:

1 + 3 + 5 + ... + ( 2n - 1 ) = n²

이 문제에 대한 증명은 다음과 같다:

n = 0일때: 0 = 0²이라 성립한다. (왼쪽에 아무 수도 더해지지 않기 때문에, 0이라고 썼다. 혹시 헛갈린다면, n = 1로 시작한다고 생각해도 좋다.)

n = k+1일때: ( 1 + 3 + ... + ( 2k - 1 ) ) + ( 2( k + 1 ) - 1 ) = ( k² ) + ( 2k + 1 ) = ( k + 1 )² (첫번째 등호에서, n = k일때의 결과를 가져다 썼다. 두번째 등호에서는, k² + 2k + 1 = ( k + 1 )² 라는 사실을 이용했다.)

n = 0일때 명제가 성립하고, n = k -> n = k+1이 성립하기 때문에, 수학적 귀납법에 의해서, 모든 n에 대해서 명제는 성립한다. 증명 끝.

 좀 더 쉽게 풀어 써보도록 하자.

n = 0일때: 0 = 0²이라 성립한다.

n = 1일때: 1 = (0) + 1 = 0² + 2×0 + 1 = 1²이라 성립한다.

n = 2일때: 1 + 3 = (1) + 3 = 1² + 2×1 + 1 = 2²이라 성립한다.

n = 3일때: 1 + 3 + 5 = (1 + 3) + 5 = 2² + 2×2 + 1 = 3²이라 성립한다.

n = 4일때: 1 + 3 + 5 + 7 = (1 + 3 + 5) + 7 = 3² + 2×3 + 1 = 4²이라 성립한다.

n = 5일때: 1 + 3 + 5 + 7 + 9 = (1 + 3 + 5 + 7) + 9 = 4² + 2×4 + 1 = 5²이라 성립한다.

...

같은 방법으로 모든 n에 대해서 성립한다.

위의 증명에서, 가장 처음에는, n = 0일때 등식이 성립한다는 것을 보이고, 두번째에는, 어떤 하나의 수에서 등식이 성립하면, 다음 수에서도 등식이 성립한다는 것을 보였다. (예를 들면, 1 + 3 + 5 + 7 + 9를 계산 할 때, (1 + 3 + 5 + 7) = 4²이라는 사실을 가져다 썼다.) 그래서 우리는 이 논리적인 식들이 도미노 처럼 쓰러진다는 것을 알 수 있다.

사실, 우리는 2번 풀이같이 작은 n에 대해서 직접 확인해 보는 방법을 쓴다. 하지만, 논리적인 증명을 위해서는 2번 풀이에 있는 식을 잘 정리해서 1번처럼 식을 사용하는 방법을 알아야 한다. 직접 종이에 써보면서 풀어보는것을 권장한다.

수학적 귀납법에 대해 글을 썼다. 도미노를 생각하면 편하다. 프로그램의 증명에서 수학적 귀납법은 중요하게 사용되고, 뒤의 게시글에서 계속 사용될 내용이니, 꼭 알아두었으면 한다. 다음 게시글에는 Loop-invariant를 설명하려고 한다.

아래쪽에 풀어볼만한 연습문제들이 담겨있는 링크를 남겨놓겠다. 링크에 있는 연습문제는 좀 더 수학의 분야에 치우쳐져 있다. 풀이 등에 대한 질문이 있거나, 게시글에 개선할 사항은 덧글로 남겨줬으면 한다.

링크. http://mathsci.kaist.ac.kr/~sangil/home/wp-content/uploads/2015/01/induction.pdf

수정1. http://koosaga.com/190 에 링크에 대한 작성된 풀이가 일부 올라와 있다.