알고리즘(Algorithm)

알고리즘이라는 말을 들어보셨나요? 개발 공부를 하다보면 한번쯤 들을 수 밖에 없는 알고리즘! 그만큼 알고리즘은 개발 분야에서 정말 중요한 개념입니다. 이번 시간부터는 알고리즘에 대해 함께 배워보도록 합시다.

🎼 알고리즘의 정의

그런데 알고리즘은 정확히 어떤 걸 말하는 걸까요? 알고리즘의 사전적 정의는 문제를 해결하기 위한 절차, 방법, 명령어들의 집합이라고 합니다. 쉽게 말하자면 어떤 문제를 해결하기 위한 방법을 알고리즘이라고 합니다.

예를 들어, 계란 후라이를 조리하는 경우를 생각해봅시다.

1. 냉장고에서 계란 꺼내오기
2. 가스렌지 불 올리기
3. 프라이팬에 기름 두르기
4. 계란 깨뜨리기
5. 계란이 익으면 뒤집개로 건지기
6. 그릇에 담기
7. 맛있게 먹기 🤤

위 사례에서 우리가 해결하고 싶은 문제는 계란 후라이를 조리하는 것이고 위의 절차가 바로 알고리즘이라고 할 수 있습니다.

❗ 좋은 알고리즘

그런데 이때, 누군가는 계란에 소금을 뿌려야 한다고 할 수 있고 다른 누군가는 계란을 완전히 익혀 완숙을 먹고 싶다고 할 수도 있습니다.

계란 후라이를 먹고 싶다는 목적은 모두 같은데 방법에 있어 사람마다 차이가 있습니다. 이처럼 같은 문제를 두고도 알고리즘은 여러가지로 나올 수 있습니다.

그러나 단순함을 가장 좋은 가치로 둔다면 계란 후라이를 조리하는 방법은 위 절차를 따를 때 가장 효율적일 것 같습니다. 이와 같이 다양한 알고리즘이 존재하더라도 좋은 알고리즘은 따로 있습니다. 그렇다면 좋은 알고리즘이란, 어떤 것을 말할까요?

좋은 알고리즘은 두 가지 조건을 충족해야 합니다.

1. 문제를 해결한다
2. 문제를 더 잘 해결한다

2번은 그렇다치고 1번 조건은 왜 있는 걸까요? 알고리즘 자체가 문제를 해결하기 위해 존재하는 것이기 때문에 문제를 해결할 수 있어야 한다는 조건은 당연히 있어야 합니다.

생각해보세요. 계란을 깨야 계란을 조리할 수 있는데 깨뜨리지 않은 계란을 프라이펜 위에 놓을 수는 없죠. 🤣🤣🤣 그렇기 때문에 1번 조건은 무조건 충족해야 합니다.

2번 조건도 한 번 볼까요? 계란 조리에 필요한 기름은 계란이 올라오는 범위 정도만 필요한데 튀김을 조리할 때처럼 프라이팬 가득 기름을 부으면 어떻게 될까요? 조리야 되겠지만(?) 매우 비효율적입니다.

그렇기 때문에 좋은 알고리즘은 문제를 해결할 수 있어야 하고 동시에 더 잘 해결할 수 있어야 한다는 것입니다.

❗ 컴퓨터 알고리즘

그럼 이제 컴퓨터에 필요한 알고리즘을 생각해봅시다. 컴퓨터 알고리즘이란, 컴퓨터가 문제를 해결할 수 있도록 컴퓨터가 이해할 수 있는 방식으로 정리된 해결 방법을 말합니다.

'정렬'을 예로 들어 봅시다. 리스트에 무작위로 배치된 수들을 오름차순으로 배열하고 싶을 때 알고리즘이 필요합니다.

[7, 5, 2, 9, 8, 4]
[2, 4, 5, 7, 8, 9] # 정렬

우리가 해야할 일은 컴퓨터가 정렬을 수행할 수 있도록 컴퓨터가 이해하기 쉬운 설명서를 만들어주는 것입니다. 이 과정이 바로 알고리즘을 설계하는 것입니다. 따라서, 프로그래밍과 알고리즘은 아주 밀접한 관계를 맺고 있죠.

🎼 알고리즘의 중요성

그렇다면 알고리즘이 중요한 이유는 뭘까요? 좋은 알고리즘이 추구하는 가치는 문제를 효율적으로 해결하는 것입니다.

개발의 진입장벽이 낮아지면서 많은 소프트웨어들이 시중에 출시되고 있습니다. 이에 따라 소프트웨어들은 차별성이라는 문제에 직면했습니다. 누구라도 출시할 수 있는 프로그램은 시장 가치가 떨어집니다. 현대의 소비자들은 보다 더 효율적인 서비스를 원하기 때문입니다.

이러한 흐름을 기반으로 기술적으로 잘 구현된 즉, 좋은 알고리즘을 통해 구현된 서비스를 개발하는 것이 개발자들 사이에서 새로운 목표로 떠오르게 된 것이죠.

넷플릭스와 와챠 같은 서비스가 인기를 얻는 이유는 뭘까요? DVD와 영화관을 통해 영화를 보던 예전과 다르게 우리는 이러한 서비스들이 추천해주는 영화를 골라볼 수 있게 되었습니다.

때로는 취향에 맞는 영화들을 잘 골라줘서 깜짝 놀랄 때가 많은데요. 이는 추천 알고리즘이 잘 구현되어 있기 때문입니다. 추천 알고리즘은 단순히 평점 순이 아니라 개인이 선호하는 영화 데이터를 수집하고 그에 맞춰 영화를 추천해줍니다.

이처럼 좋은 알고리즘은 세상의 트렌드를 바꾸기도 합니다. 이제 사람들은 보고 싶은 영화를 검색해볼 필요도 없이 사이트가 추천해주는 영화를 편하게 골라서 시청할 수 있게 되었으니 말입니다. 영화 말고도 알고리즘은 현대 산업의 모든 분야에서 활약하고 있습니다.

🎼 알고리즘과 개발자

❗ 개발자들의 기본 소양, 알고리즘

성공한 개발자들은 하나 같이 입 모아 알고리즘의 중요성을 강조하십니다. 그만큼 알고리즘은 개발자에게 중요한 역량인데요. 유능한 개발자들은 알고리즘적 사고력을 갖추고 있고 대표적인 알고리즘은 거의 다 꿰고 있습니다.

개발자가 되면 이런 식의 대화를 많이 듣게 될텐데요.

"Devide and Conquer 방식을 활용해보자"

"DFS 알고리즘을 쓰면 되겠네"

마치 의사들이 의학 용어로 대화를 주고 받는 것 같네요. 알고리즘에 대해 잘 모른다면 대화가 거의 불가능할 것 같습니다.

❗ 알고리즘 = 개발자의 실력

소통의 문제를 떠나고서라도 알고리즘은 결과물에 미치는 영향이 매우 큽니다.

좋은 알고리즘으로 구현된 프로그램은 빠르게 동작합니다. 이는 속도를 중요시하는 현대인들에게 어필할 수 있는 좋은 무기이기도 하죠. 알고리즘에 빠삭한 개발자들은 좋은 프로그램을 내놓습니다.

이 때문에 많은 경우 알고리즘을 개발자의 실력과 동일시하는 경향이 있습니다. 따라서, Google, Amazon, Facebook과 같은 대기업들과 더불어 많은 기업에서는 개발자를 뽑을 때 알고리즘 테스트를 진행합니다.

특히 대기업에서는 개발 경험이 상대적으로 부족한 신입들의 경우에 일단 알고리즘 테스트를 통해 좋은 알고리즘을 설계할 수 있다는 것을 증명하면 개발 실력은 추가적인 교육을 통해 키울 수 있다고 생각하는 경향이 있습니다.

이 말은 거꾸로 하면 개발 경력이 많더라도 좋은 알고리즘을 설계하지 못하면 그만큼 대우를 못받는다는 이야기가 됩니다.

따라서, 대기업 취업을 목표로 하고 있다면 알고리즘 공부는 필수적이겠죠?

🎼 알고리즘 공부 팁

알고리즘은 사고력을 요하는 과목입니다. 그만큼 정보 습득보다는 스스로 문제를 해결하는 과정에 초점을 두고 공부를 해야 하는데요.

처음 재귀 함수와 같은 어려운 개념에 맞닥뜨리면 절망하는 친구들이 많습니다. 하지만 재귀적 사고력은 다양한 알고리즘을 공부하기 위해 필수적으로 익혀야 합니다.

많은 생각이 필요한 챕터입니다. 문제 하나하나를 풀 때마다 많은 시간이 소요될 것입니다. 그럼에도 고민하는 시간은 여러분들의 자산이 될 것입니다. 어려운 문제를 풀었을 때, 느꼈던 희열을 기억하시나요? 너무 쉽게 포기하면 그러한 희열을 느낄 수 있는 기회를 저버리는 셈입니다.

Python 챕터에서 프로젝트를 처음 맞닥뜨렸을 때, 당황했던 기억이 납니다. 그러나 필요한 함수와 절차를 정리하고 하나씩 논리적인 틀을 잡고 나니 하나의 프로젝트를 완성할 수 있었습니다.

알고리즘적 사고 또한 이와 같은 단계적 사고라고 생각합니다. 일단 숲을 보지 말고 나무를 봅시다. 나무들 간의 유기적인 관계를 통해 어떻게 숲이 만들어졌는지를 함께 보는 겁니다.

대표적인 알고리즘의 경우 개념부터 알아가곤 합니다. 이때, 멀찍이 구경만 하지 마시고 어떻게 해서 논리가 그런 식으로 흘러가는지 한 문장 한 문장 깊은 고민과 생각을 해보시길 바랍니다. 수학 문제를 풀 때처럼 이해를 바탕으로 원리를 깨우쳐야 합니다.

챕터를 마무리 하기 전에 문제 하나를 함께 풀어 봅시다.

❗ 실습 과제. 팔린드롬

팔린드롬(palindrome)을 아시나요? '기러기'와 '토마토'처럼 거꾸로 해도 똑같은 단어들이 있습니다. 그러한 단어들을 팔린드롬이라고 합니다.

이제 우리가 맞닥뜨린 문제는 컴퓨터가 팔린드롬 단어를 분간하도록 가르쳐야 하는 것입니다. 컴퓨터가 이해할 수 있도록 설명서를 만들어줘야 겠죠?

is_palindrome 함수는 파라미터로 문자열 word를 받아서 이 문자열이 팔린드롬인지 확인합니다. 만약 팔린드롬이 맞다면 True를, 틀리다면 False를 리턴합니다.

여기서 잠깐! 코드를 작성하기 전 주의사항을 참고하시길 바랍니다. 주의사항을 제시하는 이유는 프로그램에 기본으로 내장된 함수의 사용을 방지하기 위함입니다. 그렇게 해야 알고리즘 실력이 늘 수 있겠죠?

1. for문을 사용할 것
2. append, insert 메소드와 del 함수 등을 사용하지 말 것

자, 지금부터 차례대로 한 줄씩 설명서를 작성해보도록 하죠.

우선, 함수를 정의합시다.

def is_palindrome(word):

다음으로 for문을 작성해야 하는데요. 그 전에 먼저 필요한 변수를 생각해봅시다. 어떻게 하면 word라는 문자열이 팔린드롬인지 확인할 수 있을까요? 먼저, 맨 첫 글자와 맨 끝 글자를 비교해야 할 것입니다. 그 다음에는 그 앞 글자와 그 뒷 글자, 이런 식으로 반복을 해야겠죠?

그럼 첫 글자와 끝 글자를 담을 변수들이 필요하겠네요. 저는 각각 left와 right로 정의해보겠습니다. 그런데, right라는 변수는 사실 left를 활용해서 표현이 가능합니다.

right라는 것은 무엇일까요? 맨 끝 글자죠? 맨 끝 글자는 코드로 어떻게 표현할 수 있을까요? 우선 문자열의 개수를 재야 합니다. 문자열의 개수는 문자열의 길이와 같습니다. 인덱스로 따지면 문자열 개수에서 1을 뺀 인덱스의 값이 바로 문자열의 끝 값을 뜻합니다. 'len(word) - 1' 이런 식으로 문자열 끝의 인덱스를 구할 수 있습니다.

하지만 for문은 문자열의 처음부터 끝까지 차례로 돕니다. 따라서, 두번째 글자와 비교할 두번째로 끝에 위치한 값은 'len(word) - 1'로 구할 수 없습니다. 인덱스가 바뀜에 따라 값도 함께 바뀌어야 하기 때문이죠. 이때 필요한 것은 left입니다. 'len(word) - 1'에서 left 인덱스를 추가적으로 빼주면 right 인덱스가 나옵니다.

정리하자면, right는 일반적으로 'len(word) - 1 - left'로 표현이 가능합니다.

이제 for문을 사용해서 left 인덱스가 word 문자열의 길이만큼 도는 동안 문자열을 비교할 수 있습니다. 따라서, for문의 첫 머리는 이렇게 작성해볼 수 있겠네요.

for left in range(len(word)):

그런데 사실 for문이 word의 길이만큼 돌 필요가 없습니다. 중간을 기준으로 앞뒤 값만을 비교하기 때문에 문자열의 절반만 돌아도 되는 것이죠. 만약 끝까지 다 돈다면 결국에는 처음 문자열과 같은 문자열이 되버립니다. 따라서 이렇게 코드를 수정해줍시다.

for left in range(len(word)//2):

자, 지금부터는 for문이 돌아가면서 수행해야 할 반복 작업들을 생각해봐야 합니다. 팔린드롬의 핵심은 앞 글자와 뒷 글자가 같은지 비교하는 것입니다. 따라서, for문이 돌 때마다 left 인덱스 값에는 right 인덱스의 값을 넣고 right 인덱스 값에는 left 인덱스 값을 넣어본 후 두 값이 같은 지를 확인해 보면 됩니다. 그럼 이런 식으로 표현이 가능하겠죠?

left = right
right = left

그런데 잠깐, 여기서 right의 값이 left에 들어감으로써 원래 left가 가지고 있던 값이 사라졌습니다. 그럼 다음 줄에서 원래 의도했던 대로와는 달리 바뀐 left 값이 right 값에 들어가게 됩니다. 이를 방지하려면 어떻게 해야할까요? temp라는 임시 변수를 추가해줘야 합니다.

temp = left
left = right
right = temp

이렇게 하면 기존의 left값이 temp에 저장되어 결과적으로는 right에 temp값을 넣음으로써 의도했던 대로 두 값이 reverse 됩니다.

이제 이 자리를 바꾼 두 값이 같은지를 확인하면 됩니다. 만약 두 값이 같으면 for문은 계속 돌지만 같지 않은 경우에는 바로 False를 리턴해야 합니다. 이를 코드로 표현해보면 다음과 같습니다.

if word[left] != word[right]
    return False

이제 모든 과정을 하나로 합쳐봅시다.

def is_palindrome(word):
    
    for left in range(len(word)//2):
        right = len(word) - left - 1

        temp = left
        left = right
        right = temp

        if word[left] != word[right]:
            return False

그런데 이 코드를 돌려보면 True가 나와야 할 곳에 None이 나오게 됩니다. 왜 그런 걸까요? return은 반환할 값이 없을 때, None을 대신 출력합니다. 위 코드에서 두 값이 다를 때는 False를 리턴한다는 조건은 있지만 True에 대해서는 아무 명령어를 주지 않았습니다. 따라서, for문을 모두 돌아도 False가 나오지 않으면 True를 반환하는 return True라는 명령어를 추가해주어야 합니다.

def is_palindrome(word):
    
    for left in range(len(word)//2):
        right = len(word) - left - 1

        temp = left
        left = right
        right = temp

        if word[left] != word[right]:
            return False
    
    return True

이로써 팔린드롬을 확인하는 함수 is_palindrome이 완성되었습니다.

해설이 매우 길었지만 이런 식으로 한 줄 한 줄 논리를 생각하며 코드를 작성해야 합니다. 이러한 과정이 바로 알고리즘을 익히는 방법입니다.

* 이 자료는 CODEIT의 '알고리즘의 정석' 강의를 기반으로 작성되었습니다.