Algorithm 을 왜 공부해야 할까?

"들어가기 앞서 이 글은 취준 / 면접시 알고리즘을 봐야 하나? 라는 토픽과는 전혀 무관하다. 난 단순히 엔지니어링 측면에서 알고리즘의 중요성에 대한 내 생각을 적어보려고 한다"

최근 알고리즘 문제 풀이에 재미를 느끼고 있는데 Leetcode 문제 풀이를 하던 중, 여러 배열의 문자들의 combination 을 어떻게 구성해야 할까? 라는 고민이 생겼다. 예를 들면 아래와 같은 상황이라고 가정해보자. 

이 아티클에서 구현 Level 의 언어는 Python 을 이용하려고 한다. Kotlin 으로 구현해버리면, Kotlin 을 모르는 사람은 알기 힘든 경우도 종종 있어서, 내 생각에 psuedo code 에 비슷하게 구현가능 한 언어인 Python 을 선택했다.

위와 같은 상황에서 a 와 b 배열을 한단어씩 조합해서 가능한 Combination 을 뽑아보면 아래와 같은 결과가 나올 것 이다.

[ad, ae, af, bd, be, bf, cd, ce, cf]

이걸 코드로 작성하면 어떻게 작성해야 할까? 이 두개의 배열에서 Combination 을 뽑아내는 건 아주 쉬운 일이다. 

가장 Simple 한 Solution 은 이중 for-loop 를 통해서 한가지씩 조합을 대조해보면 될것이다.

코드는 위와 같고, 결과 값도 우리가 원하는 대로 잘 출력되는 것을 확인할 수 있다.

여기까지는 내 기준에서는 조금 쉽다고 생각되고, 이중 for-loop 만 안다면 머릿속으로 그려볼 수 있다고 생각한다.

그런데 여기서 아래와 같은 한가지 변경점이 하나 생긴다고 해보자.

현재는 2개의 배열에 대한 조합을 구하는데 그쳤지만, 앞으로는 N 개의 배열에 대한 조합이 올거에요. 

이제 우리는 어떻게 대응해야 할까? 배열의 갯수만큼 for-loop 를 돌려야 하나? 근데 몇개가 올줄알고 코드에 적어두지? 등등의 머릿속이 고민들로 복잡해 질 것이다. 우리는 이 요구사항을 어떻게 대응하는 것이 좋을까?

Change Solution

보통 이렇게 Brute-force 에서 벗어나서 다른 방법으로 대응해야 하는 경우에는 나는 이 상황에 어울리는 Data Structure 가 있는지 확인해보는 편이다. 예를 들어 3개로 배열을 늘린뒤 Tree 구조로 한번 어떻게 풀 수 있을지 생각해보자.

Tree 구조를 생각하면 위와 같이 풀이 할 수 있을 것이다. 첫번째 Root Node 에는 파란색 배열의 단어들을 순차적으로 넣어주면 되고, 각 노드들을 DFS 방식으로 따라가면서 단어들을 조립하면 될 것 같아보인다. 

우리는 이로써 한가지 풀이 방식을 찾아냈다. DFS 풀이 방식은 아마도 아래와 같은 절차를 따를 것 이다.

1. Stack 에 빈문자열을 넣는다. (시작하기 위해서 하는 일종의 Initialize 작업임, 진짜 알고리즘은 아래부터)
2. Stack 에서 문자열을 꺼낸뒤, 문자열의 길이로 어떤 배열을 사용해야 하는지 계산한다. (위의 예시라면, 파란/초록/빨강 배열중 하나를 사용해야 하는 경우를 계산하는 것이다.)
3. 다음 Stack 에 이전 문자열 + 현재 문자열을 더해서 넣어준다.
4. 만약 max_height (최대 깊이) 에 도달했다면 Loop 를 탈출한다.

코드는 어떻게 구성될까? 아마도 아래와 같이 구성될 것이다.

일단 우리는 문제를 해결하는데 성공했다. 배열이 몇개가 오던지 간에 Combination 을 만들 수 있게 된 것이다. 

이렇게 됬을때 시간복잡도를 간단하게 계산해 본다면 N(input) ^ N(input) 이 나오게 될 것이다. 따라서 이 알고리즘으로 수행하는 input 값의 수를 일정이상 제한하는 것이 좋을 것 이다. 우리는 일단 DFS 솔루션으로 이 문제를 해결하는데 성공했다.

만약 위의 상황에서 출력의 sorted 를 제거하려면 어떻게 해야할까?

간단하다. 지금은 stack 을 사용하고 있는데 queue 를 이용하는 방식으로 바꿔주기만 하면된다.

다른 Solution

위의 Solution 은 또 어떻게 풀어볼 수 있을까? 뭐 BackTracking Algorithm 을 이용해서도 충분히 풀이 해낼 수 있을 것 같아 보인다.

아까의 트리를 기준으로 다시한번 살펴보면 아래와 같은 Solution 을 택할 수도 있을 것이다.

자식 Node 를 방문한 뒤 유망하지 않다고 판단되면, 다시 부모 Node 를 방문하고 다른 자식 노드를 방문하는 방식을 채택할 수도 있을 것이다. 말이 어려워서 그렇지 그림으로 보면 좀 더 편할 것이다.

BackTracking 도 DFS 와 마찬가지로 Recursive 한 Algorithm 이므로 탈출조건을 명시하는게 상당히 중요하다. 

위의 그림에서 탈출조건은 무엇일까? 여기서도 마찬가지로 MaxDepth 에 도달했는지가 탈출 조건이 될 것이다.

이번에는 Stack 또는 Queue 를 사용해도 상관은 없으나, 풀이의 다양성을 위해서 Function Call 을 통해서 Recursive 하게 코드를 작성해보자.

위와 같이 알고리즘 풀이를 통한 여러가지 문제 해결 방법에 익숙해지면, 상황에 맞는 자료구조를 통해 문제를 풀이하거나 아니면 Function Call 을 통해 풀이하거나 등등 여러가지 방법으로 생각하는 것이 가능하다. 나는 알고리즘을 풀때도 한가지 방법이 아니라 여러가지 방법으로 풀어보는게 좋다고 생각하는 것이, 자신이 BFS 든 DFS 던가 상관없이 알고리즘을 제대로 이해하고 있는지 증명할 수 있는 방법이 될 수 있고, 한 문제를 여러 Solution 으로 풀어보고 시간 또는 공간복잡도를 계산해 볼 수 있을 것이다.

만약 알고리즘을 공부하지 않았다면?

위와 같은 문제를 알고리즘을 공부하지 않는 사람이 문제를 해결하는 방식을 선택한다면 어떻게 풀까? 내가 알고리즘을 공부하지 않았다고 생각했을때는 아마도 풀기 상당히 껄끄러웠을것 같고, 아래와 같은 두가지 고민을 했을거 같다. (내 기준에 나는 이렇게 했을 것 같다 😂)

1. for-loop 를 이용 (가능할까?) 
2. recursive 를 이용 (stackOverFlow 가 위험하진 않을까?) -> 근데 사실 이 방법도 알고리즘 푸는 공부를 꾸준히 하지 않았다면 사고하지 못했을 확률도 크다. (물론, 개개인의 역량 차이로 누군가는 Recursive 로 잘 생각해낼 수도 있다. 그렇지만 난 아니였을 것 같다.)
3. Google 에 검색해서 누군가 만들어준 Code Copy And Paste -> 이것도 하나의 방법이다.

3번도 부정적으로 바라보지 않는다. 모르는데 뭐 어쩔 수 있겠나..? 잘 검색해서 시간을 줄이는 것도 일종의 개발 능력치라고 본다.

알고리즘 중요한가?

난 중요하다고 생각하는 편이다. 다만 그렇다고 해서 나도 잘하는건 아니다. 최근들어 정말 열심히하고 있고 예전과는 다르게 느끼는 것들도 많다. 예를 들어 아래 Leetcode 문제와 같은 경우는 충분히 현업에서 만날 수 있는 경우다. 현업에서 이를 만나면 풀 수 있겠는가?

https://leetcode.com/problems/letter-combinations-of-a-phone-number/solution/

Letter Combinations of a Phone Number - LeetCode

아마도 실무입장으로 딱 들어와서 생각해보면 아래와 같은 절차로 대략적으로 생각할 것 같다.

1. 유저에게 번호를 입력받는다.
2. 각 "번호 : [영어 단어들]" 로 구성된 Map 을 미리 만들어둔다. 
3. 유저에게 입력받은 번호(문자열) 을 Char 배열로 만들어 우리가 조합해야 하는 영어단어들 배열을 가져온다.
4. 구글에 "How to combination in kotlin" 을 검색한다.
5. 해당 코드를 참고하여 기능을 완성한다.

 

이렇게 해결 할 수 있을 것이다. 어떻게든 문제를 풀었다는 것이 정말 중요하지만, Combination 을 모르는 사람은 이렇게 검색조차 하지 못했을 수도 있다. 그래서 나는 알고리즘을 풀면서 이러한 단어들에 친숙해지고, 시간 복잡도를 계산해서 자신의 코드가 입력값을 극도로 제한해야 하나? 라는것도 생각해보고 하는 것이 엔지니어링 측면에서 좋다고 생각한다.

 

만약 실무에서 이 코드가 불안하다면 위와 같은 상황을 부하 테스트를 통해서 직접 테스팅 해볼 수도 있을 것이다. 하지만, 불안하다고 느끼는 것 또한 자신이 시간복잡도를 계산하고 있다는 전제하일 가능성이 높다. 시간복잡도를 잘 계산하지 못한다면, input 값에 따른 비용을 계산하지 못해 input 값이 커졌을때 장애 상황을 맞이 할 수도 있다.

현업에 더 중요한게 많은데?

나도 예전에 이런말을 많이 했었고, 실제로 알고리즘에 관한 이야기를 해보면 가장 많이 듣게 되는 말 중에 하나이다. 현업에 공부할게 더 많고 알고리즘 말고도 더 중요한게 많은데? 라는 말이다. 실제로도 동의했었지만 지금은 생각이 많이 다른게 알고리즘도 똑같이 문제(Problem) 이 주어지고, 이를 자신만의 Solution 으로 풀어내는데 과연 떨어져 있으면 과연 얼마나 동떨어져 있냐는 생각이다. 다만 중요도의 차이는 있다고 생각한다. 만약 Spring 의 @Configuration 도 잘 모르면서 알고리즘을 공부하고 있으면 이건 상당히 문제가 있다고 생각한다. 밑에서도 말하겠지만 알고리즘 풀이란것 자체는 PS 능력을 증진시키기 위한 방법이라고 생각하는데, 팀에서 제대로 자신의 프레임워크도 사용하지 못하면서 "알고리즘, 알고리즘" 이렇게 말하는건 옳지 않다고 생각한다. (우선순위를 잘 생각하자.)

PS 능력의 증진

결국 나는 알고리즘을 푼다는 건 문제를 풀어내는 능력인, Problem Solving 능력치를 키우기 위해서 하는 일종의 수련이라고 생각한다. 다만 이걸 그냥 단순히 문제를 풀기위해 문제를 외우고 이렇게 되면 큰 도움이 되진 못하겠지만, 문제를 풀기위한 여러가지 Solution 을 고안해보고 어떤게 더 괜찮을지 찾아보고 정답을 결정해 나가는 과정은 현업에서 문제를 풀어나가는 과정이랑 비슷한것 같다는 생각이 많이든다.

알고리즘 공부 언어는 파이썬?

사실 어떤 언어를 고르는가는 아무런 의미가 없고, 자신이 가장 익숙한 언어가 알고리즘을 공부하기 좋다고 생각한다.

이것도 말이 많은데, 자신이 현업 혹은 공부기간에 Java 를 사용하는 사람인데, "파이썬에서는 구현을 할 수 있는데 자바로는 못하겠어요" 라는 말은 내 생각엔 그냥 "그 문제풀이를 이해를 못했어요" 라는 말과 똑같다고 생각한다. 구구단을 파이썬에서 만들라하고, 자바로 만들라고 했을때 못만들것 같은가..? 한번 다시 생각해보길 바란다. Python 에서는 Combination API 가 있어서 편한데 라고 말하기전에 Combination 을 코드로 구현할 능력이 되는가를 먼져 생각해보길 바란다.

그래서 나한테 도움이 된건?

나도 남들과 비슷하게 처음에는 알고리즘을 굳이 공부해야 하나? 의 생각을 많이 가지고 있었고, 근데 취업을 하고나서 천천히 공부를 해보면서 느낀건 특정 문제에 부딪혔을때 좀 더 다양한 사고를 할 수 있게 되서 많은 도움이 됬다고 생각한다. 그리고 시간 복잡도 / 공간 복잡도를 구하는 건 꽤나 큰 도움이 되고, 자신의 코드가 Input 값이 제어되어야 하는 상황인지 혹은 제어를 안해도 여유로운 상황인지를 계산하게 될 수도 있을 것 이다.

 

Data Structure 를 생각하게 되는 것 또한 큰데, 문제를 해결할때 가장 쉬운 방법인 주먹구구식 (Brute-force) 방법으로 풀이하고, 이를 어떤 Data Structure 를 이용해서 효율화 할 수 있을까? 를 생각하게 되면 자료구조를 사용하는 방법들을 깨닫게 되거나 알게 된다. 예를 들면, 왜 Tree 는 Recursive 한 문제를 풀이하기 좋나요? 라고 물어보면 대답할 수 있게 되는 것이다. 여하튼, 앞으로 내 Engineering 측면에서 알고리즘을 놓을 생각은 전혀없다. 올해 말까지 총 150 문제 가량을 푸는게 목표인데 꾸준히 풀어서 내년에는 구글 코드잼 이런데도 참가해보고 싶다.

말하고 싶은 것

알고리즘이 엔지니어링 기술을 증진시키는데 필요하다고는 생각하나, 이걸 꼭 해야된다는 아니기에 일단 자신이 중요한걸 잘 선택해 나갈 수 있었으면 좋겠다. 다만 말해주고 싶은건, 알고리즘을 공부하는건 쓸모없어 라고 생각하기전에 자신이 코드를 바라보는 시선이 거기까지 닿지 못하는게 아닌가? 라는 생각을 먼져했으면 좋겠다. 나도 취준기간에 알고리즘에 스트레스를 받아서 알고리즘 유사 혐오자가 됬었는데, 지금은 심적으로 여유로워져서 그런지 내 능력을 기를 수 있는 하나의 수단으로 느껴진다.

 

위에서 언급한 것처럼 알고리즘은 하나의 PS 를 기를 수 있는 수단일 뿐이지 그 프로그래머가 알고리즘을 잘하고 못하고는 현업에서 일을 잘하고 못하고와 절대 정량적으로 비례되지 않는다. 알고리즘을 잘하지만 현업에서 막상 일할때는 일을 못할 수도 있는거고, 알고리즘을 못하지만 현업에서 일을 잘할 수도 있는 것이다. 어느정도의 비례는 있겠지만, 절대 정량적으로 비교되지는 않는다.