1. 주어진 배열 속에서 특정 값을 찾는 방법을 설명할 수 있다.
2. 알고리즘의 실행 시간의 상한과 하한을 표기할 수 있다.

boostcourse의 모두를 위한 컴퓨터 과학 (CS50 2019) 강의를 듣고 정리한 필기입니다. 😀

1. 검색 알고리즘

컴퓨터 내부에는 메모리가 있고, 이것을 임의 접근 기억장치 RAM이라고 하는데, 이것을 바이트 단위로 나누면 편하다는 것을 알고 있다.

위의 그림을 보면 바이트 0은 노랗게 칠해진 왼쪽, 제일 위 칸일 테고, 2억 바이트인 2기가 바이트는 오른쪽에서 가장 밑에 있는 칸이 될 것이다. 메모리를 이렇게 이해하면 개념적으로나 물리적으로나 왼쪽에서 오른쪽으로, 그리고 위에서 밑으로 칸을 채워가면서 자료구조를 사용할 수 있다.

지난 시간에 배운 배열을 예시로 하면, 메모리를 바이트의 격자 배열로 취급하면 우리가 원하는 대로 사용할 수 있다. 배열이라는 것을 실생활에 대입해보면 지하철 짐 보관함, 중고등학교 교실 맨 뒤에 있던 사물함, 혹은 집에 있는 수납공간과 비슷하다고 할 수 있다. 컴퓨터와 우리를 비교하기 위해 집에 있는 수납공간을 예로 들겠다. 우리는 집에 있는 서랍을 하나하나 열어보지 않아도 내용물을 파악할 수 있다. (어떤 물건이, 몇 개가 들었는지에 대해서 몰라도, 대충 라면 냄비는 어느 서랍에 있고, 반창고는 어느 서랍에 있는지 정도는 알 수 있을 것이다.) 하지만, 컴퓨터는 배열 속 내용물을 하나하나 봐야만 알 수 있다. 인간처럼 전체를 파악하는 감지 능력이 전혀 없다는 말이다.

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

1.1 선형 검색

배열의 인덱스를 처음부터 끝까지 하나하나 접근하여 우리가 찾는 값이 있는지를 확인하는 것을 선형검색이라고 한다. 매우 정확하다는 장점이 있지만, 만약 우리가 찾고자 하는 값이 마지막에 있다면 배열의 길이에 따라 오랜 시간이 걸릴 수 있다. 이것은 정렬이 되어있지 않고 규칙이 없을 때 최선의 방법은 선형검색일 것이다.

아래는 선형검색에 대한 의사 코드이다.

For i from 0 to n–1

    If i'th element is 50

        Return true

Return false

1.2 이진 검색

만약 배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 그보다 작은(작은 값이 저장된) 인덱스 또는 큰 (큰 값이 저장된) 인덱스로 이동을 반복하면 된다.

예를 들어, 우리가 50이라는 숫자를 찾는다고 하자. 배열에는 위와 같이 숫자가 입력되어있다. 우리에게는 정렬이 되어있다는 정보만 주어진 상태라고 하면, 가운데 인덱스를 먼저 확인하는 것이 유리할 것이다. 가운데 있는 숫자가 50보다 크면 왼쪽을, 작으면 오른쪽을 확인하면 된다.

아래 의사코드와 같이 나타낼 수 있다.

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. 알고리즘 표기법

아래 그림은 알고리즘을 실행하는 뎅 걸리는 시간을 그림으로 표현한 것이다. 다른 색, 다른 모양으로 뻗어있는 모양은 각 알고리즘의 최악의 경우를 나타낸다. 오늘은 알고리즘 표기법에 대한 용어를 배우고 정리할 것이고, 이것을 토대로 선형 검색과 이진 검색 뿐만아니라 다양한 알고리즘에 대해서 배우게 될 것이다.

2.1 Big O

아래 그림을 공식으로 표기한 것이 Big O 표기법이다. Big O 표기법은 컴퓨터 과학자들이 알고리즘을 설명하기 위해 사용하는 용어 중 하나이며, 가장 일반적으로 사용하는 용어이기도 하다. 이는 알고리즘이 얼마나 잘 설계되어있는지, 또 코드가 얼마나 잘 구현되어있는지 말해주는 용도로 사용된다.

이름의 O는 “on the order of”의 약자로, 쉽게 생각하면 어느 정도 크기인지를 말해준다. O(n) 은 n만큼 커지는 것이므로 n이 늘어날수록 선형적으로 증가하게 된다. O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지므로 O(n)이라고 볼 수 있다. 즉, Big O 표기법은 정확한 값은 아니지만 대략적인 추정값을 표현한 것이다.

누군가 우리의 알고리즘이 얼마나 효율적인지 물어본다면, 즉, 코드의 효율성(실행시간)을 물을 때 사용하면 된다. 실행시간이란, 프로그램이나 알고리즘이 동작하는데 걸리는 시간을 말한다. 몇 초가 걸리는지 혹은 몇 번의 계산 과정이 필요한지에 대해서 말이다.

세상에는 다양한 알고리즘이 있는데, 아래 5개는 대표적인 것들만 가지고 온 것이다.

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

2.2 Big Ω

위에서도 말했듯이 Big O 알고리즘을 나타내는 용어중 하나이다. 즉, 컴퓨터 과학자에게는 다른 도구들이 있는데, 그리스 대문자인 Ω(Omega)가 그에 해당한다. Big Ω의 의미는 Big O의 반대라고 할 수 있다. Big O는 알고리즘 실행 시간의 상한을 나타낸 것이라면, 반대로 Big Ω는 알고리즘 실행 시간의 하한을 나타내는 것입니다.

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

이진 검색에서는 어떨까? 똑같이 운이 좋다면 한 번만에 검색을 끝낼수도 있으므로 하한은 Ω(1)이 된다. 이또한, 50이 가운데에 있을 수도 있기 때문이다.

또 가끔, 입력값이 특정 순서로 들어온다면, 실행시간은 예상보다 짧아질 수 있다.

역시 아래 목록과 같은 Big Ω 표기가 많이 사용됩니다.

• Ω(n²)

• Ω(n log n)

• Ω(n)

• Ω(log n)

• Ω(1) - 선형 검색, 이진 검색

2.3 질문

Q1. 앞으로 여러가지 알고리즘을 살펴볼텐데, Ω(n)을 갖는 알고리즘이 있을까?

▶ 있다. 예를들어 배열안에 존재하는 값의 개수를 센다면 n번의 과정이 필요할 것이다. 예를 들어 서랍의 갯수를 세야한다고 치자. 7개의 서랍이 있으면 7번의 과정이 필요할 것이고, 8개가 있다면 8번의 과정이 필요할 것이다.

Q2. Big O와 Big Ω중 어느 것이 좋아야 좋은 알고리즘일까?

▶ 후자이다. 차차 알게되겠지만, 컴퓨터과학자가 걱정하는 것은 최악의 경우에 프로그램이 어떻게 동작할지, 혹은 평균적으로 어떻게 동작할지이다.