코딩 인터뷰 완전 정복 책 정리 #2

최근에 코딩 인터뷰 완전분석이라는 책으로 이직을 준비하고 있습니다.

 

흔히 면접을 할 때, 어떤것을 준비해야할 지 모르는 경우가 많습니다. 그래서 무작정 인터뷰를 해봐라 라는 조언을 받습니다.

이건 정말 사실 입니다. 직접 면접의 분위기를 알고, 질문에 대해 대답을 해보는 연습은 매우 중요합니다.

 

그렇지만, 다양한 면접 상황을 실제 면접으로만 경험치를 쌓기에는 무리가 있기 때문에, 책을 통해 간접적인 경험을 얻는 것은 유용하다고 할 수 있습니다.

 

저는 코딩 인터뷰 완전 정복이라는 책을 통해 코딩 인터뷰를 학습해보았습니다.

간략하게 정리하기 때문에, 예시와 사례는 자세히 표시하지 않겠습니다. 만약, 필요하다면 책을 구매하셔서 자세히 보시면 도움이 될 것같습니다.

책이 800페이지가 넘는 분량이기 때문에, 저를 위해서라도 요약이 필요해보였습니다.

 

 

코딩 인터뷰 완전분석 이라는 책을 읽으면서 후기를 작성하고 있습니다. 제가 기억하는 것 저에게 와닿는 것으로 정리가 되기 때문에

책의 모든 내용을 다루지는 않습니다. 그리고 책의 내용을은 그대로 작성하기 보다는 저의 경험과 후기를 작성한다고 보시면 됩니다.

 두 번째 정리 내용으로 big O에 대해 얘기할텐데 위에서 언급한 것처럼 책의 목차의 범위와 제가 작성하는 글의 단위는 일치하지 않습니다.

어쨋든 big O에 대해서 말씀을 드리겠습니다. big O는 복잡도를 나타냅니다. 컴퓨터 전공을 하셨다면 흔히 들은 내용이고 대략적이라도 아실 겁니다.

이 복잡도에는 두 가지 측면이 있고 그것은 시간 복잡도 공간 복잡도 입니다. 

 만약 알고리즘을 작성하거나 작성된 알고리즘을 통해 그 복잡도를 구할 수 있어야 합니다. 예전에는 메모리가 적어서 공간 복잡도를 고민했지만,

현대적으로는 시간 복잡도가 중요한 상황이 더 많아졌습니다. 그래서 시간 복잡도, 공간 복잡도 처럼 별도로 지정하지 않을 때 복잡도는 보통은 시간 복잡도라고 생각하시면 됩니다.

 정렬이라는 알고리즘은 O(N logN) 정도, 이진 탐색이 O(log N) 이런식으로 외우고 있는 경우가 있습니다. 이러한 내용을 외우는 이유는 코딩 질문중에 흔히 나오기 때문입니다. 그래서 이러한 답이 질문과 동시에 대답을 하게 됩니다. 외운 것이기 때문입니다. 이러한 상황이 면접에서 어떠한 평가고 내릴 수 없다고 합니다.

 책에서 면접 질문의 의도는 이 내용은 기본 지식이니 당연히 외우고 있어야지가 아니라 복잡도라는 개념을 알고 알고리즘의 복잡도를 추론할 수 있냐는 것 입니다.

이미 알고 있다면 대답할 수 있겠지만, 모른다면 대략적인 수도 코드를 작성한 후에 알고리즘의 복잡도를 그 자리에서 추론 해보는 것도 좋은 자세입니다. 어떤 문제에 대해 논리적으로 대답하는 과정을 보여줄 수 있기 때문에 평가에 도움이 된다고 할 수 있습니다. 

우리가 다루는 대부분의 문제영역은 O(루트 N), O(log N), O(N), O(N logN), O(N^2), O(2^N), O(N!)  입니다. 이러한 복잡도를 가지는 알고리즘은 현실 문제 그리고 수학 문제에서 흔합니다. 최소 이러한 복잡도를 가지는 알고리즘의 예시는 기억해두면 좋습니다. 특히 재귀적 알고리즘을 사용하면 다양한 복잡도를 가질 수 있다는 점을 미리 알고 학습하시면 좋을 것 같습니다.
 

 O, Ω, Θ에 대한 오해

책에서는 흔히 컴퓨터 공학에서 사용하는 O, Ω, Θ와 원래의 의미가 다른 점을 설명합니다. 궁금하면 따로 찾아보시면 좋을 것 같습니다.

 

우리가 문제해결 능력을 키우기 위해서 다음의 내용을 명심해야 합니다.

1. 직접 풀도록 노력하라.
2. 코드를 종이에 적으라.
3. 코드를 테스트하라.
4. 종이에 적은 코드를 그대로 컴퓨터로 옮긴 뒤 실제로 실행해 보라.

 

 

그리고 책에서 면접 질문을 받고 풀 때의 절차를 설명합니다. 면접에서 굉장히 복잡한 알고리즘을 물어보지는 않지만, 또 너무 간단하지도 않는 문제를 주기 때문에 

전략을 가지고 문제를 접근하면 도움이 됩니다.

 

책에서는 다음의 전략을 소개합니다

 

1. 듣기 - 문제를 놓치지 말고 조건들을 듣습니다. 문제 중에는 힌트가 있을 수 있습니다. 예를 들면 정렬된 숫자를 준다 입니다.
2. 예제 샘플 데이터 만들기 - 흔히 데이터가 어떤 이진 트리의 데이터일 때 너무 적은 노드만 있는 예제 샘플을 생각한다고 합니다. 우리가 생각하는 것보다 2배로 하라고 조언을 합니다.
3. 무식하게 풀기 - 일단 알고리즘의 효율성을 무시한 채 문제를 있는 그대로 풉니다. 여기서 푼다는 것은 코드 작성이 아니라 의사코드 작성입니다.
4. 최적화 - 의사코드를 작성했으면 최적화 검토를 합니다. 여기서는 BUD 최적화를 하라고 합니다.
5. 검토하기 - 정리된 의사코드를 다시 보고 문제를 해결하는데 놓친게 없는지 검토합니다. 또는 극단적인 입력에 대해서도 생각할 필요가 있습니다.
6. 구현하기 - 이제 코드를 통해 작성을 합니다.
7. 테스트 - 의도된 결과를 내는지 테스트 합니다.