네…썰렁하죠? 사실 이건 오래 전에 유행했던 일종의 허무 개그예요. 마치 엄청나게 어려운 문제를 가능하게 하는 놀라운 해결책이 있는 것처럼 묘사한 후, 문제 해결의 관건인 코끼리와 냉장고의 크기는 배재한 채, 단순히 넣는 과정만을 서술하여 허탈함과 웃음을 유발하는 것이죠.

그런데 갑자기 이런 얘기를 왜 하느냐고요? 이 구식 개그가 오늘의 주제인 ‘알고리즘’과 관련이 있기 때문이에요.

알고리즘, 익숙한 단어이지만 그 뜻을 정확히 이해하고 있는 사람은 드물거에요. 알고리즘은 사실 전혀 어려운 단어가 아니에요. 알고리즘이란 그저 ‘문제를 해결하기 위한 일련의 절차’거든요.

우리가 가장 흔히 볼 수 있는 알고리즘은 바로 ‘레시피’에요. 어떤 음식을 만드는 ‘문제’를 단계적으로 지시된 ‘절차’에 따라 해결하는 것이 레시피이니까요. 라면 봉지 뒤에 적힌 조리법도 사실 일종의 알고리즘인 것이죠.

우리는 여기서 앞서 언급한 허무 개그에 대해 다시 생각해볼 수 있어요. ‘냉장고에 코끼리를 넣는 방법’도 알고리즘이라고 볼 수 있을까요?

알고리즘의 조건 ✍️

어떤 문제를 절차적으로 해결한다고 해서 모든 방법이 알고리즘의 자격을 얻는 것은 아니예요. 알고리즘에는 사실 다섯 가지 조건이 존재하거든요.

• 입력 : 알고리즘에는 입력이 없거나 존재해야 한다.
• 출력 : 알고리즘은 최소 하나 이상의 결과를 가져야한다.
• 명확성 : 알고리즘을 구성하는 단계들의 의미는 명확해야 하며, 애매함이 없어야 한다.
• 유한성 :  알고리즘은 한정된 수의 단계들을 거친 후 문제를 해결하고 종료해야 한다.
• 효과성 : 알고리즘의 모든 단계들은 실행 가능하여야 한다.

이 조건들을 모두 충족해야 비로소 알고리즘이라고 인정받을 수 있어요. 이 조건들을 바탕으로 ‘냉장고에 코끼리를 넣는 방법’이 과연 진짜 알고리즘인지 판별해 볼까요?

우선, ‘입력’과 ‘출력’ 조건부터 살펴볼게요. 입력이란 문제를 해결하기 위해 필요한 요소를 뜻해요. 이 경우에는 ‘냉장고’와 ‘코끼리’가 바로 입력이죠. 반대로 출력은 문제를 처리했을 때의 결과예요. ‘코끼리가 들어간 냉장고’를 ‘출력’이라고 할 수 있어요.

이어지는 세 조건은 모두 단계에 대한 조건이에요.

'냉장고에 코끼리를 넣는 방법'의 세 단계를 다시 떠올려볼까요?

이렇게 간단한 세 단계의 의미를 오해할 사람은 아마 존재하지 않겠죠. ‘명확성’은 가볍게 충족할 수 있을 거예요. 세 단계만을 거치면 문제가 바로 해결되기 때문에 ‘유한성’ 조건도 충족할 수 있어요.

하지만 관건은 ‘효과성’이예요. 코끼리를 냉장고에 넣는 것은 현실적으로 불가능하기 때문이죠. 코끼리가 아주 작은 아기 코끼리거나, 코끼리도 들어갈 정도로 거대한 냉장고가 존재하지 않는 이상 말이에요. 고로, ‘냉장고에 코끼리를 넣는 방법’은 효과성 조건을 충족하지 못하기 때문에 알고리즘이라고 볼 수 없어요. 물론 ‘냉장고에 아기 코끼리를 넣는 방법’ 혹은 ‘거대 냉동창고에 코끼리를 넣는 방법’은 알고리즘이 될 수 있겠죠?

알고리즘의 다섯 가지 조건만 충족한다면, 하나의 문제에도 여러 개의 알고리즘이 존재할 수 있어요. 설악산 정상에 오르는 방법을 예로 들어보죠. 설악산 정상에 오르기 위해서는, 케이블카를 탈 수도 있고, 걸어서 등반할 수도 있어요. 심지어 헬기를 타고 정상보다 높이 올라가 레펠 하강을 할 수도 있죠. 그 외에도 수많은 방법이 존재할 거예요. 그리고 이 방법들은 모두 단계적으로 설명할 수 있어요.

이런 식으로 말이에요.

설악산 정상에 오른다는 ‘문제’를 일련의 ‘절차’를 통해 해결하니, 앞서 말한 다양한 방법들은 모두 저마다의 ‘알고리즘’이라고 할 수 있는 것이죠. (물론, 다섯 가지 조건을 충족해야 해요!)

무엇이 좋은 알고리즘이지? 👀

알고리즘은 그 종류가 다양한 만큼 장단점도 뚜렷해요. 케이블카를 타고 정상에 오르는 방식은 시간은 얼마 걸리지 않지만 돈이 많이 들고, 걸어서 등반하는 것은 돈은 한 푼도 들지 않지만 시간이 오래 걸리죠. 자신의 상황에 따라 적절한 방법을 선택하면 되는 거예요.

하지만 같은 비용과 같은 시간임에도 더 빠르고 저렴하게 등반하는 방법도 분명 존재해요. 이런 방법을 우리는 ‘효율적’이라고 평가하죠.  

이는 컴퓨터 프로그램에도 똑같이 적용할 수 있어요. 어떤 알고리즘을 택하느냐에 따라 프로그램의 성능은 눈에 띄게 달라져요. 더 효율적인 알고리즘을 택하여 적재적소에 잘 활용하는 것이 훌륭한 프로그래머의 자질이죠.

시간 복잡도 ⏲️

그렇다면 알고리즘의 효율성은 어떻게 평가할 수 있을까요?

총 100페이지로 이루어진 책에서 89페이지를 찾는 문제를 생각해보죠. 이 문제를 해결하는 알고리즘은 수없이 다양할 거예요.

가장 쉬운 방법은 단연 1페이지부터 89페이지가 나올 때까지 전부 펴보는 거예요. 이렇게 모든 경우의 수를 일일이 탐색하면서 필요한 값을 찾아내는 방식을 ‘브루트포스 알고리즘’이라고 해요. 직역하자면 난폭한(brute) 힘(force) 알고리즘이죠. 그 이름에 걸맞게 굉장히 무식하고 비효율적인 알고리즘이에요. 브루트포스 알고리즘으로 89페이지를 찾으려 한다면, 89개의 페이지를 모두 확인하는 과정을 거쳐야 하니까요.

이제 좀 더 유식한 방법을 생각해보죠. 이건 어때요? 책을 반으로 가르는 거예요. 그 다음 89페이지가 어디에 위치하나 판단하는 것이죠. 100페이지로 이루어진 책은 1~50페이지와 51~100페이지로 나눌 수 있을 거예요. 81은 51보다 큰 수이니, 1~50페이지는 고려하지 않아도 되겠네요!

한번 더 반복해볼까요? 51페이지와 100페이지는 51~75페이지와 76~100페이지로 나뉘어요. 81은 76보다도 크니 89페이지가 있을 만한 곳은 76페이지에서 100페이지 사이로 줄었어요.

76과 100은 다시 76~88페이지와 89~100페이지로 나눌 수 있어요. 어라? 벌써 89페이지를 찾았어요!

이런 식으로 탐색 범위를 줄여 나가면서 원하는 값을 찾아내는 알고리즘을 바로 이진 탐색이라고 해요. 우리는 이진 탐색을 활용하여 단 3단계만에 89페이지를 찾아낼 수 있었어요. 브루트포스 알고리즘은 89단계나 필요했는데 말이예요. 이진 탐색이 브루트포스 알고리즘보다 훨씬 효율적인 알고리즘이라는 것이죠.

문제를 해결하는 데 필요한 단계가 적다는 것은 소요되는 시간이 그만큼 짧다는 것을 뜻해요. 물론, 위 문제에 컴퓨터를 활용한다면, 두 알고리즘의 소요 시간 차이는 그리 크지 않을 거예요. 컴퓨터의 연산 속도는 상상 이상으로 빠르니까요.

하지만 효율적인 알고리즘의 진가는 연산량이 많아질 때 드러나요. 문제를 조금 바꿔볼까요? 총 페이지가 1억 페이지인 책에서 910,300,000페이지를 찾는 거예요. 이런 경우에는 이진탐색이 확실한 강력함을 뽐내죠. 브루트포스 알고리즘이 910,300,000번의 연산을 하는 동안, 이진 탐색은 시작부터 1억의 절반인 5천만 페이지를 날려버릴 수 있으니까요.

효율적인 알고리즘이란 입력값이 커질 때, 늘어나는 소요 시간의 비율이 작은 알고리즘을 의미해요. 입력값이 커짐에 따라 부르트포스 알고리즘과 이진 탐색 모두 소요 시간은 증가하죠. 허나 중요한 것은 ‘얼마나’ 증가하냐는 것이에요. 이진 탐색이 브루트포스 알고리즘보다 효율적인 이유는 바로, 입력값이 커지더라도 비교적 덜 늘어나는 소요 시간에 있는 거예요.

이처럼, 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간을 바로 ‘시간 복잡도’라고 해요. 입력이 커지는 것에 비해서 소요 시간이 너무 많이 늘어나는 알고리즘을 두고 시간 복잡도가 높다고 말하죠.

마무리

이번 레터에서는 알고리즘의 조건과 알고리즘을 평가하는 기준에 대해서 알아봤어요. 알고리즘에 대한 궁금증을 말끔히 해결한 시간이 되었길 바라요. 알고리즘에 대하여 더 궁금한 게 있다면 아래 피드백 란에 남겨주세요! 다음 콘텐츠 주제에 대한 요청도 언제나 환영이랍니다~😝