[개발자 면접] 기술 면접 준비

 

 

기술 면접에서는 보통 알고리즘 문제를 낸다. 어려운 문제같이 보여도 논리적으로 푸는 방법이 있으니 쫄지 말자.

 

 

준비하는 방법

문제와 답지를 읽어보는 것 만으로는 알고리즘 문제를 준비할 수 없다. 직접 풀어봐야 한다. 온라인이나 책에서 찾은 문제들을 다음과 같이 접근해보자:

 

1. 문제를 직접 풀어본다. 답지를 최대한 적게 보도록 노력한다. 문제를 풀 때 시간 복잡도와 공간 복잡도를 생각하면서 푼다.

 

2. 코드를 종이에 적으면서 푼다. 코딩할 때 컴퓨터를 이용하면 문법 하이라이트, 자동완성 같은 도움을 받게 된다. 하지만 종이에 차근차근 풀어 가는 것에 익숙해지는 것이 좋다.

 

3. 코드 테스팅을 종이에 한다. 인터뷰에서는 종이에 코드를 테스트 하는 경우가 많기 때문에 연습해놓는 것이 좋다.

 

4. 종이에 쓴 코드를 컴퓨터에 그대로 적어본다. 어느 부분에 실수 했는지 잘 생각해 놓자.

 

 

공부해야 할 것들

- 자료 구조 (Data Structures):

    Linked Lists

    Trees & Graphs

    Stacks & Queues

    Heaps

    Vectors / ArrayLists

    Hash Tables

 

- 알고리즘 (Algorithms):

    Breath-First Search

    Depth-First Search

    Binary Search

    Merge Sort

    Quick Sort

 

- 컨셉 (Concepts):

    Bit Manipulation

    Memory (Stack vs Heap)

    Recursion

    Dynamic Programming

    Big O Time & Space

 

위에 나와있는 자료구조, 알고리즘들을 직접 만들면서 연습하는 것도 큰 도움이 된다. 리스트에 있는 것들 하나하나 모두 익숙해지는 것이 중요하다. 그중에서도 Hash Table은 굉장히 중요하니 각별한 신경을 써서 배우도록 한다.

 

알고리즘 면접 문제 풀이

1. 주의 깊게 문제 듣기

면접관이 문제를 말하면 잘 듣고 있다가 확실하지 않은 부분들은 모두 물어본다. 

그리고 특별히 주의 깊게 들어야 할 부분들은 기억해둔다. 면접관이 괜히 문제에 넣을 리 없는 정보들 같은 것 말이다.

예를 들면, 두개의 정렬된 배열이 문제에 나오면 잘 기억해두자. 정렬된 배열과 그렇지 않은 배열을 풀 때 알고리즘에는 차이가 있다.

 

문제를 풀다가 최적화된 답이 나오지 않을 때는 문제에서 주어진 정보들을 다시 한번 떠올려보자.

 

2. 예시 그리기

예시를 한개 그려본다면 문제를 잘 풀 확률이 확실히 늘어난다. 문제를 듣자마자 일어나서 화이트보드에 예시를 그려라. 하지만 좋은 예시와 안 좋은 예시를 그리는 것에는 차이가 있다. 

 

좋은 예시 그리기:

     - 특정한 예시 사용. 숫자나 스트링을 이용하라

     - 큰 예시를 사용하라

    - 특별한 경우를 피하라

 

문제를 풀다가 예시가 좋은 예시가 아닌 것 같으면 고쳐라.

 

 

3. 브루트 포스(Brute Force) 알고리즘으로 시작

브루트 포스란 일단 최대한 가능한 경우를 모두 해보는 것을 말한다. 그럴 경우 최적화된  알고리즘이 나오기는 어렵지만 문제를 푸는데 도움이 된다. 그리고 브루트 포스로 시작하지 않으면 면접관이 최대한 쉬운 해결방법조차 모른다고 생각할 수도 있다.

 

최적화된 해결법이 아니더라도 시간 복잡도와 공간 복잡도를 말해라. 그리고나서 개선해 나가면 된다.

 

 

4. 최적화

최적화 하는 방법은 여러 가지 있다.

 

     - 아직 질문에 나왔지만 사용하지 않았던 정보가 있는지 다시 생각해본다.

 

    - 새로운 예시를 사용해본다. 새로운 패턴이 보일 수 도있다.

 

    - 틀린 해결책을 사용해보고 그게 왜 비효율적인지 생각함으로써 더 효율적인 해결책을 발견할 수 있다.

 

    - 시간 복잡도와 공간 복잡도를 서로 뒤바꿔 생각해본다. 공간을 희생해서 더 빠르게 만들 수 있을까?

 

    - 미리 계산된 정보를 이용할 수 있는지 생각해본다. 먼저 정렬을 하면 더 빠른 알고리즘이 나올까?

 

    - 해시 테이블 이용하기. 많은 면접 질문에서 해시 테이블이 사용된다

 

 

5. 알고리즘 다시 살펴보기

최적화된 알고리즘을 찾았다고 바로 코딩으로 넘어가지 말라. 다시 한번 짚어봐서 완전히 이해했는지 보자. 한번 더 알고리즘을 살펴볼 때 코드의 구조를 잡아라. 무슨 변수를 어떻게 쓸지 알고 넘어가자. 

 

알고리즘을 확실히 이해하고 넘어가지 않으면 코딩할 때 헤맬게 뻔하다. 코딩을 오래 할수록 실수를 할 확률도 올라간다.

 

6. 적용

최적화된 알고리즘을 찾았다면 이제 적용할 시간이다. 최대한 왼쪽 위에서부터 코드를 써 내려가자. 자리가 많이 필요할 것이다. 줄도 삐뚤지 않고 이쁘게 쓰도록 노력하자.

 

코드 쓸 때 팁:

 

    1. 따로 써야 할 긴 코드는 이미 쓰여 있다고 가정하고 쓰자. 예를 들면 행렬(matrix)을 초기화 (initialization)하는데 긴 코드를 써야 한다면 initMatrix()라는 함수가 존재한다고 가정하고 쓴다. 

 

    2. 에러 체크

 

    3. 좋은 변수 이름: 너무 긴 변수 이름은 쓸 때 시간이 오래 걸릴 수도 있다. 처음에만 설명적인 이름을 쓴 후, 나중에는 짧은 형태로 써도 괜찮다.

 

 

7. 테스트

많은 사람들은 코드를 다 쓴 후 이전에 만들어 놓은 예시를 이용해서 테스트해본다. 하지만 이런 식으로 디버깅하는 것은 오래 걸릴 수 있다. 바로 예시를 대입해보는 것보다 다음 방법대로 해보자:

 

    1. 라인 하나하나 자신이 의도한 대로 돌아가는지 분석한다.

    2. 이상해 보이는 코드 찾기

    3. 실수하기 쉬운 곳들: Recursion의 base case, integer division, null nodes in binary tress

    4. 작은 테스트 케이스 만들기

    5. 특수한 경우

 

버그를 발견했을 때는 바로 고치지 말고 고칠 때도 최적화된 방법을 생각하고 고친다.

 

 

 

**Cracking the Coding Interview 6th Edition을 보고 정리한 내용입니다.