* boostcourse 카테고리 내의 CS50관련 글은 네이버 부스트코스 [CS50 - 모두를 위한 컴퓨터 과학]을 수강 후 개인적으로 개념을 정리해본 글. 자세한 강의 내용을 확인하고 싶다면 네이버 커넥트재단이 운영하는 boostcourse 사이트에서 상시 무료 수강으로 진행되고 있는 CS50 강의 수강을 추천합니다.
모두를 위한 컴퓨터 과학 (CS50 2019)
부스트코스 무료 강의
www.boostcourse.org
“네이버 커넥트재단은 교육을 통해 개인의 지속적인 성장과 발전을 돕고, 원하는 곳 어디든 배움의 기회가 열리는 세상을 만들기 위해 노력합니다. 부스트코스는 커리어 역량을 강화할 수 있도록, 네이버 커넥트재단에서 기획하고 운영하는 실무형 온라인 교육 프로그램입니다.”
>> 부스트코스 홍보까지는 아니고 ㅎ 무료 강의 추천이다ㅎ
2021/01/10 - [boostcourse] - [부스트코스] CS50 코칭스터디 2기 오리엔테이션
2021/01/16 - [boostcourse] - [부스트코스] CS50 1강: 컴퓨팅 사고 강의 정리
2021/01/22 - [boostcourse] - [부스트코스] CS50 2강: C언어 강의 정리 (부제: 코딩 찌질이)
2021/01/29 - [boostcourse] - [부스트코스] CS50 3강: 배열 강의 정리 (부제: 코칭스터디 3주차)
CS50 4강 알고리즘(Algorithms)
- 검색 알고리즘
- 알고리즘 표기법
- 선형 검색
- 버블 정렬
- 선택 정렬
- 정렬 알고리즘의 실행시간
- 재귀
- 병합 정렬
2021/02/12 - [boostcourse] - [부스트코스] CS50: 초보자는 헷갈리는 C언어 용어 정리
2021/02/14 - [boostcourse] - [부스트코스] CS50 5강: 메모리 강의 정리 (부제: 설연휴 만세)
2021/02/23 - [boostcourse] - [부스트코스] CS50 6강: 자료구조 강의 정리 (부제: CS50 수강 완료!)
2021/03/03 - [boostcourse] - [부스트코스] CS50 코칭스터디 2기 수료 후기
1. 검색 알고리즘(algorithm)
배열은 한 자료형의 여러 값들이 메모리상에 모여 있는 구조로, 컴퓨터는 이 값들에 접근할 때 배열의 인덱스 하나 하나 따로 접근해야만 한다. 즉, 아래 표와 같은 배열이 있다고 했을 때 컴퓨터는 우리가 표를 보듯이 전체적으로 볼 수 없고 한 번에 한 칸만 볼 수 있는 것이다.
| 9 | 3 | 8 | 1 | 50 |
| array[0] | array[1] | array[2] | array[3] | array[4] |
따라서 컴퓨터와 같은 방법으로 검색 알고리즘을 생각해보기 위해 위의 표가 가려져 있는 상태에서 '50'의 위치를 찾아야 한다고 가정하면, 배열 내 요소의 정렬 여부에 따라 두 가지 방법을 생각해 볼 수 있다.
1.1 선형 검색(linear search)
배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 원하는 값이 있는지 확인하는 것을 말한다. 즉, 위의 표가 서랍이라고 생각하면, 첫 번째 칸부터 순서대로 열어보면서 내가 찾는 '50'이 있는지 없는지 확인하는 것이다. 의사코드로 나타내면 아래와 같다.
For i from 0 to n–1
If i'th element is 50
Return true
Return false
1.2 이진 검색(binary search)
1강 컴퓨팅 사고> 3. 알고리즘에 예시로 나왔던 '전화번호부에서 Mike smith를 찾는 방법'과 같은 방법이다.
배열이 정렬되어 있는 경우에, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하면서 그보다 작은(작은 값이 저장되어 있는) 인덱스 또는 큰 (큰 값이 저장되어 있는) 인덱스로 이동을 반복하는 검색 방법이다.
If no items
Return false
If middle item is 50
Return true
Else if 50 < middle item
Search left half
Else if 50 > middle item
Search right half
👉예시로 작성한 위의 배열 표에서는 배열이 정렬되어 있지 않기 때문에 비효율적이더라도 선형 검색을 이용하여 '50'을 찾는 수밖에 없다. 만약 배열의 크기가 훨씬 더 크다면 그만큼 더 비효율적인 코드가 될 것이다. 따라서 배열이 정렬되어 있다면 정렬되지 않은 배열보다 더 쉽게(효율적으로) 탐색할 수 있다.
2. 알고리즘 표기법
2.1 Big-O 표기법 (대문자 O 표기법)
문제의 크기가 커질 수록 문제를 해결하는 데 걸리는 시간 또한 비례해서 증가하는 n은 선형 검색을 의미하고, 문제의 크기에 큰 영향을 받지 않고 보다 완만한 곡선의 크기를 그리는 log(2)n은 이진 검색에 해당한다. n/2는 하나하나 확인하지 않고 확인 개수를 늘려 두 개씩 확인하는 경우를 표현한 것인데, n의 크기가 커질 수록 n과 n/2는 거의 비슷해지기 때문에 사실상 큰 의미가 없다.
이렇게 알고리즘의 실행 시간을 보여주는 표는 결국 알고리즘이 최악의 경우에 필요한 계산 수를 직관적으로 나타내기 위함이다. 컴퓨터 과학자들은 이러한 표에서 나아가 알고리즘이 얼마나 잘 설계되어 있고, 코드가 얼마나 잘 구현되어 있는지 나타내기 위해 표기법을 사용하는데, 위의 표와 비슷한 의미(최악의 경우에 필요한 계산 수)를 담고 있으면서도 가장 일반적인 표기법은 Big-O 표기법이다. 즉, Big-O 표기법은 알고리즘 실행 시간의 상한선을 나타내는 표기법이다. 한국어로는 '대문자 O 표기법'이라고 한다.
Big-O의 O는 'on the order of~'를 의미하는데, '~만큼의 정도로 커지는'이라고 해석할 수 있다. Big-O 표기법에 따라 선형 검색을 표기하면 O(n)으로, 이진 검색은 O(log n)으로 표기할 수 있다. n의 값이 커질수록 상세한 식은 의미가 없어지므로 생략하고 가장 중요한 부분만 나타낸다. 아직 배우진 않았지만, 자주 사용하는 다른 알고리즘 표기법까지 포함하여 실행시간을 내림차순으로 정리해보자면 아래와 같다.
- O(n^2)
- O(n log n)
- O(n) → 선형 검색
- O(log n) → 이진 검색
- O(1)
2.2 Big Ω 표기법 (대문자 오메가 표기법)
Big-O 표기법과는 반대로 Big-Ω는 최선의 경우, 곧 알고리즘 실행 시간의 하한선을 나타내는 표기법이다.예를 들어 선형 검색에서는 n개의 항목이 있을때 최대(Big-O) n번의 검색을 해야 하므로 상한이 O(n)이 되지만, 운이 좋다면 한 번만에 검색을 끝낼수도 있으므로 하한은 Ω(1)이된다. 선형 검색뿐만 아니라 이진 검색 또한 마찬가지로 운이 좋으면 처음에 발견할 수 있으므로 Ω(1)이 된다.
마찬가지로 자주 사용하는 표기법을 정리해보면 아래와 같다.
- Ω(n^2)
- Ω(n log n)
- Ω(n) → 배열 내 인덱스 개수 세기
- Ω(log n)
- Ω(1) → 선형 검색, 이진 검색
Ω(n)은 최선의 경우에도 n번이 과정이 필요한 경우인데, 배열 안에 존재하는 인덱스의 개수를 세는 경우가 그 예시가 될 수 있다. 배열에 몇 개의 인덱스가 있는지는 결국 하나하나 숫자를 세어나가는 방법 밖에는 없기 때문이다. 이 경우 최악(Big-O)도 최선(Big-Ω)도 O(n), Ω(n)이 된다.
✔️Big-O와 Big-Ω, 두가지 값 중에서 더 중요하게 다뤄야하는 부분은 Big-O이다. 컴퓨터 과학자가 걱정해야하는 부분은 최악의 경우에 프로그램이 어떻게 동작할지, 또는 평균적으로 어떻게 동작하는지에 관한 것이기 때문이다.
3. 선형 검색 (feat. 배열)
3.1 배열관련 팁TIP
3.1.1 중괄호로 배열 선언하기
배열을 선언할 때에는 3강 배열> 4. 배열> 4.2 배열에서 배웠듯 각각의 인덱스 값을 모두 따로 입력해줄 수도 있지만, 중괄호를 이용하여 보다 간단하게 나타낼 수도 있다. 의미는 같으면서도 코드의 양은 줄어들었다.
3.1.2 문자열의 비교(관계연산자)와 함수 반환(return 0;)
문자열의 비교에 앞서, 정수 배열의 선형 검색에 대한 예시로, 포스트 내 1.1 선형 검색에 작성되어 있던 의사 코드를 C언어로 작성한 것이다. 표에 써져있던 숫자들과는 다르지만 결국 정수 배열 내에 '50'이 있는지 검사를 하는 코드다. 루프를 통해 인덱스 값을 증가시키면서 '50'과 일치할 경우 찾았다는 결과를, 그렇지 않을 경우에는 찾지 못했다는 결과를 출력할 수 있도록 구성되어있다. 컴파일 결과 문제없이 제대로 실행되는 것을 볼 수 있다.
다음으로 문자열도 위와 같은 코드를 적용시켜 컴파일을 시도해보면, 문법적 오류로 인해 아예 컴파일 자체가 되지 않는다. 문자(char), 불리언(bool), 정수(int), 소수(float)등 과는 달리 '문자열(string)'은 여러 개의 문자로 구성된 배열이므로 문자열 속 문자를 하나하나 비교해야하기 때문이다. 즉, 문자열에서는 관계연산자를 사용할 수 없다. 위의 코드의 경우 문자열 전체를 한 번에 비교하려고 했기 때문에 오류가 난 것이다. 참고로 C보다 더 고수준인 파이썬이나 자바같은 다른 프로그래밍 언어에서는 한 줄로 비교가 가능하다고 한다.
그러므로 문자열을 비교하기 위해서는 <string.h>에 포함되어있는 strcmp라는 함수를 사용하는 것이 적합하다. strcmp는 비교하는 두 문자열이 같다면 0을 반환한다(양수를 반환하면 첫 번째 문자열이 알파벳 기준으로 큰 경우, 음수를 반환하면 반대의 경우).
strcmp(배열, "문자열")==0으로 입력한 결과 문제없이 컴파일 및 실행되었다. 그런데 두 가지 결과가 모두 출력되었다. 사실 애초에 코드 구성 자체가 "여기엔 없음"이 무조건 출력될 수 밖에 없도록 구성되어 있기 때문에 그렇다. 따라서 결과의 여부에 따라 반환하는 값을 달리할 수 있도록 코드를 추가해 주어야 한다.
결과가 성공적이었을 경우 return 0;을, 그렇지 않을 경우에는 어떠한 숫자가 되든 상관없지만 일반적인 방식에 따라 return 1;을 입력한다. 보통 0은 성공, 1은 실패를 의미한다.
3.1.3 구조체를 이용하여 배열에 여러가지 정보를 함께 저장하기
배열 내에 이름과 전화번호를 저장하고 출력해야 하는 코드를 작성해야 할 때, 3.1.2 문자열의 비교에서 사용한 코드와 비슷한 맥락에서 작성한다고 하면 아래와 같이 써볼 수 있다.
(전화번호는 기호들을 포함하고 있고, 0으로 시작할 수도 있기 때문에(수에 관한 형식지정자는 맨 앞의 숫자가 0일 경우 출력하지 않는다) string으로 형식을 지정해야 한다.)
그러나 이 코드는 이름과 전화번호의 배열 순서가 반드시 같아야만 한다. 자료의 수가 적으면 문제가 일어날 확률이 적지만 이름과 전화번호의 수가 늘어날 수록 오류가 일어날 수 있는 확률이 높아진다. 따라서 같은 위치의 인덱스에 이름과 번호를 같이 저장하는 방법을 생각하는 것이 좋다.
직접 번호를 미리 적어주는 코드이다 보니 더 복잡해졌지만, 이름과 번호가 서로 다른 경우가 발생할 수 있는 위험은 줄어들었다.
4. 버블 정렬(bubble sort)
배열 내의 자료가 정렬되어있지 않았을 때, 정렬하기 위한 방법 중의 하나로 '버블 정렬'이 있다. 버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법이다. 이 방법은 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생한다는 단점이 있다.
예를 들어, 아래와 같은 8개의 숫자가 임의의 순서로 나열되어 있다고 했을 때 이 숫자들을 오름차순으로 정렬하기 위해,
6 3 8 5 2 7 4 1
먼저 가장 앞의 6과 3을 비교해서 순서를 바꿀 수 있다.
교환 전: 6 3 8 5 2 7 4 1
교환 후: 3 6 8 5 2 7 4 1
다음 쌍인 6과 8을 비교해보면 교환할 필요가 없으므로 바로 다음에 있는 쌍인 8과 5를 비교해서 순서를 바꾼다.
교환 전: 3 6 8 5 2 7 4 1
교환 후: 3 6 5 8 2 7 4 1
이런 식으로 숫자 끝까지 진행하면 아래와 같이 정렬된다.
3 6 5 2 7 4 1 8
하지만 아직 오름차순으로 정렬이 되지 않았기 때문에, 다시 처음부터 동일한 작업을 반복한다.
3 6 5 2 7 4 1 8
3 6 5 2 7 4 1 8 (교환)
3 5 6 2 7 4 1 8 (교환)
3 5 2 6 7 4 1 8
3 5 2 6 7 4 1 8 (교환)
3 5 2 6 4 7 1 8 (교환)
3 5 2 6 4 1 7 8
이 과정을 끝까지 반복하면 최종적으로 아래와 같이 오름차순 정렬이 된다.
1 2 4 3 5 6 7 8
비교와 교환을 하는 모습이 마치 거품이 터지면서 위로 올라오는 (정확히는 배열의 옆으로 이동하는) 방식이기 때문에 버블 정렬이라고 한다. 강의 영상에서는 학생들이 직접 숫자를 들고 일렬로 선 다음, 옆의 사람이 가진 숫자를 들고 비교하며 자리를 옮기는 모습을 연출하기도 했다.
이 과정을 의사코드로 작성해보면 아래와 같다.
Repeat n–1 times
For i from 0 to n–2
If i'th and i+1'th elements out of order
Swap themn명이 있고, 서로를 비교한다면 최대 n-1번까지 비교할 수 있다. 그리고 이를 계속 반복해서 정렬이 될 때까지 실행했다. 따라서 이를 식으로 나타내면 (n-1)*(n-1)이 된다(0에서 n-2까지이므로 n-1과 같다.) 식을 정리하면, n^-2n+1이 되는데, Big-O 표기법으로는 O(n^2)이 된다. Big-O 표기법에 나왔던 예시를 다시 살펴보면 버블 정렬이 가장 상위에 위치하고 있음을 알 수 있다.
- O(n^2) → 버블 정렬 🆕
- O(n log n)
- O(n) → 선형 검색
- O(log n) → 이진 검색
- O(1)
버블 정렬의 경우에는 정렬이 되어있는지의 여부에 관계없이 무조건 루프를 돌며 비교하기 때문에 Big-Ω표기법 또한 Ω(n^2)이 된다.
덧붙여 이 순서상에서 이진 검색이 선형 검색보다 더 빠를 수 있는 이유는 이미 정렬되어 있는 데이터를 이용할 경우에 해당하기 때문에, 이진 검색이 선형 검색보다 낫다는 표현을 할 수는 없다.
5. 선택 정렬(selection sort)
선택 정렬은, 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬이다. 버블 정렬과 마찬가지로 정렬되지 않은 숫자로 선택 정렬을 실행해보면 아래와 같다.
6 3 8 5 2 7 4 1
먼저 아래 숫자들 중에서 가장 작은 값을 찾는다.
6 3 8 5 2 7 4 1
가장 작은 값인 1은 가장 앞에 있어야 하므로 현재 리스트의 첫 번째 값인 6과 교환한다. (강의에서 쓰인 표현을 빌리자면 '내쫓는다' ㅋㅋ)
1 3 8 5 2 7 4 6
그리고 정렬되어 있는 1은 제외하고, 두 번째 숫자부터 시작해서 또 가장 작은 값을 찾는다.
1 3 8 5 2 7 4 6
가장 작은 값인 2는 정렬되지 않는 숫자들 중에서 가장 앞에 있어야 하므로 3과 교환한다.
1 2 8 5 3 7 4 6
이 과정을 더 이상 교환이 일어나지 않을때까지 반복하면, 아래와 같이 오름차순 정렬이 된다.
1 2 3 4 5 6 7 8
선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.의사 코드로 아래와 같이 표현할 수 있다.
For i from 0 to n–1
Find smallest item between i'th item and last item
Swap smallest item with i'th item선택 정렬 또한 두 번의 루프를 돌아야 한다. 바깥 루프에서는 숫자들을 처음부터 순서대로 방문하고, 안쪽 루프에서는 가장 작은 값을 찾는다. 식으로 나타내면 아래와 같다.
n + (n-1) + (n-2) + … +1
n(n+1)/2
n^2/2 + n/2
따라서 줄여서 나타내면 소요 시간의 상한은 O(n^2)이 되며, 하한도 마찬가지로 Ω(n^2)이 되어 버블정렬과 동일한 표기법을 갖는다. 컴퓨터는 우리가 한 눈에 자료를 파악하는 것처럼 볼 수 없고, 일일히 자료를 확인해야만 알 수 있기 때문에 정렬이 이미 되어있더라도 그와 상관없이 알고리즘을 수행하기 때문이다.
- O(n^2) → 버블 정렬, 선택 정렬 🆕
- O(n log n)
- O(n) → 선형 검색
- O(log n) → 이진 검색
- O(1)
6. 정렬 알고리즘의 실행시간
6.1 정렬 알고리즘 실행시간 상한과 하한 비교 표
강의에서 다룬 알고리즘들의 실행시간을 정리해보면 아래와 같다.
| 실행 시간의 상한 |
실행 시간의 하한 |
||
| O(n^2) | 버블 정렬, 선택 정렬 | Ω(n^2) | 버블 정렬, 선택 정렬 |
| O(n log n) | Ω(n log n) | ||
| O(n) | 선형 검색 | Ω(n) | |
| O(log n) | 이진 검색 | Ω(log n) | |
| O(1) | Ω(1) | 선형 검색, 이진 검색 | |
그런데 버블 정렬의 경우, 이미 정렬되어 있는 경우에는 교환이 일어나지 않기때문에, 교환이 일어나지 않는다면 알고리즘을 빨리 종료하는 방식으로 코드를 수정해서 실행시간의 하한을 더 낮출 수 있다. 의사코드로 과정을 비교해보면 아래와 같다.
Repeat n–1 times
For i from 0 to n–2
If i'th and i+1'th elements out of order
Swap themRepeat until no swaps
For i from 0 to n–2
If i'th and i+1'th elements out of order
Swap them즉, 안쪽 루프에서 교환이 일어나지 않는다면 이미 정렬이 된 상태임을 알 수 있으므로 바깥쪽 루프를 '교환이 일어나지 않을 때(until no swaps)'까지로 바꿔줄 수 있다. 다시금 실행시간을 정리해보면 아래와 같다.
| 실행 시간의 상한 |
실행 시간의 하한 |
||
| O(n^2) | 버블 정렬, 선택 정렬 | Ω(n^2) | 선택 정렬 |
| O(n log n) | Ω(n log n) | ||
| O(n) | 선형 검색 | Ω(n) | 버블 정렬🆕 |
| O(log n) | 이진 검색 | Ω(log n) | |
| O(1) | Ω(1) | 선형 검색, 이진 검색 | |
상황에 따라서 버블 정렬이 선택 정렬보다 빨라질 수 있음을 알 수 있다. 선택 정렬의 경우에는 버블 정렬과는 달리 모든 값을 비교해야 하므로 버블 정렬과 같은 단축은 불가능하다.
6.2 실제 실행시간의 차이 (버블정렬과 선택정렬)
그러나 유튜브를 보니(코칭스터디 조원 덕에 보게됐다) 버블 정렬과 선택 정렬의 시간이 이론상으로는 같다고 해도 실제 작동시간은 버블 정렬이 보다 느리다고 한다. 영상을 통해 확인할 수 있듯이 버블 정렬의 계산 자체가 선택 정렬보다 복잡하기 때문에 컴퓨터로 작동해보면 차이가 생기게 되는 것이다.
7. 재귀(Recursion)
7.1 중첩루프
'재귀'는 함수가 본인 스스로를 호출해서 사용하는 것을 일컫는다. 재귀에 대한 이해에 앞서 우선 2강 C언어> 5. 사용자 정의 함수,중첩 루프> 5.2 중첩루프에 나왔던 블록쌓기 코드를 변형한 피라미드 쌓기 코드를 예시를 통해 중첩 루프에 대해 다시 이해할 필요가 있다.
위의 코드에서는 사용자에게 높이를 입력으로 받은 다음, 중첩을 통해 피라미드를 출력하는 함수를 사용했다. 그러나 중첩루프에서 바깥쪽 코드의 경우엔, 안쪽 루프에서 수행하는 것을 반복하는 것에 그친다. 그러므로 바깥쪽 루프를 없앤 뒤, '재귀'를 통해 호출해서 같은 기능을 수행하는 코드를 만들어 볼 수 있다.
7.2 중첩 루프를 재귀로 바꾸기
아래쪽의 draw 함수에 대한 정의를 살펴보면, 중첩루프로 구성했을 때와 달리 바깥쪽 루프가 사라지고 draw 함수 안에서 draw함수를 출력하면서 0에 대한 반환값을 추가한 것을 볼 수 있다. 디버깅 기능을 활용해서 함수의 작동 방식을 살펴보면 반복문이 먼저 실행되는 것이 아니라, 재귀 함수 부분이 가장 먼저 실행된다.
재귀의 경우엔 스택이라는 개념에 대한 이해도 필요한데, 이후 강의에서 보다 자세하게 다룬다고 함.
8. 병합 정렬(merge sort)
8.1 병합 정렬(합병 정렬)
병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누는 작업을 한 뒤에 다시금 합쳐나가며 정렬을 하는 방식이다.
다음 숫자들을 오름차순으로 정렬한다고 했을때,
7 4 5 2 6 3 8 1
먼저 숫자들을 반으로 나눈다.
7 4 5 2 | 6 3 8 1
그리고 나눠진 부분 중 첫번째를 한번 더 반으로 나눈다.
7 4 | 5 2 | 6 3 8 1
마지막으로 한 번 더 나눈다.
7 | 4 | 5 2 | 6 3 8 1
맨 앞의 부분을 또 나눌 경우, 이제 숫자가 두 개 밖에 남지 않았으므로 더 이상 나누지 않고, 두 숫자를 다시 병합한다. 단, 이 때 작은 숫자가 먼저 오도록 한다. 4와 7의 순서를 바꿔서 병합하는 것이다.
4 7 | 5 2 | 6 3 8 1
마찬가지로 5 2 부분도 반으로 나눈 후에 작은 숫자가 먼저 오도록 다시 병합한다.
4 7 | 2 5 | 6 3 8 1
이제 4 7과 2 5 두 개의 부분들을 병합한다. 각 부분들의 숫자들을 앞에서 부터 순서대로 읽어들여 비교하여 더 작은 숫자를 병합되는 부분에 가져온다. 즉, 4와 2를 먼저 비교해서 2를 가져오고 그 뒤에 4와 5를 비교해서 4를 가져온다. 그리고 7과 5를 비교해서 5를 가져오고, 남은 7을 가져온다.
2 4 5 7 | 6 3 8 1
이제 남은 오른쪽 4개의 숫자들도 위와 동일한 과정을 반복한다.
2 4 5 7 | 1 3 6 8
마지막으로 각각 정렬된 왼쪽 4개와 오른쪽 4개의 두 부분을 병합한다. 2와 1을 비교하고, 1을 가져온 다음, 2와 3을 비교하고, 2를 가져온다. 4와 3을 비교하고, 3을 가져온다. 4와 6을 비교하고… 이 과정을 병합이 끝날때까지 진행하면 아래와 같이 정렬이 완료된다.
1 2 3 4 5 6 7 8
전체 과정을 요약해서 도식화해보면 아래와 같다.
7 | 4 | 5 | 2 | 6 | 3 | 8 | 1 → 가장 작은 부분 (숫자 1개)으로 나눠진 결과
4 7 | 2 5 | 3 6 | 1 8 → 숫자 1개씩을 정렬하여 병합한 결과
2 4 5 7 | 1 3 6 8 → 숫자 2개씩을 정렬하여 병합한 결과
1 2 3 4 5 6 7 8 → 마지막으로 숫자 4개씩을 정렬하여 병합한 결과
1강에서부터 수강하면서 알 수 있는 점은, 무언가를 반으로 나누는 과정을 반복할 때에 이를 설명할 수 있는 수식으로 log가 사용된다는 점이다. 따라서 병합 정렬의 경우에는 숫자로 반으로 나누고(log n) 나눈 부분들을 다시 정리해서 병합(n)하므로 실행시간의 상한은 O(n log n)이 된다. 병합 정렬 또한 정렬이 되어있는지의 여부와 상관없이 나누고 병합하는 과정을 진행하므로 실행시간의 하한 또한 Ω(n log n)이 된다.
| 실행 시간의 상한 |
실행 시간의 하한 |
||
| O(n^2) | 버블 정렬, 선택 정렬 | Ω(n^2) | 선택 정렬 |
| O(n log n) | 병합 정렬🆕 | Ω(n log n) | 병합 정렬🆕 |
| O(n) | 선형 검색 | Ω(n) | 버블 정렬 |
| O(log n) | 이진 검색 | Ω(log n) | |
| O(1) | Ω(1) | 선형 검색, 이진 검색 | |
8.2 Big-Θ 표기법 (대문자 세타 표기법)
알고리즘의 상한선과 하한선이 같을 때 사용하는 표기법이다. 즉, Big-O와 Big-Ω가 같은 값으로 표기될 경우 Θ(Theta)로 표기하면 된다.
| 실행 시간의 상한=하한 |
|
| Θ(n^2) | 선택 정렬 |
| Θ(n log n) | 병합 정렬 |
| Θ(n) | 배열 내 인덱스 개수 세기 |
| Θ(log n) | |
| Θ(1) | |
8.3 정렬 알고리즘의 실행 시간 차이
정렬 알고리즘들의 실행 시간 차이를 시각적으로 보고 싶다면 아래 유튜브를 통해 확인 가능하다.
배우지 않은 정렬에 대한 예시들도 볼 수 있는데, 어쨌건 제일 느린건 버블 정렬이다 ㅋㅋㅋ
코칭 스터디 3주차때 미션 난이도 문제로 대거 수강취소가 발생해서
4주차 미션들은 난이도 조정을 했다고 하는데,
코딩 알못은 여전히 쉬운 미션도 어렵다.
남은 2주 어떻게 버티지?
'STUDY > boostcourse' 카테고리의 다른 글
| [부스트코스] CS50 5강: 메모리 강의 정리 (부제: 설연휴 만세) (0) | 2021.02.14 |
|---|---|
| [부스트코스] CS50: 초보자는 헷갈리는 C언어 용어 정리 (0) | 2021.02.12 |
| [부스트코스] CS50 3강: 배열 강의 정리 (부제: 코칭스터디 3주차) (0) | 2021.01.29 |
| [부스트코스] CS50 2강: C언어 강의 정리 (부제: 코딩 찌질이) (0) | 2021.01.22 |
| [부스트코스] CS50 1강: 컴퓨팅 사고 강의 정리 (0) | 2021.01.16 |