Ch.02 알고리즘이 중요한 까닭 (도서 요약 "누구나 자료구조와 알고리즘")
어떤 자료 구조를 결정했더라도 어떤 '알고리즘'을 선택했냐에 따라 코드의 효율성은 달라진다.
알고리즘이란, "어떤 과제를 완수하는 명령어 집합"일뿐이다.
예를 들어 '라면을 끓이는 과정'도 다음 다섯 단계를 거친다.
1) 물을 끓인다.
2) 스프를 넣는다.
3) 면을 넣는다.
4) 더 끓인다.
5) 젓가락을 집는다.
이처럼 알고리즘이란, 정해진 순서대로 따라가며 특정 과제를 달성하기 위한 명령어 집합이라고 보면 된다.
2. 1 정렬된 배열
새로운 자료 구조인 '정리된 배열(ordered array)'를 알아보자.
"정렬된 배열"은 1장에서 설명한 '전형적인' 배열과 거의 같기 때문에 값이 항상 순서대로 있어야 한다. 즉, 값을 추가할 때마다 적절한 셀에 넣어 배열의 값을 정렬된 상태로 유지한다.
예를 들어 배열 [ 3, 17, 80, 202 ]를 표현해보자.
| 3 | 17 | 80 | 202 |
이 배열에 75를 삽입한다면, 전형적인 배열이라면 맨 마지막에 삽입할 것이다.
| 3 | 17 | 80 | 202 | 75 |
이건 한 단계로 삽입을 처리할 수 있다.
하지만 정렬된 배열에서는 값을 오름차순으로 유지하기 위해 중간에 삽입해야 한다.
| 3 | 17 | 75 | 80 | 202 |
컴퓨터는 75를 올바른 위치에 바로 넣는 작업을 한 단계로 처리할 수 없다. 먼저 75가 들어갈 올바른 위치를 찾아야 하고, 이후 다른 값들을 옮겨 빈 공간을 만들어야 한다.
정렬된 배열에 삽입할 때는 항상 검색을 먼저 수행해서 삽입할 올바른 위치를 정해야 한다. 따라서 N에 대해 정렬된 배열에 원소가 N개이면 삽입에 총 N + 2단계 걸린다. 값이 정렬된 배열 앞부분에 놓이면 비교가 줄어들고 이동이 늘어나는 반면, 값이 뒷부분에 놓이면 비교가 늘어나고 이동이 줄어들기 때문에 배열 어디에 놓이게 되든 삽입에 필요한 단계 수는 비슷하다.
다만 새 값이 배열 맨 끝에 놓이면 이동하지 않아도 되니 단계 수가 가장 적다. 기존 N값과 모두 비교하고 삽입 자체에 1단계가 걸리니 총 N + 1단계다.
정렬된 배열은 전형적인 배열보다 삽입에 있어 덜 효율적이다. 하지만 검색 연산에선 더 강력하다.
2. 2 정렬된 배열의 검색
1장에선 전형적인 배열에서 특정 값을 검색하기 위해 왼쪽부터 오른쪽으로 한 번에 한 셀씩 확인하는 과정을 배웠고, 이러한 과정을 '선형 검색'이라고 불렀다. 하지만 정렬된 배열에서 선형 검색은 전형적인 배열과 다르다.
만약 [ 17, 3, 75, 202, 80 ]이라는 배열이 있다고 하자. 배열에 없는 22라는 값을 찾으려고 한다면 모든 원소를 하나도 빠짐없이 검색해야 한다. 중간에 검색을 멈추는 경우는 오로지 원하는 값을 찾았을 때뿐인데, 22는 없는 값이므로 검색은 끝까지 진행된다.
하지만 정렬된 배열에서는 값이 배열에 들어있지 않을 때 검색이 더 빨리 멈출 수 있다. 왜냐하면 이미 오름차순으로 정렬된 상태로 22는 75보다 작기 때문에 75까지 원하는 값이 없다면 바로 검색을 중단할 수 있다.
선형 검색은 전형적인 배열보다 정렬된 배열에서 단계 수가 더 적게 걸린다. 물론 찾으려는 값이 배열의 마지막 값이거나 마지막 값보다 크면 마찬가지로 모든 셀을 검색해야 돼서 일반적인 배열과 정렬된 배열이 효율성 면에서 큰 차이가 없어 보인다.
하지만 '선형 검색'은 값을 검색하는 알고리즘 중 하나일 뿐이다. 정렬된 배열이 전형적인 배열보다 두드러진 장점은 다른 검색 알고리즘을 쓸 수 있다는 점이다. 우리는 그것을 '이진 검색(binary search)'이라 부른다. 이진 검색은 선형 검색보다 훨씬 빠르다.
2. 3 이진 검색
'이진 검색'이란, 우리가 어릴 때 했던 숫자 알아맞추기 게임과 동일하다. 상대방이 어떤 수를 생각하고 있는지 추측하기 위해서 중간값을 이야기 한 다음 나머지 수 중 반을 없애는 것이다. 1부터 100 사이의 값 중 하나를 맞추기 위해 처음에 50을 말해서 나머지 절반을 없애고, 다음으로 75를 고른다. 이런 식으로 계속 중간 지점을 골라 남은 수 중 반을 제거하는 방식이다.
정렬된 배열에서 이진 검색은 유용하다.
만약 원소 9개를 포함하는 '정렬된 배열'이 있고, 값 7을 찾는다고 가정하자.
| ??? | ??? | ??? | ??? | ??? | ??? | ??? | ??? | ??? |
컴퓨터는 각 셀에 어떤 값이 있는지 바로 알 수 없다. 그래서 먼저 가운데 셀부터 검색을 시작한다.
1단계) 배열의 길이를 2로 나누어 가운데 셀의 인덱스를 계산하여 접근한다. 가운데 셀의 값을 확인하면,
| ??? | ??? | ??? | ??? | 9 | ??? | ??? | ??? | ??? |
값이 9이므로 7은 왼쪽 어딘가에 있다고 판단할 수 있다. 따라서 배열에 있는 셀의 절반, 즉 9보다 오른쪽에 있는 모든 셀은 제거된다.
| ??? | ??? | ??? | ??? |
2단계) 9보다 왼쪽에 있는 셀들 중 가운데 값을 확인한다. 가운데 값이 두 개이므로 임의로 왼쪽 값을 선택한다.
| ??? | 4 | ??? | ??? |
값이 4이므로, 7은 오른쪽 어딘가에 있다. 4와 그 왼쪽 셀을 제거한다.
| ??? | ??? |
3단계) 나머지 셀 중 임의로 왼쪽 셀을 선택한다.
| 6 | ??? |
어라? 이것도 아니다.
4단계) 그러면 마지막 남은 셀을 확인한다(여기에도 7이 없으면 이 정렬된 배열에는 7이 없다는 뜻이다).
| 7 |
4단계 만에 7을 찾았다.
전형적인 배열은 값의 순서가 뒤죽박죽이어서 주어진 값의 왼쪽에서 찾을지 오른쪽에서 찾을지 절대 알 수 없기 때문에 이진 검색은 정렬된 배열에만 쓸 수 있다. 이진 검색을 수행할 수 있다는 것은 정렬된 배열의 장점 중 하나이다!
2. 4 이진 검색 대 선형 검색
100개의 값을 갖는 배열에서 각 검색에 필요한 최대 단계 수는 다음과 같다.
▶ 선형 검색 : 100단계
▶ 이진 검색 : 7단계
선형 검색에서는 찾고 있는 값이 마지막 셀에 있거나 마지막 셀의 값보다 크면 모든 원소를 조사해야 한다.
하지만 이진 검색을 쓰면 추측할 때마다 검색해야 할 셀 중 절반을 제거할 수 있다. 따라서 배열의 크기를 두 배 늘리면 이진 검색에 필요한 최대 단계 수가 1씩 증가한다. 이러한 증가 패턴은 대단히 효율적이다. 데이터를 두 배로 늘릴 때마다 이진 검색 알고리즘에서는 최대 한 단계만 더 추가하면 된다.
선형 검색은 원소가 3개 있으면 최대 3단계가 필요하고, 원소가 1,000개 있으면 최대 1,000단계가 필요하다. 선형 검색에서는 원소 수만큼의 단계가 필요하다. 배열의 원소 수를 두 배로 늘릴 때마다 검색에 필요한 단계 수도 두 배로 늘어난다.
이진 검색에서는 배열의 원소 수를 두 배로 늘릴 때마다 한 단계만 늘어난다. 크키가 1,000,000개인 배열에서 선형 검색은 최대 1,000,000단계가 걸리지만, 이진 검색은 최대 20단계면 된다.
정렬된 배열은 '삽입 연산'에서 일반 배열보다 느리다(먼저 올바른 위치를 찾기 위해 검색 단계가 필요하기 때문에). 정렬된 배열을 사용하면 삽입은 다소 느리지만, 검색은 훨~~~ 씬 빠르다.
사용자의 애플리케이션에 어떤 구조가 더 좋은지 알려면 항상 분석이 필요하다. 소프트웨어에서 삽입이 자주 일어나는지, 검색이 개발 중인 앱의 중대한 기능인지 말이다.
2. 5 마무리
모든 상황에 완벽하게 들어맞는 단 하나의 자료 구조나 알고리즘은 거의 없다. 정렬된 배열에서 이진 검색을 사용할 수 있다고 해서 항상 정렬된 배열을 써야 하는 것도 아니다. 데이터 검색은 거의 없고, 데이터를 추가하기만 한다면 삽입을 더 빠르게 처리하는 배열이 더 나은 선택일 수도 있다.
해당 글은 '누구나 자료구조와 알고리즘' 책의 내용을 기반으로 작성되었습니다.
오로지 학습용으로 작성하였음을 밝힙니다.
더 자세한 내용을 확인하고 싶다면 해당 저서를 참고하시길 바랍니다.