[부스트 코딩 뉴비 챌린지 2020] week4: 알고리즘

1. 검색 알고리즘

들어가기 전에

지난시간까지 우리는 메모리의 구조, 자료형, 배열과 같은 기본적인 개념을 익혔습니다. 이번 강의부터는 여태까지 배운 내용을 활용하여 검색이나 정렬과 같은 문제를 푸는 알고리즘을 배워 보겠습니다. 먼저 주어진 배열 속에서 특정 값을 찾는 방법부터 시작해 보겠습니다.

학습 목표

주어진 배열 속에서 특정 값을 찾는 방법을 설명할 수 있습니다.

핵심 단어

• 선형 검색
• 이진 검색

오늘 수업의 최종 목표는 중요한 개념을 잘 얻어가는 것이다.

 

학습하기

지난 시간 우리는 컴퓨터 내부를 다뤘다. 메모리가 있고, 임의 접근 기억장치를 RAM이라고 하는데 이것을 바이트 단위로 나누면 매우 편리하다는 것을 깨달았다.

예로 들면 바이트 0은 가장 왼쪽위이고, 2억 byte인 2기가 바이트는 가장 밑의 오른쪽이 될 것이다. 이렇게 메모리를 보기 시작하면 개념적으로나 물리적으로나, 왼쪽에서 아래쪽, 그리고 위에서 아래 자료구조를 사용할 수 있었다.

지난시간에 배운 배열을 예제로 메모리르 바이트의 격자 배열로 취급하면 우리가 원하는 대로 사용할 수 있었다.

실생활에서 생각해보면 배열이라는 개념은 우리에게 익숙한 빨간 서랍과 같다. 우리는 배열 안에 들어있는 내용물을 전반적으로 파악할 수 있지만 컴퓨터는 그럴 수 없다. 우리처럼 빠르게 한눈에 훑고 전체를 파악하는 감지 능력이 없다. 컴퓨터는 배열 속의 내용물을 하나하나 봐야만 한다. 알고리즘과 비슷하다. 컴퓨터는 모든 숫자를 한 눈에 파악할 수 없고, 서랍을 한 번에 한 개씩만 열어볼 수 있다.

그런 의미에서 A가 서랍 속에 미리 숫자를 넣어두었다. 이제 해결해야 할 문제는 특정 숫자를 찾는 것이다. 이 문제를 컴퓨터과학적으로 설명해보면 입력값은 7개의 서랍이며, 결과값은 불리언 값, 즉 참 혹은 거짓으로, 찾는 숫자가 이 7개의 서랍 중에 있는지 보는 것이다. 

 

선형 검색

첫 번째 학생(Eric)은 각 서랍을 왼쪽부터 오른쪽으로 순서대로 찾았다. 이는 선형검색이다. 차례대로 여기서 저기까지 열어보는 것이다. 그리고 이 알고리즘은 정확했다. 하지만 우리는 단순히 맞고 틀린 지 뿐만 아니라 다른 부분도 최적화하고 싶다. 설계 즉 효율성이다. 

선형 검색 방법의 경우 효율적인 방법이다. 왜냐하면 숫자들이 정렬되지 않았기 때문에 직접 하나하나 확인하는 수 밖에 없다. 50이 가장 마지막인 건 우연이다. 

정렬되어 있는지 알지 못하는 상황에서 우리가 할 수 있는 가장 최선은 직접 하나하나 확인해보는 것이다. 운이 좋다면 숫자 50이 첫 번째 서랍에 있었을지도 모르지만 최악의 상황에서는 위처럼 모든 서랍을 열게 된다.

 

이진 검색

두 번째 방법으로는 숫자를 미리 정렬을 한 후 서랍에서 숫자 50을 찾는 것이다. 이런 경우 학생(Nizari)은 중간 서랍을 먼저 열어보았다. 그리고 선택한 서랍에서 +2 서랍을 열어보니 81이 나왔다. 그리고 이 두 서랍 사이 중간 서랍을 열어보니 숫자 50이 들어있었다.

선형 탐색과 이진 탐색은 이름에서부터 매우 직관적이다. Eric은 차례대로 보며 숫자를 찾았고, Nizari는 이진 검색을 했다. 이진은 두 개를 뜻하며, 첫 주에 얘기했던 전화번호책을 생각해보면 분할 정복 기법을 사용했었다. 사실 그 기법도 이진 탐색이라고 할 수 있다. 왜냐면 문제를 계속하여 두 갈래로 나눴기 때문이다. 이진 탐색을 반복적으로 한다. 여기서도 두 번째로 숫자 50을 찾았을 때처럼 말이다.

두 가지 알고리즘을 보았다. 이제 얘기를 정리하여 각 알고리즘이 어떻게 정확하게 문제를 풀었고 또 어떻게 더 나은 설계를 할 수 있을지 보자. 

선형 탐색에 대한 의사 코드를 다음과 같이 적을 수 있다. 의사 코드는 다양한 방법으로 적을 수 있다.

Eric이라고 상상하여 적는다면, 머릿속에서 i를 0부터 n-1로 생각하여 코드의 형식으로 표현해보면, 여기 이 서랍은 0번째이고 이 마지막 서랍은 n-1 즉 총 6번째로 총 7개의 서랍이 있다.

그는 i번째 서랍을, 즉 현재 보고 있는 서랍이 50이라면 참을 바노한한다. 이 알고리즘이 반환하는 값은 불리언값이다. 이 과정을 계속 바복한다. 하지만 만약 50이 없다면, 모든 서랍을 다 확인하였는데에도 없다면, 무엇을 반환해야 할까? 거짓이다. 따라서 이 알고리즘에서 루프가 끝난 후 마지막에는 나머지 상황을 처리하기 위해 거짓을 반환해야만 한다. 루프를 다 돌았는데에도 50을 찾지 못하면 50이 없다는 의미이다.

 

지금부터는 이 코드가 Nizari가 반으로 쪼개가며 풀었던 두 번쨰 알고리즘과 비교하여 얼마나 효율적이거나 비효율적인지 보자.

이진 탐색이라고 했다. 여러 구현 방법이 있지만 아래와 같이 작성하였다.

우선 가운데를 확인하고 만일 숫자가 50이면 참이라는 불리언값을 반환한다. 이렇게 될 수도 있지만 만약 중간 숫자가 50보다 작다면 Nizari는 왼쪽을 탐색한다. 50이 중간 숫자보다 작다면 왼쪽 절반을 탐색한다. 반면 50이 값보다 작다면 오른쪽을 탐색한다. 

하지만 가능한 경우가 여기 하나 더 있다. 중간에도 없고, 왼쪽, 오른쪽에도 없고 아무데도 없는 것이다. 이 네 번째 경우를 다음과 같이 표현해보자. 맨 위에 이 네 번재 경우로 배열에 더 이상 요소가 없다면 거짓을 반환하도록 한다. 아무것도 없기 때문이다. 계속해서 배열을 절반으로 나누다보면 결국 남은 배열이 없게 된다. 우리는 더이상 배열에 아무것도 없다는 결론을 내릴 수 있다.

 

생각해보기

만약 정렬되지 않은 배열이 있다면, 선형 검색이 빠를까요 이진 검색이 빠를까요?

정렬 되지 않은 배열에 이진 검색을 하게 되면 배열에 값이 있는 데에도 값을 못 찾고 종료되는 경우가 발생할 것이다. 따라서 문제가 발생하기 때문에 이진 검색을 할 수 없다.

만약 우연히 정렬이 된 배열이 존재한다고 하더라도 이는 이진 검색보다 선형 검색의 경우가 더 빠르다. 선형 검색의 코드가 이진 검색보다 더 코드가 짧기 때문에 더욱 빠르게 실행하여 원하는 값을 찾게 될 것이다.

 

 

2. 알고리즘 표기법

들어가기 전에

우리가 프로그램을 작성한 후에 실행하면 작업이 완료될때까지 어느정도 시간이 소요됩니다. 아주 간단한 프로그램인 경우에는 실행 시간을 걱정할 필요가 없지만, 처리하는 데이터가 많아지고 처리하는 작업이 복잡해질수록 실행 시간은 매우 중요해집니다. 특정 알고리즘을 작성하였을 때 그 실행 시간을 표기하는 방법을 배워보겠습니다.

학습 목표

알고리즘의 실행 시간의 상한과 하한을 표기할 수 있습니다.

핵심 단어

• Big O
• Big Ω

 

학습하기

위의 그림은 첫 주에 봤던 그림이다. 우리가 이를 어떻게 분석할 수 있을까?

알고리즘은 직선으로 그려지는 선형의 형태이거나(Eric의 방법), 혹은 좀 더 굴곡이 있거나 로그 형태일 수 있다(Nizari의 방법). 각각 다르게 생긴 이 모양은 각 알고리즘이 최악의 경우 필요한 계산 수를 나타낸다. 전화번호부나 서랍의 개수를 n으로 나타내면 Eric처럼 왼쪽부터 오른쪽까지 n번 확인하여 Mike Smith와 숫자 50을 찾을 수 있다. 

첫 주에 제가 한 번에 2쪽을 확인하여 속도를 높였지만, 하지만 선의 모양은 비슷하다. Eric도 그렇게 했을 수도 있다. 양손으로 서랍을 한 번에 두 개씩 볼 수도 있다. 앞서 본 두 알고리즘의 중간 단계 정도 될 것이다. 로그 함수는 좀 더 완만한 형태를 보이고 있다.

오늘은 이러한 관련 용어를 배우고 정리하여 단순히 선형 탐색과 이진 탐색 뿐 아니라, 다양한 알고리즘에 대해 배울 것이다.

 

Big-O

컴퓨터 과학자들은 알고리즘을 설명하기 위해 특정 용어를 사용한다. 알고리즘이 얼마나 잘 설계되어 있는지, 또 코드가 얼마나 잘 구현되어 있는지 말해준다. 가장 일반적으로 Big-O 표기법을 사용한다. 이름 그대로 대문자 O로 나타낸다. Big-O 표기법은 어느 정도 크기인지를 말해준다. 누군가 당신의 알고리즘이 얼마나 효율적인지 물어본다면, 즉 코드의 효율성을 묻는다면 손으로 이렇게 뻗어 나타내어 은유적이면서도 직관적으로 코드의 속도를 대략 알려줄 수 있다.

n번, n/2번, log n번이라고 말하지 않고 컴퓨터 과학자들은 보통 그 알고리즘은 O(n) 또는 O(n/2)라고 또는 O(log n)이라고 말한다. 다음과 같이 문자로 표기하고 O(n)이라고 읽는다. 수학에서의 함수 표기와 비슷하게 생겼다.

사실 Big-O 표기법을 사용하면, 손짓과 비슷한 느낌을오 대략적인 추정값을 표현하는 것이다.

O(n)와 O(n/2) 이 두 개의 선은 매우 비슷하게 생겼기 때문에 나누기 2를 없애버려도 된다.

왜 이렇게 해도 되는지 곧 알아본다. 어쨌든 이 두 선은 매우 비슷하니 같은 것으로 생각하자.

로그 함수가 가물가물할 수도 있지만, 밑의 2 또한 큰 의미가 없으므로 없다고 생각하자. 밑이 2, 3, 10일 수도 있지만 로그 함수끼리는 비슷한 모양이다. 따라서 크게 상관이 없다. 

이 빨간 선과 노란 선이 같다고 말할 수 있는 이유는, 만약 우리가 푸는 문제가 충분히 크다면, 즉 문제가 계속 커져서 이 정도 크기의 화면에 담기도록 축소해서 보기 위해 x축과 y축을 늘려본다면 아래와 같이 노란 선과 빨간 선은 아주 가까워 질 것이다.

게속 그림을 축소하여 더욱더 크기가 큰 문제를 본다면 두 선은 결국 거의 같아 보일 것이다.

따라서 컴퓨터 과학자는 알고리즘의 효율성을 설명할 때 정확히는 O(n/2)일지라도 그냥 O(n)이라고 말한다. 로그의 경우도 그냥 O(log n)이라고 한다. 밑이 뭐든 상관없다.

매우 수학적인 것 같으면서도 손짓과 같이 대략 설명하는 셈이다.

 

세상에는 다양한 알고리즘이 있는데, 여기 가장 대표적인 실행 시간을 요약해보았다.

실행 시간이란, 프로그램이나 알고리즘이 동작하는 데 걸리는 시간이다. 몇 초가 걸리는지 혹은 몇 번의 계산 과정이 필요한지를 말한다. 

목록을 보면 익숙한 표기들이 보인다. 이 목록에 우리가 배운 알고리즘을 채워보자.

선형 검색은 O(n)이다. 최악의 경우 Eric은 모든 서랍을 열어본다. 몇 주전에 제가 전화번호부에서 Mike Smith를 찾기 위해 모든 장을 확인해야만 했다.

이진 탐색은 이 중에 O(log n)이 된다. 더 빠르다. 목록 아래쪽에 있다는 것은 위쪽에 있는 것보다 빠르다. 

현재는 여기까지 배웠는데 나머지에는 어떤 알고리즘이 놓이게 될까? 어떤게 더 느리고 어떤게 더 빠른지 오늘 알아보자.

 

Omega Ω

컴퓨터 과학자에게 사실 또 다른 도구가 있다. 그리스어 대문자 Omega이다. 이의 의미는 Big-O의 반대이다.

Big-O는 알고리즘을 수행하는데 필요한 시간의 상한선을 의미한다. Eric의 경우 7개의 서랍 중 50을 찾기 위해 n번이 필요한 선형 탐색을 했다. 따라서 O(n)이라고 표현한 것이다. 최악의 경우에 필요한 상한선을 말한다. 즉, 알고리즘 실행 시간의 상한을 나타낸 것이다.

Omega를 사용하면 최상의 경우를 나타낼 수 있다. 즉, 알고리즘 실행 시간의 하한을 나타내는 것이다.

Eric이 선형 탐색을 할 때 최악의 경우 n번 또는 7번의 과정이 필요하다. 최선의 경우는 몇 번의 과정이 필요할까? 한 번이다. 운 좋게도 50이 첫 번째 서랍에 있을 수도 있다. Nizari의 경우 50을 찾기 위해 가운데부터 살펴본다면 최소 몇 번에 가능할까? 한 번에 가능하다. 

즉 알고리즘의 상한선도 있지만 가끔 운이 좋아서 입력값이 특정 순서로 들어온다면 실행 시간이 예상보다 짧아질 수 있다.

여기 새로운 목록이 있다. 앞서 본 목록과 흡사하지만 Big-O가 아닌 Omega를 사용한다. 지금까지 배운 알고리즘을 적용해보자.

선형 탐색을 Omega로 표현하면 어떻게 될까? Ω(1)이다. Eric의 선형 검색을 사용하면 최선의 경우에는 한 번이면 된다. 즉 선형 탐색은 Ω(1)이다. 

이진 탐색의 경우 최선의 경우가 log n이 아니다. 운이 좋으면 한 번이기 때문에 Ω(1)이다.

 

이제 우리는 어떤 알고리즘이나 코드가 주어지는 입력값에 따라 얼마나 좋은지 파악할 수 있는 척도가 생겼다.

Big-O와 Omega이다.

 

Q1. Ω(n)를 갖는 알고리즘에는 어떤게 있나요?

최선의 경우에도 n번의 과정이 필요하다. 예로 들어서 서랍의 개수를 세어야 하는 것과 같이 말이다. 최악의 경우에 모두 확인하기 때문에 O(n)이다. 또한 Ω(n)이다. 최선의 경우에도 하나씩 살펴볼 수 밖에 없기 때문이다. 아니면 정확한 답이 아니기 때문이다.

 

Q2. Omega값과 Big-O값 중 어느 것이 좋아야 더 좋은 알고리즘인가요?

후자이다. 차차 알게될 것이다. 컴퓨터 과학자가 가장 걱정하는 부분은 최악의 경우에 프로그램이 어떻게 동작할지 혹은 평균적으로 어떻게 동작하는지이다. 최선의 경우도 물론 좋지만, 이미 정렬된 입력값을 받아 매우 빠르게 정렬한다면 누가 좋다고 생각할까? 물론 이 경우는 예외적이다. Big-O와 상한선이 우리가 좀 더 신경 써볼 부분이다.

• 상한선 : 더 이상 올라갈 수 없는 한계선
• 하한선 : 더 이상 내려갈 수 없는 한계선

 

생각해보기

실행시간의 상한이 낮은 알고리즘이 더 좋을까요, 하한이 낮은 알고리즘이 더 좋을까요?

상한이 낮은 알고리즘이 좋다. 최상의 경우보다는 최악의 경우를 더 고려해야 하기 때문이다.

 

 

3. 선형 검색

들어가기 전에

주어진 배열에서 선형 검색으로 값을 찾는 방법을 알아봅니다. 전화번호부와 같이 배열이 여러개가 있는 경우, 한 배열의 특정 속성값을 찾고 동일한 위치의 다른 배열의 속성값을 출력하는 방법도 배워봅니다. 또, 이를 더 간단하고 확장성있게 구현하는 방법을 배워봅니다. 

학습 목표

주어진 배열 또는 구조체에서 선형 검색을 할 수 있습니다.

핵심 단어

• 선형 검색
• 구조체

 

이름 찾기 프로그램

위의 코드는 작동하지 않는다.

관계연산자(==)는 문자열에 사용할 수 없다. 문자열은 문자, 부울, 소수 혹은 정수와는 다르다. 즉 자료형이 다르기 때문에 문자열에는 ==을 사용할 수 없다.

문자열 자체는 배열로 여러 개의 문자로 구성된다. 두 문자열을 비교하고 싶다면 문자열 속에 문자를 하나씩 비교해야 한다. 전체를 한 번에 비교할 수는 없다.

하지만 파이썬이나 자바 같은 다른 프로그래밍 언어에서는 위와 같이 한 줄로 비교가 가능하다. 그러나 C는 모든 것이 low 레벨로 진행이 된다. 문자열을 비교하기 위해 등호를 사용할 수 없다.

 

따라서 아래와 같은 방법으로 문자열을 비교할 수 있다.

문자열을 비교하는 함수 strcmp에 첫 번째 비교 대상으로 names[i]를, 두 번째 비교 대상으로 "EMMA"를 적는다. strcmp함수는 두 문자열이 같다면 0을 반환한다. 양수를 반환하면 첫 번째 문자열이 알파벳 기준으로 큰 경우이고, 음수면 반대의 경우이다. 하지만 오늘은 두 문자열이 같은지만 확인하겠다.

또 strcmp는 <string.h>라이브러리에 있으므로 위에 #include <string.h>를 추가해야 한다.

하지만 위의 코드를 실행한 결과 이와 같은 결과가 출력됨을 확인할 수 있다. 배열에서 EMMA를 찾은 걸까, 못찾은 걸까? 그녀는 분명 여기 있는데 없다고 한다. 무엇이 잘못되었을까?

문제는 바로 마지막에 적어둔 not found가 무조건 출력된다는 것이다.

그럼 found를 출력한 후 바로 어떻게 해주어야 할까? return해주어야 한다. 결과가 성공적이라는 것을 알려주기 위해 일반적으로는 0을 반환하고, 성공적이지 않았을 경우 1을 반환한다. 숫자 자체에는 큰 의미가 없지만 관습이라고 하자.

0은 성공, 1은 실패이다.

위와 같은 코드로 실행할 경우 결과가 "Found"로 잘 나옴을 확인할 수 있다.

 

전화번호부 프로그램

이제 이 두 가지 개념을 하나의 프로그램으로 합쳐서 전화번호부 프로그램을 만들어보자.

이제 번호가 필요하다. 전화번호를 어떻게 저장하면 좋을까? 어떤 자료형을 사용하면 좋을까?

왜 문자열일까? 전화번호에는 -나 괄호가 있고 해외번호에는 + 기호도 있다. 이는 문자다. 숫자가 아니다. 따라서 int형이나 long형에 넣을 수 없다. 전화번호라고 부르지만 이제 프로그래머로서 사실 숫자가 아니라 숫자처럼 보이는 문자열로 나타내는 것이 더 적합하다. 게다가 특정 지역에서 통화를 하기 위해 0부터 누르게 되는데, 수학에서는 맨 앞의 0은 생략되어 버린다. 숫자처럼 보이지만 다른 요소들이 많다면 정수형으로 나타내는 것은 좋지 않다.

따라서 numbers를 문자열 배열로 선언하자.

이번에는 EMMA를 찾을 건데 정확하게는 이름이 아니라 번호를 찾을 것이다. 따라서 찾았는지가 아니라 그녀의 번호를 출력할 것이다.

조금전처럼 strcmp함수를 사용해서 names[i]와 "EMMA"가 같은지 확인한다. EMMA를 찾았고 번호를 출력하고 싶다면 ""에 무엇을 적어야할까? 문자열 표기를 위한 형식 지정자인 %s를 작성한다. 그리고 이름이 아니기 떄문에 name이 아닌 numbers를 작성한다. 다른 배열이지만 같은 위치에 정보가 있다.

위의 코드를 실행한 결과, 출력이 잘 나옴을 확인할 수 있다. 제대로 잘 작동하고 있다.

 

선형 검색의 비효율성

이제는 개선할 부분이 있는지 살펴보자.

하지만 이 코드의 설계에서 혹시 거슬리는 부분이 있을까? 개선할 방법이 있을까? 이 코드에 부자연스럽거나 자칫하면 위험할 만한 부분이 보일까?

이름을 올바른 순서로 나열하고 번호도 맞는 순서대로 나열했다고 가정하고 있다. 하지만 이것은 나만의 규칙에 불과하다. 동료나 친구와 함께 일할 때에도 이렇게 하기로 약속할 수도 있다. 하지만 이는 위험하다. 4개보다 더 많이 있다면 모든게 빠르게 엇나가기 시작한다. 혹은 만약 이름을 사전 순으로 정렬한다면 번호는 어떻게 정렬해야 할까?

사람의 이름과 번호를 같이 저장하는 상황을 보자. 오늘 우리는 우리만의 자료형을 만들어 볼 것이다.

int, bool, float, long을 보았지만 우리만의 자료형을 만들어 보자.

 

typedef struct

typedef. 새로운 키워드이다. 새로운 타입을 정의한다는 말이다. 구조체를 만드는데, 구조체(struct)는 C에 미리 정의된 키워드로 마치 그릇처럼 여러 가지 자료형을 담을 수 있다. struct는 여러가지 자료형을 위한 그릇이다.

어떤 것을 넣을까? 사람의 이름과 전화번호를 저장할 것이다. 이 구조체를 person이라는 이름으로 정의할 것이다. 단순히 person이라고 했지만, 이 문법을 사용해서 컴파일러에게, 즉 이 경우 clang에게 int, float, char, bool 뿐 아니라 이제 person이라는 자료형이 있다고 알려줄 수 있다. C에는 원래 없었지만 typedef struct person을 사용하여 만들었다. 그 안에 묶어둔 것은 이름과 번호 두 가지 정보이다. 

이제 무엇을 할 수 있을까? 코드를 수정하여 더 나은 설계를 만들어보자. 이 부분에서 people배열을 만들 것이다. 4명의 직원이 있으니 4명을 위한 people 배열을 만든다. 지금까지 해왔던 방식으로 자료형을 먼저 선언할 것인데, 사용할 자료형은 person이고 배열의 이름은 people라고 하자. 총 4명의 사람이 들어간다.

그럼 이 배열의 이름은 people이고 크기는 4이다. 배열 안에 각각 요소는 한 사람을 표현한다. 이 부분은 전과 같다.

배열의 내용을 채우기 위해 다음과 같이 할 수 있다.

적어야 할 양이 늘어나서 더 불편하게 느껴질 수 있지만, 이제 모든 정보를 한 번에 묶어서 표현할 수 있다. person 자료형의 값이 4개나 있고, 각각 person안에는 이름과 번호가 들어있다. 모든 정보가 엮여 있다. 제가 이름순으로 정렬해도 이름과 번호의 관계는 그대로 유지될 것이다.

마지막으로 아랫부분 코드를 수정해야 한다. 

typedef와 점(.)을 이용하여 더 복잡해진 것 같지만 더 잘 설계된 코드라고 할 수 있다.

앞으로 프로그래밍을 하면서 이렇게 캡슐화하여 많은 관련 정보를 한 번에 관리할 일이 많을 것이다. 특히 데이터베이스를 사용한다면 말이다.

 

Q. 저 코드를 더 간소화할 수 있을까요?

네 똑같이 중괄호를 사용할 수 있는데 이 경우는 코드가 더 지저분해져서 굳이 하지않았지만 가능은 하다. 하지만 사실 생각해보면 이 프로그램이 굉장히 멍청하다. 왜냐하면 제가 직접 적은 목록에서 EMMA를 찾기 때문이다. 동적이지 않다. 실제로는 getstring과 같은 함수를 사용할 것이다.

 

생각해보기

전화번호부와 같이 구조체를 정의하여 관리 및 검색을 하면 더 편리한 예는 또 무엇이 있을까요?

상품명에 관련된 정보들이 될 것이다. 예로 들어서 "식빵"이 있다면 이의 원가, 판매가격, 할인가격, 할인율, 재료, 유통기한 등 상품과 관련된 많은 정보들을 상품과 연관지어서 구조체로 정의할 수 있다. 그렇게 되면 유통기한이 얼마 남지 않은 상품을 관리하거나 검색하기 용이해질 것이다.

 

 

4. 버블 정렬(bubble sort)

들어가기 전에

어떤 배열이 주어졌을 때, 그 배열이 미리 정렬되어 있다면 훨씬 빠른 속도로 검색이 가능합니다. 정렬하기 위한 방법은 여러가지가 있고, 각각 실행 시간도 다릅니다. 이번 강의에서는 그 중 하나인 버블 정렬을 배워 보겠습니다.

학습 목표

버블 정렬의 원리와 실행 시간을 설명하고 구현할 수 있습니다.

핵심 단어

• 버블 정렬

 

학습하기

이제 우리는 Nizari나 Eric이 서랍을 이용해서 직접 보여주었던 개념을 코드로 구현할 수 있게 되었다.

이제 무엇을 해야할까? 사실 Niari의 경우 Brian이 이미 숫자를 정렬해뒀기 때문에 이득을 봤다고 할 수 있다. 하지만 대가가 있었다. 모든 숫자가 정렬될 때까지 기다려야 알고리즘을 수행해볼 수 있었다. 그렇다면 생각해볼 문제는, 정렬하는데 얼마나 많은 시간이 필요한지, 그렇다면 꼭 정렬한 후 숫자를 찾아야 할지, 아니면 정렬하지 않고 바로 탐색하는게 좋을지 이다. 특히 한 방법이 더 오래 걸린다면 말이다. 이것은 서로 상충될 것이다.

다음과 같이 생각해보자. 여러분에게 입력이 주어질텐데 정렬이 되지 않은 숫자들이다. 목표는 숫자를 정렬하여 반환하는 것이다. 어떻게 구현하면 될까? 예로 7, 2, 1, 6, 3, 4, 50처럼 정렬되지 않은 숫자들을 결과로 1, 2, 3, 4, 7, 50 순서로 출력하는 것이 목표이다. 이 방법을 어떻게 구현할 수 있을까?

 

버블 정렬(bubble sort)

거품이 떠오르듯 8이 왼쪽에서 오른쪽으로 움직이고 7도 마찬가지로 거품처럼 움직였다. 이를 반복하면 큰 숫자가 올바른 위치로 갈 때까지 움직인다. 이를 의사코드로 적어보면 다음과 같다.

다음 과정을 n-1번 반복했다. 왜 n-1일까? n명이 있고 서로를 비교한다면 최대 n-1번 비교할 수 있다. 그래서 Bonnie는 총 n-1번 지시했고, i가 0부터 n-2까지라고 나왔는데 무슨 과정을 의미할까? i는 인덱스고 사람을 배열로 생각하고 있다. i가 0부터 시작할 때 i번째 사람과 i+1번째 사람의 순서가 잘못됐다면 자리를 바꾸라고 했다.

이처럼 의사코드로 숫자와 단어 몇 개로 간결하게 표현할 수 있다. Bonnie가 내린 지시사항을 말이다. 그녀는 n-1번 지시를 내렸다. 그래서 점점 빠르게 계속 반복했던 것이다. 첫 번째 사람을 배열의 0번째 항목으로 여기고 그 다음 사람을 1번째, 2번째 항목으로 여겼다. 

그리고 한 명식을 i라고 한다면 다른 사람을 i+1라고 하고 순서가 맞지 않으면 자리를 바꾸게 했다. 계속 이를 반복해서 모두 정렬이 될 때까지 했다.

 

버블 정렬의 Big-O

총 몇 번의 과정이 필요했을까? 얼마나 걸렸을까? 버블 정렬 실행시간의 Big-O 표기는 어떻게 될까?

바깥 반복문은 n-1번 반복하고 안쪽 반복문 또한 n-1번 반복한다. 0부터 n-2까지니까. 이 수식을 곱해서 정리해보면 아래와 같이 나온다.

하지만 여기서 중요한 점은, 지수가 가장 큰 n^2의 영향력이 가장 크다는 점이다. n이 커질수록 n^2가 미치는 영향은 더 커지기 때문에 컴퓨터 과학자는 버블 정렬이 O(n^2)라고 말한다.

아까 봤던 상한선 목록에 버블 정렬은 맨 위에 놓이게 된다. 즉 버블 정렬을 하면 선형 탐색이나 이진 탐색보다 더 시간이 많이 든다는 것이다.

그렇다면 궁금해지는 것은, Eric과 Nizari 알고리즘 중에선 Nizari가 더 빨라서 좋았다. 하지만 정렬되어 있다고 가정했었다. 그렇기 때문에 이진 탐색이 선형 탐색보다 좋다고 하는 건 맞지 않다. 많은 시간이 들여서 항목을 미리 정렬한 후 이진 탐색을 시작할 수 있으니까. 딱히 이득이 없거나 오히려 더 느릴 수도 있다. 그렇기 때문에 상황에 따라 배열에 대해 여러 번 탐색을 해야 하는 경우라면 한 번 정렬해두는게 좋다. 그럼 빠른 검색으로 장기적인 이득을 볼 수 있다.

 

버블 정렬의 Omega

버블 정렬의 Omega는 뭘까? 버블 정렬은 좋은 입력값이 주어져도 크게 달라지지 않는다. 정렬 알고리즘에서 가장 좋은 입력값은 이미 정렬된 것이다. 정렬되어 있다면 사실 더 할 일이 없는 것이다. 하지만 버블 정렬은 무식하게 동작한다. 이미 정렬이 돼있어도 종료하라는 말 없이 그저 맹목적으로 n-1번 반복하고 내부에서도 n-2번 반복한다. 

버블 정렬의 실행 시간의 하한선은 무엇일까? 이미 정렬된 배열이 들어와도 여전히 n^2이다. 여전히 같은 횟수를 반복하기 때문이다. 따라서 버블 정렬의 하한선은 Omega(n^2)이다. 

 

생각해보기

버블 정렬이 효율적인 경우는 어떤 경우인가요? 반대로 어떤 경우에 비효율적이게 될까요?

버블 정렬의 Big-O는 O(n^2)지만 Omega의 경우도 Ω(n^2)이다. 따라서 다른 정렬과 비교했을 때 n이 너무 작은 값이거나 너무 큰 값일 때 시간이 많이 걸리므로 비효율적이다.

 

 

5. 선택 정렬(selection sort)

들어가기 전에

앞서 배운 버블 정렬은 직관적이지만 O(n^2)의 시간이 소요됩니다. 이 방법이 최선일까요?  이번에는 다른 정렬 알고리즘인 선택 정렬을 배워보겠습니다.

학습 목표

선택 정렬의 원리와 실행 시간을 설명하고 구현할 수 있습니다.

핵심 단어

• 선택 정렬

 

학습하기

더 잘할 수 있을지 보자. 근본적으로 다른 접근법을 사용하는 선택 정렬을 해보자.

선택 정렬에서도 비슷한 입력이 주어진다. Brian이 숫자를 임의의 순서로 돌 것이다. 현재 숫자는 정렬되어 있지 않다. 총 1~8 8개의 숫자가 있다. 

버블 정렬의 장점은 직관적인 방법이었다는 점이다. 왼쪽과 오른쪽을 보고 작은 문제를 풀어나가는 것이다. 하지만 근본적으로 정렬이라는 문제를 생각해보면 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 옮기는 방법은 어떨까?

6 3 8 5 2 7 4 1

가장 작은 수는 무엇일까? 6이다. 현재까지는 배열에서 가장 작은 값이다. 머릿속에 변수처럼 기억하자.

다음 수는 3이다. 3은 6보다 작으니 이제 6은 잊고 3을 가장 작은 수로 기억한다. 

8,5는 더 크다. 이제 2가 가장 작은 값이다. 이후 7, 4도 크다. 1은 더 작다. 맨 마지막에야 가장 작은 값인 1을 발견했다. 어떻게 할까? 그냥 옮기면 된다. 6을 쫓아내고 6과 자리를 바꾼다.

1 3 8 5 2 7 4 6

1이 제자리에 놓여 있다. 이제 n-1개의 수를 살펴봐야 한다. 다음으로 작은 수는 위와 같은 방법으로 훑어보았을 때 2이다. 그럼 2를 집어서 3과 자리를 바꾼다. 

그리고 계속 반복한다.

1 2 3 5 8 7 4 6

1 2 3 4 8 7 5 6

1 2 3 4 5 7 8 6

1 2 3 4 5 6 8 7

1 2 3 4 5 6 7 8

드디어 다했다. 쌍을 이뤄 앞뒤 순서를 교환하지 않았다. 매번 목표를 세워 가장 작은 값을 찾고 다음 작은 값을 찾는... 이 방법을 선택 정렬이라고 한다. 반복할 때마다 다음으로 가장 작은 수를 찾는다.

의사 코드로는 이렇게 적는다.

앞으로 어떤 상황이든 n개의 항목이 있다면 첫 번째 항목은 0이고 마지막 항목을 n-1이라고 한다. 컴퓨터 과학자는 0부터 n-1을 1부터 n을 세기 위해 사용한다.

i번째부터 마지막 항목 중 가장 작은 항목을 찾는다. 무슨 말일까? i를 0으로 초기화한다면 8개 중에서 가장 작은 항목을 찾으라는 것이다. 그리고 그 항목을 i번째 항목과 교환한다. 제일 작은 항목을 찾을 때마다 집어들어 위치를 바꾼다. 그리고 이 알고리즘을 계속해서 반복한다.

 

선택 정렬의 Big-O

그러면 선택 정렬이 더 나을까? 보자. Big-O 표기법으로 배열을 정렬하는데 얼마나 걸릴까? 어떻게 생각해볼 수 있을까?

실제로 가장 작은 항목을 찾는데 걸리는 시간을 계산해보면 모든 항목을 봐야하기 때문에 n번의 과정이 필요하다. 첫 번째 과정에서는 모든 항목을 다 살펴봐야 한다. 따라서 가장 작은 수를 찾는데 거의 n번의 과정이 필요하다.

그 후 1은 제자리로 돌아오고, 불빛을 켜면 옆에 7개가 남게 된다. 이제 n-1번 과정이 남는다.

2번을 하고 나면 n-2, 다음은 n-3, n-4, .. 그리고 마지막에는 한 숫자만 남는다.

그렇다면 총 몇 번의 과정일까? n번으로 시작해서 n-1을 더하고, n-2번 그리고 계속 더하면 총 몇번이 될까?

위와 같이 n(n+1)/2이 된다. 그리고 아래와 같은 과정으로 풀 수 있고, 결과는 O(n^2)가 된다.

따라서 n이 커질수록 저 공식에서 우리가 신경 써야 할 부분은 점점 빠르게 커져서 가장 빠르게 증가하는 항이다.

따라서 선택 정렬 또한 O(n^2)이다. 근본적으로 다른 알고리즘이지만 실제 같은 성능을 갖는다. 더 잘하지 못했다.

 

선택 정렬의 Omega

선택 정렬의 코드가 이렇게 된다면 이미 정렬된 배열을 받으면 이득을 볼까? 아니면 맹목적으로 n^2번의 일을 계속해서 반복할까? 최선의 상황인 경우 선택 정렬을 해보자. 앞에 놓인 수만 알 수 있기 때문에 같은 코드를 계속 반복하게 된다. 즉 횟수도 똑같고 최선의 경우에도 시간을 낭비하게 된다. 선택 정렬은  Ω(n^2)이기 때문이다.

 

 

6. 정렬 알고리즘의 실행시간

들어가기 전에

지금까지의 강의에서 정렬 알고리즘이나 검색 알고리즘을 학습하면서 그 실행 시간의 상한과 하한도 함께 배워 보았습니다. 이번 강의에서는 각 알고리즘들의 실행 시간을 비교해보고, 그 시간을 좀 더 단축시키는 방법이 있을지 알아보겠습니다.

학습 목표

여러 정렬 알고리즘과 검색 알고리즘의 실행 시간을 Big O와 Big Ω로 정의할 수 있습니다.

핵심 단어

• Big O
• Big Ω

 

버블 정렬의 실행 시간 단축화

저런, 우리는 이 문제에 대한 나쁜 해답을 2개나 배웠다. 더 잘할 수 없을까?

버블 정렬로 다시 돌아가 보자. 버블 정렬은 인접한 항목들의 위치를 바꾼다. 계속 반복해서 모든 게 정렬될 때까지 말이다. 언제쯤 배열 앞뒤를 훑는 걸 그만둬도 될까? 한 명 한 명 보며 i와 i+1번째를 살펴보며 언제 정렬이 다 됐다고 결론을 내릴 수 있을까? 

지원자를 봤는데 아무것도 하지 않으면 더 일을 할 필요가 없다. 알고리즘은 n-1번 반복하라 했지만, 여기에 알고리즘을 멈추거나 줄이는 조건문이 있으면 시간을 단축할 수 있을 것이다. 

버블 정렬도 마찬가지다. 의사코드를 교환이 없을 때까지만 반복하도록 하면 된다.

1 2 3 4 5 6 7 8

버블 정렬을 해보자. 1,2 2,3 3,4 4,5 5,6 6,7 7,8 아무것도 교환하지 않을 것이다. 하지만 만약 알고리즘이 하라는대로 다시 n-1번을 진행한다면 교환이 일어나지 않았다는 답을 계속 돌려받을 것이다. 교환이 없을 때 알고리즘을 일찍 종료한다면, 최선의 경우에는 몇 번의 과정이 필요할까? n-1번이다. 8개의 항목이 있으니 7개의 쌍을 비교할 것이다. 즉 n-1개 이다. 최선의 경우 버블 정렬의 하한선은 더이상 n^2가 아닌 n이 된다.

이렇게 조금만 머리를 쓰면 알고리즘의 실행 시간을 줄일 수 있다.

정렬 알고리즘 시각화

이제 알고리즘을 시각화하여 조금 다른 관점에서 보자. 각각 알고리즘을 그래프로 시각화한 모습을 아래의 시각화 도구 사이트에서 볼 수 있다.

www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

여기 숫자 배열이 있는데, 각 숫자는 막대로 그려져 있다. 짧은 막대는 0, 1, 2와 같은 작은 값이다. 긴 막대는 99나 100 같은 큰 값이다.  사람을 막대로 표현한 것이다. 

우리도 보다시피 많은 과정이 필요하다. 절반 정도 하면 속도가 빨라진다. 하지만 n^2번의 과정인 것이 체감된다. n^2는 실행 시간으로 좋은 상한선은 아니다. 특히 배열 순서가 정말 임의라면 말이다.

 

이번에는 선택 정렬을 보자. 위와 동작 방식이 다르다. 가장 작은 수를 가장 왼쪽으로 옮긴다. 버블 정렬은 큰 값이 오른쪽으로 떠오른다면 선택 정렬은 가장 작은 값을 찾아서 제 자리에 차례차례 둔다. 하지만 이도 시간이 많이 걸린다. 

 

 

7. 재귀

들어가기 전에

알고리즘을 구현하기 위해 코드를 작성하다 보면 동일한 작업을 반복해야 할 때가 있습니다. 이러한 작업을 함수로 구현하면 코드를 보다 효율적으로 만들 수 있음을 배웠습니다. 하지만 함수 내에서도 동일한 작업이 반복되는 경우는 어떨까요? 이번 강의에서는 함수를 함수 내에서 재사용하는 방법, 즉 재귀적으로 호출하는 방법을 배워 보겠습니다.

학습 목표

함수를 재귀적으로 사용하는 코드를 작성할 수 있습니다.

핵심 단어

• 재귀

 

학습하기

이번 주는 알고리즘과 구현에 대해 배울 것이다. 우리는 학교를 포함한 실생활에서 투표를 자주 한다. 그리고 여러 가지 알고리즘을 통해서 다양한 결론을 내릴 수 있다. 여러분이 누군가를 뽑으면 사용되는 알고리즘에 따라 기록 방식이 달라질 수 있다.  그리고 이런 부분이 실제로 선거 결과에 영향을 미칠 수 있다. 앞으로 과제 중 3번째 과제는 투표와 관련된 다양한 알고리즘을 구현하는 것이다. 예를 들면 가장 간단히 제일 많은 표를 받은 사람이 뽑히는 '최대 득표수 방법'을 사용하거나, 혹은 결선 투표처럼 한 명이 아니라 기호에 따라 여러 명의 순위를 매길 수도 있다. 그리고 프로그램이나 많은 사람이 동원되어 순위에 따라 승자를 결정하는 것이다. 이렇게 학교나 실생활에 영향을 줄 수 있는 다양한 방법이 있다. 이번 주에는 이런 개념을 코드로 다뤄볼 것이다.

 

재귀 (Recursion)

이제 버블 정렬이나 선택 정렬보다 근본적으로 더 나은 알고리즘이 있나 보자. 사실 수많은 정렬 알고리즘이 존재하는데 우리는 그중에 중요한 몇 가지만 볼 것이다.

지금까지 본 O(n^2)보다 더 나은 알고리즘이 있는지 찾아보자. 그러기 위해 지금부터 컴퓨터 공학을 배우면서 여러분의 생각을 흔들어 버릴 수많은 개념 중 하나를 소개할 것이다. 

첫 주로 돌아가보면 모든 게 간단했다. 전화번호부에서 Mike Smith를 찾아보았다. 그 때는 프로그래밍 방법 중 반복문을 강조하여 배웠었다. 3번째 줄로 돌아가 무언갈 계속 반복해서 하는 것이다. 반복문의 예시이다. 결국 반복하라는 의미이다. 아주 간단하다. 하지만 이 알고리즘을 조금 다르게 혹은 더 좋게 만들 수 있지 않을까? 위 코드의 노란 부분인 반복문을 없애면 더 빠르고 간결하게 풀 수 있을지 보자.

여기를 보면, 책의 왼쪽의 가운데를 펼쳐보고 여기는 오른쪽의 가운데를 펼쳐보라고 한다. 이렇게 왼쪽이나 오른쪽의 가운데를 확인하는 이유는 오른쪽이나 왼쪽의 남은 절반에서 Mike Smith를 찾기 위해서였다. 중요한 사실은 전화번호부의 크기를 절반으로 줄인다는 것이다.

알고리즘은 사실 똑같다. 그렇다면 복잡하게 여기저기 이동하며 이것저것 다시하라 하지 말고 의사 코드를 간단하게 줄여서 책의 왼편을 탐색하거나 오른편을 탐색하라고 해보자. 코드에서 빈 줄을 없애서길이를 줄여보자. 특정 줄로 가라고 알려줄 필요 없이 무엇을 할지만 알려주면 된다.

노란색 두 줄이 새롭게 추가된 줄이다. 순환 논리처럼 보일지도 모른다. Mike Smith를 어떻게 찾을지 물어보면 그냥 MIke Smith를 찾으라고 하는 것과 같다. 여기서 중요한 점은, 단순히 같은 것을 반복시키는 게 아니라 Mike Smith를 이렇게 큰 전화번호부에서 찾는 데 없다면 더 작은 크기에서 다시 찾아보라고하며 알고리즘 다음 단계에서의 문제의 크기를 계속 절반으로 줄여나가는 것이다.

이것은 재귀라는 프로그래밍 기법의 예시이다. 여러분의 프로그램이나 알고리즘이 스스로 계속 호출하는 것이다. 화면의 코드는 Search라는 함수이다. 재귀 함수는 내부에서 자기 자신을 호출한다. 머리에 혼돈이 올 수 있지만 곧 자세히 배울 것이다. 여기 Search함수에서 노란색으로 표시한 두 줄이 줄어든 문제에서 다시 검색하라고 Search함수를 반복적으로 호출하기 때문에 재귀이다.

이를 적용해보자. 이전에 봤던 피라미드와 다른 피라미드가 있다. 왼쪽에서 오른쪽으로 내려가도록 정렬되어 있다. 이런 피라미드를 만들려면 코드를 어떻게 작성하면 될까? iteration.c 코드를 작성하여 알아보자.

반복문을 사용하여 좀 더 정확히는 중첩 반복문으로 마리오 피라미드를 성공적으로 구현했다.

하지만 마리오 피라미드에는 흥미로운 점이 있다. 이게 흔한 구조일까? 높이 4의 피라미드를 어떻게 정의할까? 분명 높이 3의 피라미드에 한 줄을 추가한 것이다. 높이 3의 피라미드는 무엇일까? 높이 2의 피라미드에 한 줄을 추가한 것이다. 높이 2의 피라미드는? 높이 1의 피라미드에 한 줄을 더한 것이다.

이를 재귀적 정의라고 한다. 눈에 보이는 혹은 가상의 물체의 구조를 그 물체의 자체를 이용해서 설명하는 것을 말한다. 특수한 경우가 있다. 높이가 1이라면 높이 0의 피라미드는 뭘까? 아무것도 아니다. 반환, 종료 혹은 정지 등 알고리즘에 맞게 처리 해야 한다. 시작점에 대해서는 이건 특별한 경우이므로 아무것도 하지 않고 재귀적으로 자기 자신을 호출하지 않도록 알려주어야 한다.

재귀 호출의 원리를 또 이용해보자. 한 번 더 해보자. re cursion.c 파일을 만들며 알아보자. 

이번에는 중첩문을 사용하지 않고, 작은 피라미드로 큰 피라미드를 정의할 것이다. 그려야 할 피라미드의 높이가 4라면 이 정의에 따르면 제일 먼저 뭘 해야할까? 높이 4의 피라미드를 어떻게 그릴까? 4에서 1을 뺀 값인 3 크기의 피라미드를 그리는 것이다. 이는 코드로 h-1을 입력하는 것이다. 이렇게 하면 높이가 h-1인 즉 3인 피라미드를 그린다. 

하지만 아직 끝난게 아니다. 이렇게 하면 컴파일도 안된다. 현재는 끝없이 자신을 호출하기 때문이다. 피라미드 크기가 3, 2, 1, 0, -1, -2 처럼 1을 빼기만 하면 끝나지 않을 것이다. 따라서 시작점이 필요하다. 어떤 조건에서 아무것도 그리지 않아야 할까? h==0이라면 반환해야만 한다. 시작점인 것이다. 하드 코딩된 조건문으로 의도치 않은 반복을 막는다.

 한 가지 더 해야 할 일이 있다. 위의 표시된 부분으로 이 코드가 영원히 반복하지 않도록 해야한다.

방금 높이 3 피라미드를 그렸으니 다음 뭘 해야할까? 이제 그려야 할 것은 높이 4 피라미드 줄을 추가하는 것이다. 높이 h-1의 피라미드를 그려주는 함수가 있다고 가정하고 이제 한 줄을 추가로 그려주는 부분을 구현해보자.

높이 h-1 피라미드를 그린 후, 위와 같은 코드를 추가하면 된다. 반복문이 필요하지만 한 번이면 충분하다. 

네 번재 줄에서 h가 4일 때 몇개의 #를 그려야할까? 0 1 2 3. 4개이다. 추가한 코드는 4개의 #를 출력해준다. 

그리고 이전의 위의 코드가 놀랍게도 그 위에 나머지를 전부 출력한다. 높이 3의 피라미드 말이다. 그리고 그 위 코드는 음수가 돼도 계속 호추랗지 않도록 막아준다. 즉 h=0이면 멈추라는 것이다.

명시적으로 출력한 것은 한 줄에 해당하는 벽돌이다. 재귀적으로 스스로를 호출하면서 이진 탐색이나 분할 정복법에서처럼 기존 문제보다 더 작은 크기의 문제를 풀어간다. 문제를 조금씩 먹어 치우는 것이다.

 

Q. 반복문 다음에 어떻게 되돌아가서 출력하나요?

그게 아니다. 가장 먼저 출력한다. IDE의 디버깅 기능을 사용하면, 20번 줄이 호출되면 높이 3의 피라미드를 그려 달라고 호출하고, 2로 다시 호출하고, 1로 다시 호출한다. 높이 1에서는 어떻게 될까? # 하나를 출력한다. 그리고 #2개를 출력한다. 그리고 # 3개, # 4개를 출력한다.

여기서 출력을 하기 전에 draw함수를 호출하기 때문에 정확히 어떻게 동작하는지는 모르겠지만 매우 잘 돌아간다. 우선 여기 시작점의 조건문인 h==0이 끝없이 반복하는 것을 막아주고, 그리고 여기 다른 경우인 for문에서 계속 피라미드를 한 줄씩 그려준다.

Q. 내려갔다가 올라오는 것인가요?

맞다. 방금 말한 것처럼 우리는 몇 주 후 '스택' 개념에 대해 배우면서 어떻게 이게 가능한지 볼 것이다. 우선은 함수가 초기에 주어진 입력보다 더 작은 입력을 가지고 계속해서 자신을 호출하는 것만 이해하자.

 

(+) 컴퓨터 과학자도 유머가 있다!

구글에서 recursion을 입력하게 되면 뭐가 나오냐면, 

이렇게 뜬다 (ㅋㅋㅋ)

 

 

8. 병합 정렬(merge sort)

들어가기 전에

앞서 배운 정렬 알고리즘은 직관적이지만 실행 시간의 상한이 다소 높았습니다. 반복되는 작업이 많았기 때문인데요, 지난 강의에서 배운 재귀를 활용하면 정렬 알고리즘을 더 효율적으로 만들 수 있을까요?

학습 목표

재귀를 활용한 병합 정렬을 구현할 수 있습니다.

핵심 단어

• 병합 정렬

 

학습하기

이제 재귀를 사용해서 정렬 문제를 풀어보자. 병합 정렬이라는 알고리즘이 있다. 버블 정렬이나 선택 정렬보다도 뛰어난 알고리즘으로 널리 알려져 있다. Big-O만 봐도 더이상 n^2가 아니다.

실생활에 많은 것이 정렬되어 있다. 휴대폰 속 연락처나 페이스북이나 인스타그램 친구 목록처럼 클라우드에서 사용하는 대부분 앱은 정렬을 사용한다. 하지만 정렬하는 데 느리다면 매우 당혹스러울 것이다. n^2처럼 말이다. 

 

병합 정렬의 의사 코드는 이렇게 생겼다.

입력으로 어떤 정보의 배열이 주어졌을 때 이렇게 동작한다.

받은 입력에 항목이 하나라면 그냥 반환한다. 정렬할 게 없다. 우리의 시작점이다. 가장 단순한 경우라서 하드코딩 할 수 밖에 없다. 이런 상황에는 이렇게 하라고 명시적으로 적어야 한다. 항목이 한 개라면 이미 정렬된 거나 다름 없다. 순서가 틀린 게 없기 때문이다.

다른 경우는 흥미롭다. 마리오 예제와 같이 병합 정렬을 사용하여 모든 배열을 정렬하고 싶다면, 우선 왼쪽 절반을 정렬하고, 오른쪽 절반을 정렬한 후 짜집기를 하듯이 하나의 배열로 합치면 된다. 합쳐진 배열 또한 정렬되도록 말이다.

병렬 정렬은 세 단계로 구성된다. 왼쪽 정렬과 오른쪽 정렬, 그리고 이 두 배열의 병합이다.

다시한번 적절한 비유를 들자면, 이 과정은 롤러코스터를 탈 때처럼 꽉 잡고 집중해야 한다. 

여기 정렬되지 않은 숫자 배열이 있다.

 

목표는 버블 정렬이나 선택 정렬보다 빠르게 정렬하는 것이다.

병합 정렬은 왼편 정렬, 오른편 정렬, 그리고 병합이다. 그게 끝이다. 마리오 예시처럼 높이 h-1피라미드와 시작점을 출력하면 끝이다. 재귀 알고리즘의 핵심이다.

왼쪽 절반은 뭘까? 이 4개의 수이다. 이 숫자 4개의 배열을 정렬하자. 뭘로 할까? 병합 정렬이다. 왼쪽을 정렬하고 오른쪽을 정렬하고 하나로 합친다. 아무것도 하지 않는 것과 같다. 바로 다른 것을 정렬하라고 한다.

왼쪽 절반인 7와 4를 정렬해보자. 크기가 2인 배열은 어떻게 할까? 병합 정렬을 한다. 왼족과 오른쪽을 정렬하고 하나로 병합한다. 헛소리 같다. 아무 일도 하지 않았는 데에도 정렬 중이라고 하니까. 우선은 보자.

 

이것이 왼쪽의 절반이다. 크기가 1인 배열은 어떻게 정렬할까? 끝이다. 이미 정렬된 것이다. 반환하여 이 과정을 영원히 반복하지 않도록 한다.

다음은 뭘까? 오른쪽 정렬이다.

오른쪽 정렬도 이미 되어 있다.

이제 흥미로워질 텐데, 세 번째 과정이 무엇일까? 크기 1의 배열 2개를 합친다. 추가 공간이 필요해 아래와 같이 열을 하나 추가하겠다. 컴퓨터의 메모리를 추가한다. 

4가 당연히 먼저고 7이 뒤에 놓인다. 병합 과정인 것이다. 

병합이란 두 배열 중에서 가장 작은 값을 꺼내 다른 배열의 가장 작은 값 다음에 두는 과정을 말한다.

이건 정렬된 크기 2의 배열이다.

다음 두 번째 과정은 뭘까? 방금 왼쪽 절반을 정렬했으니, 오른쪽 절반을 정렬해야 한다. 30초 전 하던 얘기를 잘 떠올려봐라. 오른쪽 절반을 어떻게 정렬할까?

왼쪽 절반 부분

 

오른쪽 절반 부분

왼쪽 절반은 끝나있고, 오른쪽 절반도 끝나있다. 이제 합치면 된다. 이 두 배열을 어떻게 합칠까?

2가 먼저 오고, 5가 다음에 온다. 방금 이 배열의 오른쪽 절반을 정렬했다.

왼쪽 정렬과 오른쪽 정렬을 했으니 다음 세 번째 과정은 뭘까? 병합이다. 어떻게 할까? 두 배열이 있는데 어떻게 바른 순서로 병합할 수 있을까?

2가 먼저, 그다음 4, 5, 7이 오면 된다.

이제 원래 배열의 왼쪽 절반을 정렬했다. 그럼 두 번째 과정이 뭘까? 오른쪽 절반을 정렬하는 것이다.

오른쪽 절반을 정렬하기 위해 그 안의 왼쪽 절반을 정렬해야 하는데, 

다시 왼쪽 절반을 정렬하려 하면 완료되어 있고 오른쪽도 완료됐다.

병합은 3 그리고 6 순으로 된다.

이제 숫자 4개 중 왼쪽 절반을 정렬했다. 다음은? 오른쪽 절반을 정렬한다. 8과 1에 대해 왼쪽도 오른쪽도 정렬되어 있다. 하나로 합치면 1, 8이 된다.

 

세번째론 뭘 할까? 병합이다. 오른쪽과 왼쪽을 합쳐보자. 1 3 6 8 이다. 2분 전으로 돌아가보면, 이게 전체 배열의 오른쪽 절반이었다. 그럼 세 번째 과정은 뭘까? 병합이다.

두 배열을 합쳐보자. 1 2 3 4 5 6 7 8 이다. 모두 합쳐졌다. 많은 과정이 있었지만 사실 지금까지 했던 방법 중 가장 적은 횟수로 끝냈다.

어떤 일이 일어났냐면, 실제로 한 것은 크기 8의 배열을 쪼개어 어느 순간 크기 1의 배열 8개를 만들었다. 항목이 한 개면 더 이상 할 게 없으니 반환한다. 그 다음에는 크기가 2인 배열 4개로 만들고, 그리고 크기가 4인 배열 2개로 만들고, 결과적으로 크기가 8인 하나의 배열로 합칠 수 있었다.

여기 패턴이 보이나? 아래에서 위로 올라가는데, 가장 아래 배열이 하나 있고 절반으로 나누고 그걸 다시 나누고 그걸 다시 나눴다. 첫 주부터 매번 무언가를 계속해서 절반으로 나눌 때 이 과정을 설명하는 수식이나 함수가 뭐가 있었죠? 로그이다. CS50에서 혹은 어떤 알고리즘을 얘기할 때 무언가를 절반으로 계속 나눈다면 로그 함수로 표현할 수 있다. 크기가 8인 배열을 쪼개서 크기가 1인 배열 8개로 만드는데 필요한 과정은 밑이 2인 log n이다. 대략 log n이라고 하죠. 이 그림의 높이가 log n이다.

쪼개는 과정이 한 번 있을 때마다 합치는 과정이 한 번 있다. 세 번째 과정으로 가장 중요하다. 병합을 할 때마다 4개와 4개 또는 2+2+2+2 또는 1+1+1 ... 1 하며 총 8개의 항목을 합쳤다. 즉 모든 n개의 항목을 확인한다. 

이 그림처럼 8개 혹은 n개가 있다고 하면 높이는 log n이 된다. 나눌 수 있는 횟수가 log n번이기 때문이다. 그렇다면 병합 정렬의 실행 시간을 어떻게 될까? n 곱하기 log n이다. n개의 숫자를 다시 합쳐야 하는데, log(n)번 반복되기 때문이다. 이게 이 과정을 반복하는 횟수이다. 밑이 2인 log(8)을 계산해 보면, 역시나 3이 나온다. 

 

병합 정렬의 Big-O : O(n log n)

어떻게 이렇게 계산이 되는 지는 또 그저 받아드려야 하는 부분이지만, 중요한 것은 이 알고리즘이 근본적으로 더 빠르다는 것이다. 아까 목록에서 보면, 버블 정렬과 선택 정렬은 위에 잇다. 문제가 더 어려워지지만 훨씬 느린 알고리즘도 많을 것이다. 우선 병렬 정렬을 O(n log n)에 추가하자. 왜 중간에 놓일까? log n에 대해 완전히 익숙지 않을 수 있지만, 여기 n이 있고 그 위에는 n^2가 있으니, n보다 조금 작은 값을 곱해주면 그 중간이 된다. 곧 이게 무슨 의미인지 살펴볼 것이다.

 

병합 정렬의 Omega : Ω(n log n)

Omega는 어떨까? 최선의 경우 병합 정렬은 얼마나 걸릴까? 버블 정렬처럼 더이상 교환이 일어나지 않을 때 멈추는 최적화 기법은 없다. 항상 왼쪽 절반을 정렬하고 오른쪽 정반을 정렬한 뒤, 마지막으로 병합한다. 따라서 병합 정ㄹㄹ의 Omega 또한 n log n이다. 

우리의 두 번째 버전의 버블 정렬은 좋은 경우에 n번 만에 가능했다. 교환이 일어나지 않을 때 멈춘다면 말이다.

병합 정렬은 장단점이 있다. 최악의 경우 훨씬 빠르다. n^2가 아니고 n log n 이다. 하지만 최선의 경우, 여전히 시간 낭비를 한다. 컴퓨터 과학에서 자주 일어나는 일이다. 공짜는 없다. 상한선을 개선하고 싶다면 하한선을 희생해야 할 수도 있다.

 

Theta(Θ)

이 수업에서 배울 마지막 그리스 문자로 대문자 Theta(Θ)가 있다. 어떤 알고리즘이 상한선과 하한선이 같을 때, Theta표기법을 사용하면 된다. 두 알고리즘(선택 정렬, 병합 정렬)을 적용할 수 있겠다.

선택 정렬은 느렸다. O(n^2) 이면서 또한 Ω(n^2)였다. 맹목적으로 가장 작은 값을 계속해서 찾기 떄문이다.

병합 정렬은 Θ(n long n)이다. 맹목적으로 같은 알고리즘을 계속 반복하낟. 입력이 이미 정렬되어 있던 상관없다. 하지만 n log n은 꽤 강력하다.

 

병합 정렬의 빠른 실행 속도 : 시각화 자료

https://www.youtube.com/watch?v=3WDWH59k1q4

마지막으로 살펴볼 것은, 이해를 도울 시각화 자료이다. 지금 볼 것은 여러 개의 수직 막대로 총 100개의 막대가 있다. 작은 막대는 작은 값을, 큰 막대는 큰 값을 나타낸다.

맨 위의 알고리즘은 선택 정렬이다. 가장 밑이 버블 정렬이고 가운데가 병합 정렬이다. 오늘은 이걸로 마무리할텐데, 같은 입력에 대한 각 알고리즘의 실행 시간을 보면서 병합 정렬이 얼마나 나은지, 즉 n log n과 n^2가 얼마나 차이가 나는지 살펴보자.

하고 싶은 말은 어떤 알고리즘을 만들 때 우리 목표는 정확하게 만드는 것 뿐만 아니라 잘 설계하자는 것이다.