[CS][CS50] 알고리즘 - 재귀 / 병합 정렬 / 정렬 알고리즘의 실행시간

boostcource
모두를 위한 컴퓨터 과학 (CS50 2019) : David J. Malan
www.boostcourse.org/cs11
실습환경 : CS50 Sandbox & CS50 IDE

모두를 위한 컴퓨터 과학 (CS50 2019)

 

재귀

함수가 본인 스스로를 호출해서 사용하는 것을 재귀(Recursion)라고 부른다.

 

재귀를 이해하는데에는 예시를 사용하는 것이 가장 좋다.

 

 

예시 : 피라미드 그리기

사용자로부터 높이 값을 받아

해당 높이 값을 가지는 피라미드를 출력하는 프로그램을 만들어보자.

#include <cs50.h>
#include <stdio.h>

void draw(int h);

int main(void){
    int height = get_int("Height: ");
    draw(height);
}

void draw(int h){
    for(int i=1; i<=h; i++){
        for(int j=1; j<=i; j++){
            printf("#");
        }
        printf("\n");
    }
}

// > Height: 5
// ? #
// ? ##
// ? ###
// ? ####
// ? #####

main 함수에서 높이 값을 입력받은 뒤

루프를 이용해 피라미드를 출력하는 draw 함수에 매개변수 height를 전달해 실행한다.

 

 

draw 함수 내에 있는 중첩 루프를 살펴보자면

사실 바깥 쪽 루프는 안 쪽 루프에서 수행하는 내용을 반복하도록 하는 것이다.

그래서 이 바깥 쪽 루프를 없애고 재귀적으로 호출하도록 코드를 수정해볼 수 있다.

#include <cs50.h>
#include <stdio.h>

void draw(int h);

int main(void){
    int height = get_int("Height: ");
    draw(height);
}

void draw(int h){
    if(h == 0){
        return;
    }
    draw(h-1);
    for(int i=0; i<h; i++){
        printf("#");
    }
    printf("\n");
}

// > Height: 5
// ? #
// ? ##
// ? ###
// ? ####
// ? #####

draw(5) -> draw(4) -> draw(3) -> draw(2) -> draw(1) -> draw(0)

차례로 재귀함수가 소환이 되어, 실행은 draw(0)부터 draw(5)까지 역순으로 진행하게 되는데

너비가 h인 한 층씩 그려내는 로직이 완성된다.

h = 0인 상황에 대해서는 아무것도 출력하지 않도록 하는 조건문은 꼭 추가해줘야 한다.

 

 

재귀를 사용하는 이유

반복문을 사용할 수 있는데도 재귀를 종종 사용하는데 변수 사용을 줄일 수 있다는 이점이 있기 때문이다.

이는 단순히 메모리에 대한 이점이 아닌

변경 가능한 상태(mutable state)를 제거해서 프로그램 오류가 발생할 가능성을 줄일 수 있다는 것이다.

또한 더 직관적이라는 이유도 있다.

 

 

 

---

병합 정렬

병합 정렬(합병 정렬)은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬하는 방식이다.

 

이전에 공부한 이진 검색이 포함된 분할 정복 탐색처럼 데이터를 반으로 나누어간다는 공통점을 가진다.

그리고 이 과정은 재귀적으로 구현되기 때문에 위에서 나온 재귀를 학습하면 더 이해하기 쉽다.

 

 

만일 1부터 8까지의 숫자로 구성된

[6, 3, 8, 5, 2, 7, 4, 1] 이라는 임의의 배열이 존재하고

이를 오름차순으로 정렬하려고 한다.

 

먼저 숫자들을 반으로 나눈 뒤, 나눠진 부분 중 첫 번째를 한 번 더 반으로 나눈다.

그리고 또 나눠진 부분 중 첫 번째를 반으로 나눈다.

이렇게 숫자가 두 개 밖에 안남으면 더 이상 나누지 않고 두 숫자를 다시 병합하는데

이 때 작은 숫자가 앞에 오도록 순서를 바꿔가면서 병합한다.

 

그렇게 처음에는 맨 앞의 6과 3을 비교하고, 그 다음은 8과 5를 비교하고,

그 다음에는 36 과 58 묶음을 가지고 비교하는 형태가 되며 아래와 같이 과정이 진행된다.

 

(* 빠른 이해를 위해 작은 숫자를 맨 앞으로 보내는 모습으로 표현했지만
   실제로는 추가 메모리를 따로 갖고 거기에 작은 숫자를 저장한다는 식으로 이해하면 된다.)

 

이후 3568 과 1247 묶음을 갖고 비교하면 아래와 같이 진행되며

최종적으로 오름차순 정렬이 완료된 [1, 2, 3, 4, 5, 6, 7, 8] 배열이 완성된다.

 

 

전체 과정을 요약해서 도식화해보면 아래와 같다.

• 6 | 3 | 8 | 5 | 2 | 7 | 4 | 1 : 가장 작은 부분 (숫자 1개)으로 나눠진 결과
• 3   6 | 5   8 | 2   7 | 1   4 : 숫자 1개씩을 정렬하여 병합한 결과
• 3   5   6   8 | 1   2   4   7 : 숫자 2개씩을 정렬하여 병합한 결과
• 1   2   3   4   5   6   7   8 : 마지막으로 숫자 4개씩을 정렬하여 병합한 결과

 

 

병합 정렬 실행 시간의 상한은

숫자들을 반으로 나눈데에 O(log n)의 시간이 들고,

각 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문에

종합적으로 O(n log n) 이다. 

하한은 숫자들이 이미 정렬되었는지 여부에 관계가 없기 때문에 동일하게 Ω(n log n) 이다.

 

 

 

---

정렬 알고리즘의 실행시간

앞서 알고리즘 표기법 에 대해 알아보면서 선형 검색, 이진 검색의 Big O 와 Big Ω 를 탐색했는데

이제는 버블 정렬과 선택 정렬, 병합 정렬의 Big O 와 Big Ω 를 정리에 추가해보자.

 

상한 (Big O)

• O(n^2) - 선택 정렬, 버블 정렬
• O(n log n) - 병합 정렬
• O(n) - 선형 검색
• O(log n) - 이진검색
• O(1)

하한 (Big Ω)

• Ω(n^2) - 선택 정렬
• Ω(n log n) - 병합 정렬
• Ω(n) - 버블 정렬
• Ω(log n)
• Ω(1) - 선형 검색, 이진 검색

 

 

 

---

복습 퀴즈

Q1. 아래 코드와 같이 피라미드 쌓기를 재귀적으로 작성한 코드에서, h 값으로 3이 입력되었을 때 draw 함수는 총 몇 번 호출되는가? (parameter로 3을 받은 draw 함수 최초 호출을 제외한다.)

void draw(int h){
	if(h == 0){
		return;
	}
	draw(h-1);
	for(int i=0; i<h; i++){
		printf("#");
	}
	printf("\n");
}

답: 3번

draw(2) -> draw(1) -> draw(0)

 

 

Q2. 선택 정렬, 버블 정렬, 병합 정렬, 선형 검색, 이진 검색 5가지 알고리즘을 최선인 경우일 때의 실행시간(하한)이 빠른 순서대로 나열하자면? (단, 하한이 같은 경우 상한이 빠른 순으로 나열한다.)

답: 이진 검색 - 선형 검색 - 버블 정렬 - 병합 정렬 - 선택 정렬

선택 정렬 : 상한 O(n^2) / 하한 Ω(n^2)

버블 정렬 : 상한 O(n^2) / 하한 Ω(n)

병합 정렬 : 상한 O(n log n) / 하한 Ω(n log n)

선형 검색 : 상한 O(n) / 하한 Ω(1)

이진 검색 : 상한 O(log n) / 하한 Ω(1)