1. 듣기

독특한 정보를 모두 사용해야 한다. 문제를 푸는데 아무 영향을 끼치지 않는 정보를 제공하는 경우는 많지 않다. 화이트보드에 정보를 미리 써놓자.

2. 예제

• 명확한 예제를 쓰라: 문제에 맞는 실제 숫자와 문자열을 사용하라.
• 충분히 더 큰 예제를 쓰라: 대부분 예제의 크기가 매우 작다. 충분하게 큰 예제의 50% 정도밖에 안 되는 경우가 많다.
• 특별한 예제를 지양하라: 무심코 특별한 경우의 예제를 그리기 굉장히 쉬우므로 특히 주의를 기울여야 한다. 어떤 경우든지 여러분의 예제가 특별한 경우에 속한다면, 큰 문제가 없어 보이더라도 예제를 다시 만들라.

3. 무식하게 풀기

면접관이 무식하게 풀기도 못한다고 착각하지 않게 해야한다.
무식하게 풀고 그것을 개선해 나가면 된다. 무식한 알고리즘은 최적화의 시작점이고, 문제에 집중하도록 도움을 준다.

4. 최적화

• 간과한 정보가 있는지 찾아보기
• 새로운 예제
• 잘못된 방식으로 풀기 (?) TODO
• 시간과 공간의 실익을 따지기. 추가 상태를 저장해놓기
• 정보를 미리 계산해 두기. 정렬 등
• 해시테이블을 사용하기
• 가능한 최선의 수행시간(BCR)을 생각하기

5. 검토하기

코딩을 시작하기 전에 완벽에 가까운 상태로 만들고 들어가야 한다
변수 사용과 값 변경을 미리 알고 있어야 한다. 의사코드를 적어보기. 배열 검색, 최대값 찾기, 힙에 넣기 등의 크기로. 코드를 거의 작성하는 수준일 필요는 없음

6. 구현하기

• 모듈화된 코드를 사용하라. 초기화를 구현하기보다, init함수가 있다고 가정하고 가는게 낫다
• 에러를 검증하라. 에러가 가능한 부분에 TODO로만 넣어두자
• 필요한 경우에 다른 클래스나 구조체를 사용하라. 2차원 배열을 사용하는 대신 구조체를 정의했다고 두고 쓰자. 세세한 건 나중에
• 좋은 변수명을 사용하라. 반복이 심하면 줄여쓴다고 말하고 줄이면 된다
• 리팩터링 할 부분을 발견하면, 바로하지 말고 면접관에게 설명한 후 시간을 들일 필요가 있는지 판단하라
• 뭔가 헷갈리면, 2번 예제로 돌아가 위의 과정을 다시 짚어보라

7. 테스트

• 이전에 만든 예제를 테스트에 사용하지 마라
• 개념적 테스트부터 시작하라. 코드를 읽어보면서 머릿속에서 테스트 돌려보기. 면접관에게 설명하는 자신을 상상하라
• 평소와 다르게 돌아가는 부분을 유심하게 살펴보라. for의 시작이 1부터라던가.
• 버그가 자주 발생하는 부분을 유심히 살펴보라. 재귀함수의 베이스케이스, 정수 나눗셈, 이진트리의 null 노드 연결 리스트 순회 시 앞과 끝
• 작은 규모의 테스트를 돌려보라. 작으면 빨리 찾는다
• 특별한 경우를 테스트하라. null, 단일원소, 극단적인 입력, 다른 특별한 입력

최적화 및 문제풀이 기술

(1) BUD를 찾으라

• 병목현상(Bottlenecks)
• 불필요한 작업(Unnecessary Work)
• 중복되는 작업(Duplicated Work)

병목현상

• 어떤 부분 때문에 알고리즘이 느려지는 경우
• 검색을 여러 번 하는 것 처럼 반복적으로 수행하는 부분이 여러 개 있는 경우

불필요한 작업

중복되는 작업

(2) 스스로 풀어보라

손으로 직관적으로 푸는 것이 알고리즘을 생각하는 것보다 최적화되어 있을 수 있다. 무의식적인 부분을 빠짐없이 알고리즘으로 제대로 옮겨야 한다.

(3) 단순화, 일반화하라

• 자료형과 같은 제약조건을 단순화하거나 변형시킨다
• 단순화된 버전의 문제를 푼다
• 단순화된 문제의 알고리즘이 완성되면 해당 알고리즘을 보다 복잡한 형태로 다듬어간다

(4) 초기 사례로부터 확장하기

n = 1에서 구해노은 해법을 이용해서 n = 3, n = 4 까지 확장한다
자연스럽게 재귀 알고리즘으로 되는 경우가 많다

(5) 자료구조 브레인스토밍

일련의 자료구조를 차례차례 살펴보면서 하나씩 적용해보자. 트리를 써보자 라는 결심만으로 문제가 자연스레 풀리는 경우가 있다
연결리스트? 배열? 이진트리? 힙?

가능한 최선의 수행시간 Best Conceivable Runtime

어떤 문제를 푸는 데 상상할 수 있는 모든 해법 중 수행 시간이 가장 빠른 것을 의미
TODO

오답에 대한 대처법

TODO

알고 있던 문제가 면접에 나왔을 때

TODO

면접용으로 완벽한 언어

TODO

어떤 코드가 좋아보이나

• 정확도
• 효율성
• 간략화
• 가독성
• 관리가능성

TODO

포기하지 말라

TODO