CS50 - 알고리즘

Algorithms

1) 검색 알고리즘

배열은 한 자료형의 여러 값들이 메모리상에 모여있는 구조이다.
컴퓨터는 이 값들에 접근할 때 배열의 인덱스 하나하나를 접근한다.
만약 어떤 값이 배열 안에 속해 있는지를 찾아보기 위해서는 배열이 정렬되어 있는지 여부에 따라 선형 검색 과 이진 검색 방법을 사용할 수 있다.

선형 검색

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

의사코드

For i from 0 to n–1

    If i'th element is 50

        Return true

Return false

이진 검색

만약 배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 원하는 인덱스로 이동 반복

의사코드

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

2) 알고리즘 표기법

출처 : 부스트캠프(모두를 위한 컴퓨 과학) - Big O 표기법, 알고리즘을 실행하는데 걸리는 시간

O : on the order of

O(n) : n만큼 커지는 것이므로 n이 늘어날수록 선형적으로 증가하게 된다. O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지므로 O(n)이라고 볼 수 있다.

주로 아래 목록과 같은 Big O 표기가 실행 시간을 나타내기 위해 많이 사용됨.

• O(n^2)
• O(n log n)
• O(n) - 선형 검색
• O(log n) - 이진 검색
• O(1)

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

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

아래 목록과 같은 Big Ω 표기가 많이 사용됨.

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

3) 선형 검색

원하는 원소가 발견될 때까지 처음부터 마지막 자료를 차례대로 검색한다. 그래서 선형 검색 알고리즘은 정확하지만 아주 효율적이지 못한 방법이지만, 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에는 유용하다.

4) 버블 정렬

정렬되지 않은 리스트를 탐색하는 것 보다 정렬한 뒤 탐색하는 것이 더 효율적이다. 정렬 알고리즘 중 하나는 버블 정렬이다. 버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말한다. 단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중하여 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있다는 단점이 있다.

정렬 실행 시간의 상한은 O(n^2), 하한도 Ω(n^2) 이다.

만약 정렬이 모두 되어 있어서 교환이 하나도 일어나지 않는다면, 버블 정렬의 하한은 Ω(n) 이 된다.

5) 선택 정렬

또 다른 정렬 알고리즘 중 하나는 선택정렬이다. 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬이다. 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.

정렬 실행 시간의 상한은 O(n^2), 하한도 Ω(n^2) 이다.

6) 재귀

함수가 본인 스스로를 호출해서 사용할 수 있을 때, 재귀(Recursion)라고 부른다. 재귀의 장점은 반복문보다 코드가 간결해져 가독성이 좋고 반복문 사용을 통한 오류 발생을 막을 수 있다.

7) 병합 정렬

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

정렬 실행 시간의 상한은 O(n log n)이다. 요소들을 반으로 나누는 데에 O(log n)의 시간이 을고, 각 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문이다. 실행 시간의 하한도 역시 Ω(n log n) 이다. 숫자들이 이미 정렬되었는지 여부에 관계 없이 나누고 병한하는 과정이 필요하기 때문이다.