1.2. 시작하기

• 의사 코드

• 삽입 정렬

• 수행시간 분석

  • 표기법

• 분할 정복

  • 병합 정렬

  • 병합 정렬의 수행시간 분석

1.2.1 삽입 정렬

정렬 문제를 삽입 정렬을 사용해 풀어보자

1. 입력: n개 수들의 수열 {a1, a1, ..., an}

2. 출력: a'1 <= a'2 <= ... <= a'n 을 만족하는 입력 수열의 순열 (재배치) {a'1, a'1, ..., a'n}

3. 키: 정렬하고자 하는 숫자

a = [5, 2, 4, 6, 1, 3]

for j in range(1, len(a)):
    key = a[j]
    i = j - 1

    while i >= 0 and a[i] > key:
        a[i+1] = a[i]
        i = i - 1

    a[i+1] = key

루프 불변성

• 초기조건: 첫번째 반복을 시작하기 전에 루프 불변성이 참이어야 한다

• 유지조건: 시작되기 전에 참이었다면 다음 반복이 시작되기 전까지도 계속 참이어야 한다.

• 종료조건: 종료될 때 그 불변식이 알고리즘의 타당성을 보이는 데 도음이 될 유용한 특성을 가져야 한다.

어떠한 특성을 증명하기 위해 베이스 케이스와 귀납적 과정을 통해 증명하는 수학적 귀납법과 유사함을 알 수 있다.

• 첫 반복이 시작되기 전에 불변식이 만족한다는 것은 베이스 케이스가 참임을 보이는것과 비슷하다

• 다음 반복으로 넘어갈 때 불변식이 만족함을 보이는 것은 귀납적 과정을 보이는 단계와 비슷하다.

세번째 특성이 가장 중요하다, 루프 불변성을 보이는 목적이 결국 알고리즘의 타당성을 보이는 것이기 때문이다.

일반적인 수학적 귀납법은 귀납적 과정이 무한정 반복되지만 여기서는 루프가 종료될 때 귀납적 과정도 종료된다.

삽입 정렬의 타당성

• 초기조건

  • j = 2 일 때 루프 불변성이 성립하는가?

    • 부분 배열 a[1 .. j-1] 은 a[1] 한개의 원소로 구성되는데 원래는 a[1] 한개의 값이다

    • 해당 부분 배열은 정렬되어 있으므로 불변성 성립

• 유지조건

  • for 루프의 바디 부분은 a[j]의 올바른 위치를 찾을 때까지 a[j-1], a[j-2], a[j-3], ... 을 오른쪽으로 한 자리씩 이동시킨 후 a[j] 값을 적절한 위치에 삽입한다.

  • 배열 a[1..j]는 기존과 동일한 원소를 정렬한 상태로 갖게 된다.

  • 이 과정을 반복하면서 루프 불변성이 유지된다

• 종료조건

  • for 루프는 j 가 a.length = n 보다 커질때 (j = n + 1) 종료된다

  • 이때 부분배열은 a[1..n], 곧 전체 배열이므로 알고리즘이 타당함

연습문제

1. 그림 2.2 를 모델로 이용해 수열 A = {31, 41, 59, 26, 41, 58} 이 입력으로 주어질 때 삽입 정렬의 동작을 설명하여라

   • 31 {41} 59 26 41 58

   • 31 41 {59} 26 41 58

   • 31 41 59 {26} 41 58

     • {26} 31 41 59 41 58

   • 26 31 41 41 {59} 58

   • 26 31 41 41 59 {58}

     • 26 31 41 41 {58} 59

2. 수열을 오름차순 대신 내림차순으로 정렬하도록 삽입 정렬을 재작성하라

    a = [5, 2, 4, 6, 1, 3]
   
    for j in range(1, len(a)):
        key = a[j]
        i = j - 1
   
        while i >= 0 and a[i] < key:
            a[i+1] = a[i]
            i = i - 1
   
        a[i+1] = key

3. 선형 검색을 루프 불변성을 이용해 알고리즘이 타당함을 증명하라

    a = [5, 2, 4, 6, 1, 3]
    v = 1
    r = None
   
    for i in range(1, len(a)):
        if v == a[i]:
            r = i
            break

   • 초기조건

     • 시작하기 전 탐색된 부분배열은 0이므로 그 안에는 v 가 존재하지 않는다는걸 알 수 있다

   • 유지조건

     • for 루프의 바디 부분은 v == a[i] 일 때까지 반복된다.

     • 부분배열 a[1..i-1]에는 v가 없다는 것을 알수있다.

   • 종료조건

     • 루프는 v를 가진 인덱스 i를 찾거나배열의 끝까지 찾고자 하는 값이 없을떄 종료된다

     • 이때 값을 찾았거나 v를 가진 인덱스 i가 없다는것을 알수 있음

4. 원소가 n개인 두 배열 a, b 에 저장된 두 개의 n 비트 이진수를 더하는 문제를 고려해 보자. 두 이진수의 합은 원소가 n+1개인 배열 c에 이진수 형태로 저장되어야 한다. 이문제를 엄밀하게 서술하고 두 정수의 합을 구하는 의사코드를 작성하라

   • 엄밀하게 서술 => 입력과 출력을 정의하는것

   • 입력: n 비트 이진수 원소가 n개인 두 배열 a, b

   • 출력: 배열 a와 b의 원소가 더해진 값이 n+1개인 배열 c

1.2.2 알고리즘의 분석

알고리즘의 분석

• 그 알고리즘을 실행하는데 필요한 자원을 예측하는 것

• 대부분의 경우 측정 대상은 계산 시간

알고리즘을 분석하기에 앞서 이용할 구현 기술의 모델을 잘 정의해야 함

• 자원과 비용에 관한 모델도 포함

• 이 책에서는 대부분의 경우 알고리즘이 단일 프로세서와 랜덤 접근 기계 모델에서 구현된다고 가정함

삽입 정렬의 분석

• 삽입 정렬의 수행시간은 입력에 의해 결정됨

• 어느 정도 정렬되어 있느냐에 따라 수행시간이 달라질수도 있음

• 일반적으로 입력 크기가 커질수록 알고리즘의 수행시간이 증가하기 때문에 수행시간을 입력 크기의 함수로 표현

  • 수행시간과 입력 크기를 더욱 주의 깊게 정의할 필요가 있다.

입력 크기에 대한 가장 정확한 개념은 주어진 문제에 따라 다르다. 입력 항목의 개수일수도 있고, 총 비트수일수도 있고, 노드나 간선의 갯수일수도 있다.

어떤 입력에 대한 알고리즘의 수행시간 은 기본적으로 연산 개수 또는 실행된 단계의 횟수를 말함. 기계의 종류에 독립적으로 분석할 수 있도록 가능한 실행 단계의 개념을 정의하는 것이 편리하다.

최악의 경우와 평균적인 경우 분석

주로 최악의 경우의 수행시간에만 관심을 가질것

• 최악의 경우로 상한 보장 가능

• 최악의 경우는 생각보다 빈번

• 평균적인 경우가 최악의 경우와 비슷할 때가 종종 있다,

증가 차수

쎄타-표기법

연습문제

1.2.3 알고리즘의 설계

알고리즘을 설계하는 방법은 여러가지

• 점진적인 방법 -> 삽입 정렬

• 분할 정복

  • 장점: 훨씬 빠르고 수행시간을 쉽게 구할 수 있다.

분할정복 접근법

• 재귀적 구조

  • 재귀로 연관된 부분 문제를 다룸

  • 분할 정복 접근법

  • 전체 문제를 형태가 유사한 작은 문제로 분할하고 재귀적으로 풀어낸다, 그리고 찾은 해를 결합하여 원래 문제의 해를 구함

분할 정복의 단계

• 분할

• 정복

• 결합

병합 정렬의 예

• 분할: 정렬할 원소의 배열을 절반으로 분할

• 정복: 병합 정렬을 사용해 두 부분 배열을 재귀적으로 정렬

• 결합: 정렬된 두 개의 부분 배열을 병합해 정렬된 배열 하나로

정렬할 수열의 크기가 1이 되면 이미 정렬된 것 -> 호출이 바닥에 이름

핵심 작업은 결합 단계에서 두 부분 수열을 병합하는것

연습문제