좋은 알고리즘 작성법, 재귀 함수를 거쳐 알고리즘 패러다임 시간입니다!
알고리즘에도 수학처럼 공식이 있다는 것을 아셨나요? 여지껏 우리는 이러한 공식 없이 어찌보면 아주 무식한 방법으로 알고리즘을 풀어왔습니다.
하지만 이번 시간에 배울 알고리즘 패러다임을 익히면 여러분도 효율적인 알고리즘을 생각해 낼 수 있는 힘을 기를 수 있습니다.
🦸♂️ 알고리즘 패러다임
세상에는 다양한 문제들이 있습니다. 그리고 그 다양한 문제들에는 또 다양한 문제 해결 방법들이 있었죠. 우리는 지금까지 효율적으로 문제를 풀기 위한 좋은 알고리즘에 대해 고민해 왔습니다.
이렇게 다양한 문제들을 풀다보면 알고리즘을 생각해내는 과정들이 겹치는 경우가 종종 있습니다. 그 이유는 알고리즘을 만들어내는 여러 접근법들 중 유사한 것이 많기 때문이죠.
이렇게 자주 나타나는 알고리즘 접근법을 하나로 묶은 것을 알고리즘 패러다임이라고 부릅니다.
하나의 문제에 대해 여러 알고리즘을 떠올려 볼 수 있듯 반대로 여러 알고리즘 패러다임으로 같은 문제에 접근해 볼 수 있습니다.
알고리즘 패러다임을 익히면 이전에 맨땅에 헤딩하듯 알고리즘을 구상했던 것과는 달리 어떤 식으로 풀어나가야 할지 감이 생깁니다.
문제를 분석하고 해결 방법을 찾아내는 동안 사고력이 늘기도 하고 나름의 노하우도 생각할 수 있게 됩니다. 그러다보면 막막했던 문제도 효율적으로 해결할 수 있는 요령이 생기기도 하죠.
🦸♂️ Brute Force
첫번째 알고리즘 패러다임은 'Brute Force'입니다. 암호학에는 'Brute-Force Attack'이라는 개념이 있는데요. 우리말로는 무차별 대입 공격이라는 뜻을 가지고 있습니다.
Brute Force란, 말 그대로 무차별적으로 가능한 모든 방법을 다 시도하는 것을 의미합니다.
학창 시절 사용했던 자물쇠의 암호를 기억하시나요? 대개 세 자리에서 네 자리로 이루어진 이 암호는 000부터 999 혹은 0000부터 9999에서 지정한 수를 찾아내야 합니다.
이 자물쇠의 암호를 풀기 위해서는 어떻게 해야 할까요? 가장 쉽게 생각할 수 있는 방법은 무식하게 000부터 999까지 가능한 모든 경우의 수를 전부 시도해보는 것입니다. 시간이 엄청 소요되긴 하지만 하다 보면 풀릴 거라는 확신을 가질 수 있는 방법입니다.
이처럼 Brute Force는 어떤 문제에 대해 가능한 모든 경우의 수를 시도하는 가장 순진한 알고리즘 접근법입니다.
예시를 한 번 볼까요? 숫자 카드 네 장이 있다고 가정합시다. 왼쪽에는 숫자 1, 4가 있고 오른쪽에는 숫자 2, 3이 있습니다.
이제 이 네 장의 카드에서 왼쪽 카드 한 장과 오른쪽 카드 한 장을 각각 뽑은 후, 두 수를 곱하여 가장 큰 값을 만들어야 합니다.
Brute Force에 따라 가능한 모든 경우의 수를 도출해봅시다.
1 x 2 = 2
1 x 3 = 3
4 x 2 = 8
4 x 3 = 12
이렇게 총 4가지 경우의 수가 나옵니다. 이 중에서 가장 큰 값은 4와 3의 곱인 12입니다. 가장 큰 값을 찾았으므로 이 문제는 해결되었습니다.
❗ Brute Force 코드로 구현하기
이를 코드로 구현해봅시다.
def max_cards(left_cards, right_cards):
max_product = -1
for left in left_cards:
for right in right_cards:
max_product = max(max_product, left * right)
return max_product함수 max_cards는 파라미터로 카드 숫자 리스트를 받고 두 리스트의 수의 곱 중 최댓값을 리턴합니다.
카드 수의 최대 곱을 위한 변수 max_product를 선언하고 초기값을 -1로 설정해줍니다. 초기값을 설정하는 이유는 리스트에서 뽑은 수들의 곱과 비교해서 가장 큰 값을 넣어주기 위함입니다.
이제 반복문을 만들어줘야 하는데요. 두 리스트를 돌아야 하므로 반복문도 두 개가 필요합니다.
두 반복문을 도는 동안 max 함수를 통해 max_product와 두 수의 곱을 비교하여 최댓값을 찾고 그 결괏값이 max_product에 들어가게 됩니다.
다시 말해, 두 수의 곱이 max_prodcut보다 크면 max_product는 그 수로 새롭게 갱신되는 것이죠.
이를 반복하여 최종적으로 설정된 max_product 값이 최댓값이 되고 반환됩니다.
print(max_cards([1, 4], [2, 3]))12시간 복잡도도 구해볼까요?
len(left_cards)를 m, len(right_cards)를 n이라고 합시다.
함수 max_cards에는 left_cards를 도는 반복문 안에 right_cards를 도는 반복문이 중첩되어 있으므로 시간 복잡도는 O(mn)이 됩니다.
🦸♂️ Brute Force 평가
Brute Force 방식을 사용하면 모든 경우의 수를 도출하기 때문에 언젠가는 답을 찾을 수 있다는 확신을 가질 수 있습니다.
하지만 모든 경우의 수를 도출한다는 것은 시간적으로 매우 비효율적인 것 같습니다. 이렇듯 일반적으로 Brute Force 방식은 비효율적이라는 평가를 받고 있습니다. 특히 인풋이 커질수록 더욱 그렇죠.
만약 알파고가 Brute Force 방식으로 바둑을 둬야 한다면 어떤 일이 벌어질까요?
바둑판은 가로 19칸, 세로 19칸으로 총 361칸을 가지고 있습니다. 알파고가 게임에서 이기기 위해 두어야 할 첫 돌의 위치는 어디일까요?
이때 Brute Force 방식을 사용하려면 모든 경우의 수를 계산해야 하므로 360 x 359 x ... x 2 x 1로 360!이 나옵니다. 360!은 엄청 큰 수입니다.
겨우 첫 번째 돌 하나를 놓아야 할 뿐인데 엄청나게 많은 경우의 수를 고려해야 한다는 것이죠. 아무리 좋은 슈퍼컴퓨터라 하더라도 이렇게 많은 경우의 수를 계산해서는 절대 이세돌 9단을 이길 수 없습니다.
그럼에도 우리가 Brute Force 방식을 알아야 하는 이유는 뭘까요?
Brute Force의 장점은 직관적이고 명확하다는 것입니다. 따라서 코드를 구현하기도 매우 쉽습니다. 또한, 답을 확실하게 찾을 수 있다는 장점도 있죠.
이렇듯 나름의 장점이 있기 때문에 인풋의 크기가 작은 편이면 굳이 더 효율적인 알고리즘을 찾을 필요 없이 Brute Force를 활용해 보는 것도 나쁘지 않습니다.
단, 인풋의 크기가 크다면 이 방식은 과감히 버려야 합니다. 시간이 매우 오래 걸리기 때문이죠. 이에 따라 결국에는 효율적인 알고리즘을 찾게 되는데요.
그럼에도 효율적인 알고리즘의 첫 시작은 Brute Force 방식입니다. Brute Force 방식으로 생각해보고 거기서부터 발전을 시키는 것이죠. 그렇기 때문에 Brute Force 방식을 이해하는 것은 필수적입니다.
알고리즘 패러다임 첫 번째 시간! 어떠셨나요? 모든 경우의 수를 도출하는 Brute Force는 우리가 가장 쉽게 생각해볼 수 있는 방법입니다.
다음 시간에는 조금 더 효율적으로 문제를 해결할 수 있는 다양한 알고리즘 패러다임을 만나보도록 합시다.
* 이 자료는 CODEIT의 '알고리즘의 정석' 강의를 기반으로 작성되었습니다.