[cs50 모두를 위한 컴퓨터 과학] 알고리즘(Algorithm)

네이버 boostcourse의 모두를 위한 컴퓨터 과학 (CS50 2019) 4. 알고리즘을 들으며 정리한 내용입니다.
더 자세한 강의의 예시는 https://www.boostcourse.org/cs112/lecture/119019?isDesc=false 참조하세요.

 

 

1. 검색 알고리즘

• 선형 검색 - 처음부터 끝까지 하나씩 증가시키며 그 값이 맞는지 검사 ex) 전화번호부 위에서 아래로 맞는 이름이 나올 때까지 검색

• 이진 검색 - 만약 배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 그보다 작은 값이 저장되어 있는 인덱스 또는 큰 값이 저장되어 있는 인덱스로 이동을 반복. ex) 전화번호부가 정렬되어 있다면, 중간부터 시작해 a-z 알파벳순의 가까운쪽(왼쪽 or 오른쪽)의 또 중간으로 이동해 반복 검색

 

2. 알고리즘 표기법

 

알고리즘을 실행하는데 걸리는 시간

위와 같은 그림을 공식으로 표기한 것이 Big O 표기법.

(O는 “on the order of”의 약자로, 쉽게 생각하면 “~만큼의 정도로 커지는” 것)

Big O 표기법 - 알고리즘 실행 시간의 상한을 나타냄.

• O(n^2)
• O(n log n)
• O(n) - 선형 검색, n이 늘어날수록 선형적으로 증가, O(n/2)도 n이 매우 커지면 1/2은 큰 의미가 없어지므로 O(n)이라고 볼 수 있음.
• O(log n) - 이진 검색
• O(1)

Big Ω(오메가) - 알고리즘 실행 시간의 하한을 나타냄.

• Ω(n^2)
• Ω(n log n)
• Ω(n) - 배열 안에 존재하는 값의 개수 세기
• Ω(log n)
• Ω(1) - 선형 검색, 이진 검색

ex) 선형 검색에서 n개의 항목이 있을 때 최대 n번의 검색을 해야 하므로 상한은 O(n), 첫번째 검색에서 찾는다면 하한은 Ω(1)

 

3. 버블 정렬

• 거품이(비교 및 교환이) 터지면서 위로 올라오는 (배열의 옆으로 이동하는) 방식 ex)욕조에서 거품이 가장자리까지 이동하는 모습처럼 처음부터 끝까지 이동함.
• 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬.
• 단 두개의 요소만 정렬해주는 좁은 범위의 정렬에 집중.
• 버블 정렬의 의사코드

Repeat n–1 times

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

중첩 루프를 돌아야 하고, n개의 값이 주어졌을 때 각 루프는 각각 n-1번, n-2번 반복되므로

(n-1)*(n-2) = n²-3n+2 번의 비교 및 교환이 필요.

여기서 가장 크기가 큰 요소는 n² 이므로 위와 같은 코드로 작성한 버블 정렬 실행 시간의 상한은 O(n²).

정렬이 되어 있는지 여부에 관계 없이 루프를 돌며 비교를 해야 하므로 버블 정렬의 실행 시간의 하한도 Ω(n²).

 

4. 선택 정렬

• 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬.
• 선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가.
• 선택 정렬의 의사 코드

For i from 0 to n–1

    Find smallest item between i'th item and last item

    Swap smallest item with i'th item

여기서도 두 번의 루프를 돈다.

바깥 루프에서는 숫자들을 처음부터 순서대로 방문하고, 안쪽 루프에서는 가장 작은 값을 찾음.

따라서 소요 시간의 상한은 O(n²), 하한도 Ω(n²). 버블 정렬과 동일.

 

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

 

실행시간의 상한

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

 

실행시간의 하한

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

빅 오 표기법의 속도 차이는 O(1) < O(logN) < O(N) < O(NLogN) < O(N^2) < O(N^3) < O(2^N) < O(N!)의 순서

출처: https://inor.tistory.com/30 [Inor:티스토리]

 

6. 병합 정렬

• 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식.
• 재귀적으로 구현_ 재귀(Recursion)함수는 함수가 본인 스스로를 호출해서 사용할 수 있는(자신을 재참조하는) 함수를 뜻함.

병합 정렬 실행 시간의 상한 : O(n log n)

- 숫자들을 반으로 나누는 데 O(log n)의 시간이 들고, 각 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문.

실행 시간의 하한도 역시 Ω(n log n).

- 숫자들이 이미 정렬되었는지 여부에 관계 없이 나누고 병합하는 과정이 필요하기 때문.