알고리즘 인터뷰 공부 방법입니다
알고리즘(algorithm) 인터뷰는 알고리즘 문제를 한 시간 내에 한두 문제를 풀어야 합니다. 이 인터뷰에서 목적하는 바는 이 사람이 소프트웨어 엔지니어로서 문제를 정의하고, 알고리즘을 생각하고, 코딩에 큰 문제가 없고, 소통하는데 문제가 없는가 확인하는 것입니다. 실제 회사 일을 짧은 시간에 시켜볼 수는 없으니, 한 시간 내에 풀 수 있는 작은 문제를 주고 문제를 잘 푸는지 작은 시뮬레이션을 해보는 거라고 보시면 됩니다.
그럼 쉬운 알고리즘 문제를 예로 한 번 인터뷰 보는 식으로 문제를 풀어 보겠습니다.
단어 중에서 앞에서 읽으나 뒤에서 읽으나 똑같은 단어를 회문(palindrome)이라고 합니다. 예를 들어서, "aba", "abba"는 palindrome입니다. "abc", "ab"는 palindrome이 아닙니다. 단어를 입력받고 이게 palindrome인지 아닌지 참/거짓으로 구별하는 알고리즘을 만들어보시오.
1. 먼저 인터뷰어와 질문과 답변을 하면서 문제를 이해합니다. 인터뷰 문제는 일부로 문제를 100% 명확하게 주지 않습니다. 그래서 자신이 받은 빈틈이 있는 문제에서 여러 경우의 수를 따지며 스스로 빈틈을 메꿔야 합니다.
(1) 위 문제에서는 입력된 단어가 빈 문자 ""면 어떻게 처리할지
(2) 입력되는 문자는 영어 소문자만인지
(3) 단어의 길이가 최대 얼마까지 길어질 수 있는지 등을 미리 물어볼 수 있습니다.
실제 회사 일을 하다 보면 100% 명확한 요구사항을 받는 일은 없습니다. 약간 두리뭉실한데, 이걸 명확하게 하는 과정을 스스로 할 수 있는가 보려는 것입니다. 이런 걸 안 따지고 바로 코딩으로 들어가면, 이 사람은 불명확한 요구사항을 가지고 코딩을 하려고 하겠구나 해서 red signal이라고 안 좋은 신호로 봅니다.
2. 알고리즘을 글로 간략하게 쓰면서 생각합니다. 알고리즘을 가볍게 써 보면서 내가 생각한 게 동작하는지 확인하는 과정을 거쳐야 합니다. 알고리즘을 글로 써 보면 아래 같이 쓸 수 있습니다. 이런 글을 Pseudo-code라고 합니다.
(1) 입력된 문자에서 앞에서부터 한 글자를 읽고
(2) 뒤에서부터 한 글자를 읽고
(3) 두 글자가 다르면 회문이 아니므로 거짓(false) 결과 전달
(4) 두 글자 비교를 단어 중간에 도착할 때까지 1~3 과정을 반복
(5) 모든 글자를 다 봤는데 다른 글자가 없으면 회문이므로 참(true) 결과 전달
3. 그리고 여기에 걸리는 시간 복잡도(time complextiy)와 공간 복잡도(space complexity)를 계산합니다. 말이 어려운데, 결국 이 알고리즘이 얼마나 오래 걸릴까, 얼마나 많은 메모리를 사용할까 추측하는 것입니다. 알고리즘이 너무 오래 걸릴 걸로 추측되면 다른 알고리즘을 생각해야 합니다. 몇 가지 알고리즘이 나오면 그중에서 가장 시간 복잡도와 공간 복잡도가 나은 알고리즘을 선택합니다. 이때까지도 코딩은 하지 않습니다.
4. 위 모든 과정에서 인터뷰어와 서로 소통해야 합니다. 조용히 하고 있으면, 인터뷰어 입장에서는 뭘 생각하고 있는지 알 수가 없고, 도와주고 싶어도 도와줄 수가 없습니다. 아래 같은 말들을 할 수 있습니다.
(1) 제가 지금 생각하는 건 이겁니다.
(2) 이거 어떻게 생각하나시요?
(3) 이걸로 해도 될까?
5. 인터뷰어도 지금 알고리즘으로 코딩해도 좋다고 하면 이제 코딩을 시작합니다.
(1) 코딩의 시작은 어떤 함수를 만들지입니다. 이런 식으로 만들 거다 하고 함수에 이름을 지어주고, 입력과 출력을 설정합니다. 일종의 껍데기를 만듭니다.
def isPalindrome(word: str) -> bool:
return False
(2) 함수 만들자마자 생각했던 알고리즘으로 바로 코딩하는 사람들이 있는데, 전 그러지 말고 여러 경우의 수를 따져서 테스트부터 만들기를 권합니다. 여기서는 쉽게 출력을 통해서 이 함수가 정상적으로 동작하는지 확인해 봅니다. "a"는 palindrome이니까 True가 나와야 해. "ab"는 palindrome이 아니니까 False가 나와야 해 하는 식으로 명시적으로 코드가 코드를 테스트합니다. 이를 테스트 주도 개발 또는 TDD(Test Driven Development)라고도 합니다.
def isPalindrome(word: str) -> bool:
return False
print(isPalindrome("")) # True
print(isPalindrome("a")) # True
print(isPalindrome("aba")) # True
print(isPalindrome("abba")) # True
print(isPalindrome("ab")) # False
print(isPalindrome("abc")) # False
이때 실행하면 모두 False라고 나옵니다.
False
False
False
False
False
False
(3) 이제 본격적으로 알고리즘을 코딩합니다. 지금 글은 프로그래밍 글이 아니므로, 코딩으로 잘 옮겼다고 치겠습니다. 위 알고리즘을 코드로 변경하면 아래와 같습니다.
def isPalindrome(word: str) -> bool:
l, r = 0, len(word) - 1
while l < r:
if word[l] != word[r]:
return False
l += 1
r -= 1
return True
print(isPalindrome("")) # True
print(isPalindrome("a")) # True
print(isPalindrome("aba")) # True
print(isPalindrome("abba")) # True
print(isPalindrome("ab")) # False
print(isPalindrome("abc")) # False
6. 실행해서 원하던 기댓값이 나오는지 확인합니다. 위 코드를 실행하면 이제 기대했던 값 대로 나옵니다. 여기서 기대했던 값이 안 나온다면, 코드를 차근차근 다시 보면서 실수한 게 없나 고치는 과정, 디버깅을 합니다.
True
True
True
True
False
False
7. 혹시라도 어디라도 오랫동안 막히는 부분이 있으면 인터뷰어와 이야기하면서 힌트를 얻으려고 노력합니다. 5분 이상 어느 한 곳에서 막혀 있다면, 인터뷰어에게 현재 막힌 곳을 잘 설명하면서, 도움을 요청할 수도 있습니다. 아무 때나 계속 도움을 요청하는 것은 당연히 안 되지만, 한두 번 정도는 도움을 요청할 수도 있습니다. 한데 이때 힌트를 받고도, 힌트를 잘 못 받거나, 무시하면 오히려 감점의 대상이 되기도 합니다. 입사해서 동료와의 일을 그렇게 할 수도 있다고 보기 때문입니다.
(1) 여기가 문제인데, 어떻게 하면 좋을까요?
(2) 이 부분에서 막혀있습니다. 조언을 해주실 수 있을까요?
8. 마지막으로 코드를 최대한 깔끔하게 만듭니다. 테스트를 통과했다고 끝났다고 손 놓지 말고, 시간이 조금 남는 다면, 코드 가독성에 문제가 없는지, 중복된 코드나 줄일 수 있는 코드가 없는지 확인하면서 깔끔하게 만듭니다. 이런 세심함이 인터뷰어 입장에서는 나중에 회사 들어와서도 깔끔하게 코드를 만들겠구나 하고 상상하게 만듭니다.
이런 알고리즘 문제는 어디에서 보면 되냐면 leetcode를 사용하길 권합니다. 외국계를 지원하거나, 외국계를 지원하지 않아도 알고리즘 문제 풀이는 이곳이 가장 좋다고 생각합니다.
영어로 문제가 나오니 진입 장벽이 약간 있지만 영어가 엄청 어려운 것도 아니고 영어 공부도 하는 셈 치고, 이미 실리콘 밸리의 많은 엔지니어들이 이곳에서 연습하므로 다른 곳으로 안 가셔도 됩니다.
그리고 막상 갔는데 이곳에 알고리즘 문제만 3500개쯤 있으므로 뭐부터 풀어야 할지 모를 수 있습니다. 그래서 먼저 알고리즘 인터뷰에 자주 나온 문제 150개를 추린 것부터 시작하길 권합니다. 여기 150문제를 큰 막힘 없이 풀 수준이면 실리콘 밸리 테크 회사들에 인터뷰 볼만한 기본 실력은 되는 것입니다.
https://leetcode.com/studyplan/top-interview-150/
150문제를 다 푼 이후에는 인터뷰 볼 회사 또는 가고 싶은 회사에 맞추어서 문제를 푸셔도 되고, 자기가 부족한 영역이 있으면 그쪽 문제를 집중적으로 풀어도 됩니다.
마지막으로, 150문제나 되는데 언제 푸나 싶고, 혼자 하다 보면 몇 문제 풀다가 포기하는 경우가 많습니다. 이럴 때 혼자 하지 마시고, 스터디 커뮤니티, 스터디 클럽++에서 공부하시면 딱 좋습니다.
스터디 클럽++ 소개글: https://brunch.co.kr/@jaedong/7