[CS50] 4. 알고리즘

 

 

📚 시리즈 목차 

1. 컴퓨팅 사고

2. C언어

3. 배열

4. 알고리즘

5. 메모리

6. 자료구조

 

 

 

📚 4. 알고리즘

 

1) 검색 알고리즘

 

1️⃣  선형 검색

선형 검색은 가장 간단하고 직관적인 검색 알고리즘이다.  

검색 방법은 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지를 검사하는 것이다. 

선형 검색은 리스트를 처음부터 끝까지 순차적으로 탐색하기 때문에 최악의 경우 리스트의 길이에 비례하는 선형 시간 O(n)이 소요된다.  (바로 다음에 배움) 즉, 리스트의 크기가 클수록 검색 시간이 증가한다.  따라서 선형 검색은 특정한 상황이나 작은 크기의 리스트에서 사용될 때 유용하다. 

 

 

2️⃣ 이진 검색

이진 검색은 정렬된 배열 또는 리스트에서 특정한 값을 찾는 데 사용되는 검색 알고리즘이다. 

배열의 중간 요소와 비교하여 검색 범위를 반으로 줄여가면서 값을 찾아가는 방식이다. 

 

이진 검색은 검색 범위를 반으로 줄여가는 특성 때문에 선형 검색보다 훨씬 빠른 속도를 가진다.  이 알고리즘의 시간 복잡도는 O(log n)으로, 검색 범위가 계속 반으로 줄어들기 때문에 크기에 비례하지 않고 로그 시간에 검색이 수행된다. 따라서 이진 검색은 매우 큰 크기의 정렬된 배열에서도 효율적으로 작동한다.  

 

---

 

2) 알고리즘 표기법

우리가 프로그램을 작성한 후에 실행하면 작업이 완료될때까지 어느정도 시간이 소요된다.  아주 간단한 프로그램인 경우에는 실행 시간을 걱정할 필요가 없지만, 처리하는 데이터가 많아지고 처리하는 작업이 복잡해질수록 실행 시간은 매우 중요해진다.  특정 알고리즘을 작성하였을 때 그 실행 시간을 표기하는 법에 대해 알고있다면 실행시간을 더 쉽게 파악할 수 있다. 

 

 

1️⃣  Big O 표기법

 

Big O 표기법은 알고리즘의 효율성을 표현하는 데 사용하는 기법으로서 이 표기법은 알고리즘이 입력 크기에 따라 얼마나 빠르게 실행되는지 또는 얼마나 많은 자원(시간 또는 공간)을 사용하는지를 나타낸다. 즉 실행 시간의 상한을 나타낸다.  쉽게말해 "최악의 경우"에 대해 나타내는 것이라고 이해할 수 있다.  

 

Big O 표기법은 함수 f(n)을 사용하여 알고리즘의 실행 시간이나 자원 사용량이 입력 크기 n에 대해 어떻게 증가하는지 표현한다. 

여기서 n은 일반적으로 알고리즘의 입력의 크기 또는 규모를 나타낸다.  Big O 표기법은 큰 영향을 주며 가장 빠르게 증가하는 항목에 초점을 맞춘다.  여기서 O는 "on the order of"의 약자로 "~만큼의 정도로 커지는" 것이라고 볼 수 있다.

 

Big O 표기법은 다음과 같은 형태로 나타낼 수 있다.  (빠를수록 위쪽에 위치)

 

• O(n^2)
• O(n log n)
• O(n)
• O(log n) 
• O(1)

 

2️⃣  Big Ω 표기법

Big O가 알고리즘 실행 시간의 상한을 나타낸 것이라면, 반대로 Big Ω는 알고리즘 실행 시간의 하한을 나타낸다. 

예를 들어 선형 검색에서는 n개의 항목이 있을때 최대 n번의 검색을 해야 하므로 상한이 O(n)이 되지만 운이 좋다면 한 번만에 검색을 끝낼수도 있으므로 하한은  Ω(1)이 된다.

 

Big Ω 표기법은 아래 목록과 같이 표현할 수 있다. 

 

• Ω(n^2)
• Ω(n log n)
• Ω(n)
• Ω(log n)
• Ω(1)

---

 

3) 버블 정렬

정렬되지 않은 리스트를 탐색하는 것 보다 정렬한 뒤 탐색하는 것이 더 효율적이다.  알고리즘에도 정렬 알고리즘이 여러개 존재하는데 그중 간단하고 직관적인 정렬 알고리즘인 버를 정렬에 대해 알아보자. 

 

버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말한다.  정렬되지 않은 배열에서 가장 큰 요소가 배열의 맨 뒤로 이동하면서 요소들이 순차적을 정렬된다. 

 

아래 그림을 보면 바로 이해가 된다. 

wikimedia.org

간단하고 이해하기 쉬운 알고리즘이나 배열의 크기가 커질수록 비효울적일 수 있다.  버블 정렬의 시간 복잡도는 O(n^2)이므로 큰 규모의 배열에서는 다른 효율적인 정렬 알고리즘을 고려하는 것이 좋다. 

 

 

---

 

4) 선택 정렬

정렬 알고리즘에서 이전에 버블 정렬에 대해 알아보았다면 또 다른 정렬 알고리즘인 선택 정렬에 대해 알아보자. 

선택 정렬은 버블정렬과 반대로 배열에서 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬이다.   

 

선택 정렬은 매 반복마다 최솟값(최댓값)을 찾아 앞으로(뒤로) 이동시키는 특징을 가지고 있다. 이를 통해 반복할 때마다 정렬된 부분이 하나씩 채워지게 되며, 마지막 반복이 끝나면 배열 전체가 정렬된다. 

 

wikimedia.org

 

선택 정렬은 반복 횟수에 비례하여 비교 연산을 수행하기 때문에 시간 복잡도는 O(n^2)이다. 따라서 큰 규모의 배열에서는 다른 효율적인 정렬 알고리즘을 고려하는 것이 좋다.  

 

---

 

5) 병합 정렬

아직 공부하지 않은 대표적인 정렬 방법이 하나 더 있다. 

전화번호부의 분할 정복 탐색처럼 데이터를 반으로 나누어간다는 것과 공통점이 있는 방법인 병합 정렬(합병 정렬)이 있다. 

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

 

 

 

병합 정렬은 입력 크기에 관계없이 항상 시간 복잡도가 O(n log n)이다. (숫자들을 반으로 나누는 데는 O(log n)의 시간이 들고, 각 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸린다. 하한도 숫자들이 이미 정렬되었는지 여부에 관계없이 나누고 병합하는 과정이 필요하기에 역시  Ω(n log n) 이다)

따라서 큰 규모의 배열에서도 효율적으로 동작한다.  또한 안정적인 정렬 알고리즘이기 때문에 동일한 값에 대해서도 상대적인 순서가 유지된다. 

---

 

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

지금까지 배운 선형 검색, 이진 검색, 버블 정렬 선택 정렬의 실행시간은 각각 어떻게 되는지 알아보자. 

 

 

📌 실행시간의 상한

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

 

📌 실행시간의 하한

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

---

 

 

📌  이해하는 데 도움을 주는 사이트 및 영상

• 여러가지 정렬 방법 속도 비교 영상

 

 

• 정렬를 시작적으로 보여주는 사이트 : 링크

---

 

 

✅  퀴즈 복습

 

typedef는 새로운 데이터 타입의 별칭을 정의하는 키워드이다. 

 

선형 검색의 상한은 O(n)이고 하한은 Ω(1)이다. 

 

 

버블 정렬의 핵심은 가장 큰 요소가 배열의 맨 뒤로 이동하면서 요소들이 순차적을 정렬하는 것이다. 

 

선택 정렬의 핵심은 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식

 

 

📌 실행시간의 하한

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

이진 검색이 상한(log n)이 더 빠르기에 더 앞쪽이다.

 

O(n)과 O(n^2) 사이에 O(n log n)이 들어갈 수 있다. 

 

---

[참고]

모두를 위한 컴퓨터 과학 (CS50 2019) 알고리즘