지난 시간에는 문제에 대한 해결 과정인 알고리즘의 정의를 배웠습니다. 이번 시간에는 하나의 문제를 두고 얼마나 많은 알고리즘이 구현될 수 있는지 함께 알아보도록 하겠습니다.
🧮 여러 가지 방법으로 문제 해결하기
여러분은 신발 가게에 가서 원하는 브랜드의 신발을 찾아 구매하려고 합니다. 이때, 브랜드는 알파벳 순서로 나열되어 있습니다. 어떻게 하면 원하는 브랜드를 찾을 수 있을까요?
방법은 여러 가지입니다. 그 중 두 가지 방법을 함께 봅시다. 첫번째 방법은 알파벳순으로 정렬되어 있다는 전제 하에 A 브랜드를 시작으로 차례로 내려와 원하는 브랜드를 찾으면 신발을 꺼내오면 됩니다.
혹은 우선 중간 지점의 알파벳을 기준으로 두고 원하는 브랜드를 찾아보는 방법도 있습니다. 만약 원하는 브랜드가 중간 지점보다 앞에 있다면 중간보다 뒤에 있는 브랜드는 볼 필요가 없겠죠?
그렇게 뒷 부분을 제외한 뒤 다시 중간 지점을 찾고 앞뒤를 비교하여 필요없는 브랜드는 제외하면 됩니다. 이런 식으로 반씩 제외하는 걸 반복하다 보면 결국에는 원하는 브랜드를 찾을 수 있습니다.
이처럼 세상에는 같은 문제를 해결하는 여러 가지 방법들이 존재합니다. 그러나 어떤 방법으로 해결하느냐에 따라 시간적, 비용적 효율이 각각 다른데요. 알고리즘 공부는 다양한 방법들을 고민하고 그 중에서 효율적인 방법이 무엇인지 분석하는 것입니다.
🧮 선형 탐색과 이진 탐색
앞서 설명한 브랜드의 예제는 알고리즘의 대표적인 문제인 탐색에 대한 예시였습니다. 탐색이란, 저장된 정보들 중에서 원하는 값을 찾는 것을 말합니다. 프로그래밍에서는 리스트에 나열된 수 중 원하는 수를 찾는 것으로 예를 들어볼 수 있겠네요.
앞에서 원하는 브랜드를 찾을 때, 두 가지 방법을 제시했었죠? 두 방법은 프로그래밍에서 각각 선형 탐색 알고리즘과 이진 탐색 알고리즘으로 불립니다.
예시를 한 번 볼까요? 10개의 숫자 요소를 가진 리스트가 있다고 가정합시다.
[1, 1, 2, 3, 5, 8, 13, 21]여기서 우리는 8을 찾고 싶습니다. 브랜드의 사례에서 첫번째로 활용했던 방법은 왼쪽부터 차례로 살펴보는 것이었습니다. 이 방법을 활용하면 1부터 시작해서 차례로 보다가 8이 나오면 그 뒤는 볼 필요도 없이 종료하면 됩니다. 이런 식으로 하나씩 차례로 보는 방법을 선형 탐색 알고리즘(linear search algorithm)이라고 합니다.
두번째 방법도 볼까요? 여기서 중간 값은 3이나 5정도가 될 수 있을 것 같습니다. 5를 기준으로 봅시다. 리스트가 숫자의 크기순으로 나열되어 있는 만큼 8은 5보다 큰 숫자니 뒷쪽에 있을 확률이 큽니다. 그럼 이제 5의 왼쪽은 볼 필요가 없어집니다.
8, 13, 21이제 5를 포함한 그 왼쪽 부분을 제외한 나머지 리스트에서 또 중간 값을 찾아봅시다. 이 리스트에서는 13이 중간 값입니다. 8은 13보다 작으니 앞 부분에 있겠죠? 그래서 13을 포함한 뒷 부분을 제외해줍니다. 그럼 8 하나가 남고 8은 우리가 원하는 숫자이니 탐색이 종료됩니다.
이렇게 중간 값을 기준으로 수를 비교하고 필요 없는 수를 배제하는 방법을 이진 탐색 알고리즘(binary search algorithm)이라고 합니다.
두 방법 중 어떤 방법이 더 효율적인지 알아보기 전에 두 알고리즘을 프로그래밍으로 한 번 구현해보도록 합시다.
🧮 선형 탐색 구현하기
리스트의 처음부터 끝까지 순서대로 하나씩 탐색을 진행하는 함수 linear_search를 작성해봅시다. 이 함수는 파라미터로 원하는 값 value와 리스트 my_list를 받습니다.
def linear_search(value, my_list):0번 인덱스부터 차례로 하나씩 확인해서 만약 value가 my_list 안에서 발견되면 즉시 그 인덱스를 리턴하고 프로그램을 종료합니다. 만약 my_list를 다 돌고도 value와 같은 값을 못 찾으면 None을 리턴해줍니다.
우선, 리스트를 차례로 돌기 위해 반복문이 필요합니다. 이럴 때, 적합한 반복문은? 네, 맞습니다. 한정된 범위를 돌 때는 for문이 적합합니다. 이제 이 for문은 리스트의 길이만큼 돌 예정입니다.
for i in range(len(my_list)):for문이 리스트를 도는 동안 해야할 일은 value와 my_list의 인덱스 값이 같은지 다른지를 확인하는 겁니다. 이에 적합한 명령어는 뭐가 있을까요? value와 값이 다르면 계속 돌고 같으면 인덱스를 반환하고 종료해야 합니다. 조건이 달려있죠? 따라서, if문을 활용하는 것이 좋겠네요.
if value == my_list[i]:
return i위 코드를 보면 종료 조건은 적어줬지만 값이 다를 때의 수행 부분은 적지 않았습니다. 왜냐하면 그 부분은 for문을 다 돌고 난 이후의 수행되어야 하기 때문이죠. 따라서, for문을 벗어나서 적어주도록 합시다.
return None사실 이 부분은 적지 않아도 크게 문제 되지는 않습니다. 어차피 return은 따로 명령어가 없으면 None을 반환하기 때문이죠. 그럼에도 적어주는 이유는 가독성을 높이기 위해서입니다. 다른 사람들이 볼 때, 리스트를 다 돌고도 원하는 값이 없으면 None을 리턴한다는 사실을 바로 알아볼 수 있게끔요.
이제 lenear_search 함수의 코드를 한 번에 봅시다.
def lenear_search(value, my_list):
for i in range(len(my_list)):
if value == my_list[i]:
return i그리고 두 가지 예시를 보도록 하죠.
print(linear_search(4, [2, 4, 6, 8, 10]))
print(linear_search(1, [2, 4, 6, 8, 10]))1
None🧮 이진 탐색 구현하기
다음으로 어떤 원소가 리스트 안에 포함되어 있는지 확인하는 binary_search 함수를 작성해 봅시다. 이 함수도 마찬가지로 찾을 값 value와 리스트 my_list를 파라미터로 받습니다.
여기서 한 가지 주의해야 할 사항이 있습니다. 선형 탐색과 달리 이진 탐색은 리스트가 정렬되어 있다는 것이 전제되어야 합니다. my_list가 정렬되어 있지 않으면 이진 탐색 알고리즘을 적용할 수 없습니다.
이진 탐색. 단어가 낯설지 않으신가요? 단어 '이진(binary)'에는 '두 부분으로 나누어진'이라는 뜻을 담고 있습니다. 비교를 할 때마다 탐색 범위가 절반으로 줄어들기 때문에 이진이라는 단어가 사용된 것입니다.
이진 탐색은 선형 탐색보다 코드가 좀 더 복잡합니다. 조건들이 더 많기 때문인데요. 하나씩 나누어서 살펴봅시다.
❗ 중간 인덱스 구하기
제일 먼저 해야할 일은 리스트의 중간 지점을 구하는 일입니다. 이를 위해 우리는 중간 인덱스를 찾아야 합니다. 중간 인덱스를 구하는 방법은 첫번째 인덱스와 마지막 인덱스를 더하고 그 수를 2로 나누면 됩니다. 이를 위해, 각자의 변수를 선언해줍니다.
first_index = 0
last_index = len(my_list)-1첫번째 인덱스는 통상 0입니다. 마지막 인덱스의 경우, 리스트의 길이에서 1을 빼면 구할 수 있습니다. 이제 중간 인덱스를 구해볼까요? 중간 인덱스를 구하는 김에 중간 값도 구해 봅시다.
middle_index = (first_index + last_index) // 2
middle = my_list[middle_index]❗ 값 비교
중간값을 구했다면 다음으로 해야 할 일은 찾을 값 value와 중간값의 크기를 비교하는 것입니다. 만약 중간값보다 value가 작다면 중간값부터 뒷 부분은 필요 없겠죠? 반대로 중간값보다 value가 크다면 중간값을 포함해서 앞 부분은 필요가 없습니다.
이를 코드로 구현해 봅시다. 앞서 얘기했듯 여러 조건이 주어지면 if문을 활용하면 됩니다.
if value < middle:
last_index = middle_index - 1
elif value > middle:
first_index = middle_index + 1
elif value == middle:
return middle_indexif문의 수행 부분을 보면 각각 last_index와 first_index의 값을 middle_index를 기준으로 변경했습니다. 이런 식으로 중간값의 앞뒤 값을 제거한 새로운 리스트를 만들 수 있는 것이죠.
그리고 마지막 조건으로는 두 값이 일치할 때를 적어주었습니다. 인덱스를 구하는 메소드 .index를 아시죠? 이를 통해 인덱스를 반환할 수 있습니다.
❗ for 반복문
그런데 중요한 것은 값 비교는 한 번만 해서는 안 되고 리스트를 도는 동안 계속해서 이루어져야 합니다. 따라서, for문을 활용해야 되죠.
또 하나 생각해야 될 것은 for문이 적용될 범위입니다. 어디서부터 for문을 시작해야 할까요? 만약, 모든 코드를 for문으로 감싸게 되면 어떻게 될까요?
이 코드의 첫 부분에는 첫 번째 인덱스와 마지막 인덱스의 변수를 지정해주었습니다. 이 부분이 for문에 들어가게 되면 for문이 도는 동안 계속해서 두 값이 초기화 될 것입니다. 기껏 middle_index를 통해 초기 값과 끝 값을 바꿨는데 자꾸 초기화가 되면 안되겠죠? 따라서 이 부분은 for문에서 빠져야 합니다.
그렇다면 중간값은 어떨까요? 정답부터 말하자면 포함되어야 합니다. 왜냐하면 중간값은 계속해서 변해야 되는 값이기 때문이죠. 예를 들어, 찾는 값이 중간값보다 작아서 맨 끝 인덱스가 변경되면 자연히 중간값도 새로 바뀐 리스트에 따라 바뀌어야 합니다.
이 말은 곧, 조건문 또한 반복문 안에 들어가야 된다는 얘기가 됩니다. 즉, 중간값 설정과 조건문이 for문 안에 들어와 for문이 리스트를 도는 동안 계속해서 수행되어야 한다는 것이죠. 이렇게 for문을 정리하면 다음과 같습니다.
for middle_index in range(len(my_list)):
middle_index = (first_index+last_index) // 2
middle = my_list[middle_index]
if value < middle:
last_index = middle_index - 1
elif value > middle:
first_index = middle_index + 1
elif value == middle:
return middle_index자, 이제 마찬가지로 for문을 다 돌고도 원하는 값을 찾지 못할 때에는 None을 반환해준다는 명령어 return None을 for문 밖에 적어주면 됩니다.
완성된 함수와 그 예시를 봅시다.
def binary_search(value, my_list):
first_index = 0
last_index = len(my_list) - 1
for middle_index in range(len(my_list)):
middle_index = (first_index+last_index) // 2
middle = my_list[middle_index]
if value < middle:
last_index = middle_index - 1
elif value > middle:
first_index = middle_index + 1
elif value == middle:
return middle_index
return Noneprint(binary_search(4, [2, 4, 6, 8, 10]))
print(binary_search(1, [2, 4, 6, 8, 10]))1
None🧮 탐색 알고리즘 비교
두 알고리즘을 모두 구현해봤습니다. 이제 어느 알고리즘이 더 효율적인지 알아볼 차례입니다.
먼저, 선형 탐색 알고리즘부터 보겠습니다. 8개의 리스트가 주어졌을 때, 가장 빨리 값을 찾는 경우는 첫번째 인덱스의 값을 찾을 때일 것입니다. 앞에서부터 순차적으로 찾기 때문이죠. 그렇다면 반대로 가장 느리게 값을 찾는 경우는 없는 값을 찾을 때일 것입니다.
다시 말하자면, 첫번째 인덱스 값의 경우 딱 한 번만 찾으면 됩니다. 그러나 값이 없을 때는 순차적으로 여덟 개의 숫자를 거쳐야 합니다.
이진 탐색 알고리즘의 경우에는 어떨까요? 가장 빨리 찾는 경우는 아무래도 리스트의 중간값이 되겠죠? 중간 지점부터 구하니 말입니다. 그럼 가장 느린 경우는 어떨 때일까요? 마찬가지로 값이 없을 때입니다.
8개의 리스트라면 8개에서 4개, 4개에서 2개, 그리고 2개에서 1개가 되고 종료되기까지 총 3번을 거쳐 탐색이 이루어집니다. 그런데 생각해보면 찾는 값이 없을 때조차 이진 탐색은 딱 3번의 탐색을 거칩니다. 선형 탐색이라면 8번의 수를 다 돌아야 알게되는 결과인데 말이죠.
수를 늘려서 생각해보면 리스트의 길이가 16일 때, 최악의 경우를 가정하면 선형 탐색은 16번, 이진 탐색은 4번에 걸쳐 프로그램이 돌아갑니다. 32인 경우에는 선형 탐색 32번, 이진 탐색 5번입니다. 수가 늘어날 수록 두 차이가 매우 크게 나타나죠?
그렇다면 선형 탐색은 늘 비효율적인 선택일까요? 그렇지 않습니다. 앞서 이진 탐색은 정렬된 리스트의 경우에만 활용해볼 수 있다고 했습니다. 따라서, 정렬되지 않은 리스트의 경우에는 선형 탐색이 더 효율적이라 할 수 있죠.
이번 시간에는 한 가지 문제에 대한 여러 가지 알고리즘의 예로 탐색에 대해 알아봤습니다. 그리고 두 알고리즘을 코드로 구현해 보기도 했죠. 이처럼 알고리즘은 단순히 개념만 이해하는 것이 아니라 코드로 구현해 보는 과정 또한 중요합니다. 결국에는 컴퓨터가 이 알고리즘에 따라 일을 수행해야 하기 때문이죠?
많이 어려우셨나요? 그럴수록 복습이 필요합니다. 천천히 코드를 복기해보세요. 일단 이해가 되면 그 다음은 쉽습니다.
다음 시간에는 여러 가지 알고리즘의 또 다른 사례를 다뤄보려 합니다. 계속해서 더 알아가 봅시다.
* 이 자료는 CODEIT의 '알고리즘의 정석' 강의를 기반으로 작성되었습니다.