[리뷰] 코딩 인터뷰 완전 분석 - 기술적 문제

book.naver.com/bookdb/book_detail.nhn?bid=12327704

코딩 인터뷰 완전 분석

(이제 취업 준비겸 코딩테스트를 위해서 "코딩 인터뷰 완전분석"을 읽기 시작했다.)

-준비하기

1. 직접 풀도록 노력하라: 포기하지 말라! 그리고 문제를 풀 때는, 공간과 시간 효율에 대해서도 반드시 생각하길 바란다.

2. 코드를 종이에 적으라

3. 코드를 테스트하라: 물론 종이 위에서 말이다. 일반적인 경우뿐 아니라, 기본 조건, 오류 발생 조건 등을 전부 테스트하라는 뜻이다.

4. 종이에 적은 코드를 그대로 컴츄터로 옮긴 뒤 실제로 실해해 보라: 종이에 적는 과정에서의 실수 목록들을 만들어서 실제 면접장에서는 같은 실수를 저지르지 않도록 유의하라.

 

-알고 있어야 할 것들

핵심 자료구조, 알고리즘, 기본 개념

자료구조	알고리즘	개념
연결리스트(Linked Lists)	너비 우선 탐색(Breadth-Fist Search)	비트 조작(Bit Manipulation)
트리, 트라이(Tries), 그래프	깊이 우선 탐색(Depth-First Search)	메모리(스택 vs 힙)
스택&큐	이진탐색	재귀
힙(Heaps)	병합정렬(Merge Sort)	동적 프로그래밍(Dynamic Programming)
Vector / ArrayList	퀵 정렬	big-O 시간 & 공간
해시테이블

이 주제에 대해 사용법, 구현법, 애플리케이션, 그리고 가능하다면 공간과 시간 복잡도에 대해서도 알아두기 바란다.

자료구조와 알고리즘을 종이에(그 다음엔 컴퓨터로) 직접 구현해 보는 건 굉장히 좋은 훈련이다. 자료구조가 내부적으로 어떻게 돌아가는지 이해할 수도 있다.

특히, 해시테이블은 매우 중요한 주제다.

 

-실제 문제 살펴보기

코딩기술 순서도

1.듣기

문제 설명과 관련된 것이라면 어떤 정보든지 아주 집중해서 들어야 한다. 최적 알고리즘을 설계하기 위해선 모든 정보가 필요할지도 모른다.

2.예제 

대부분의 예제들은 크기가 아주 작거나 특별한 사례인 경우가 많다. 직접 예제를 만들어서 디버깅하라. 직접 만든 예제가 특별한 경우인가? 혹은 충분히 큰 입력인가?

3. 무식하게 풀기

우선은 빨리 무식한 방법(brute force)으로 풀길 바란다. 알고리즘의 효율을 높이려고 미리 애쓰지 말라. 아주 단순한 알고리즘 및 시간 복잡도를 먼저 말한 다음에 최적화를 시도하라. 아직 코딩할 단계는 아니다!

4.최적화

BUD최적화를 통해 무식하게 푼 방법을 개선하거나 아래의 방법을 시도해 본다.

-간과한 부분이 있는지 생각해 보자. 보통의 경우 문제에서 언급된 정보를 모두 사용해야한다.

-예제를 손으로 풀어 본 뒤 여러분의 사고 과정을 되짚어 보라. 어떻게 풀었는가?

-잘못된 방법으로 문제를 풀어 본 뒤 왜 알고리즘이 틀렸는지 생각해 보라. 여기서 발견된 문제들을 해결할 수 있는가?

-시간과 공간의 비용-이익 관계를 고려하라.이때 해시테이블이 특히 유용하다.

5.검토하기

최적의 해법을 찾았다면, 다시 한번 자세하게 검토해 보라.코딩 시작 전에 세밀한 부분을 제대로 알고 있는지 확인할 필요가 있다.

6.구현하기

시작부터 코드를 모듈화시키고 아름답지 않은 부분은 리팩터링해서 깔끔하게 만들라.

7.테스트

다음의 순서로 테스트해 보길 바란다.

7-1.개념적 테스트: 마치 코드 리뷰를 하듯이 자세하게 코드를 훑어보며 테스트하기

7-2.특이하거나 표준적이지 않은 코드

7-3.산술연산 혹은 널(null)노드와 같이 실수가 날 만한 부분

7-4.작은 크기의 테스트들. 큰 크기의 테스트보다 빨리 검증 가능하고 효율적

7-5.특이하거나 극단적인 입력

BUD 최적화
-병목현상(Bottlenecks)
-불필요한 작업(Unnecessary Work)
-중복되는 작업(Duplicated Work)

 

->순서도를 적용시켜보자!

1.경청하기

문제를 주의 깊게 듣고 문제와 관련된 모든 독특한 정보를 머릿속에 기억해 둬야 한다. ex) "정렬된 배열 두 개가 주어졌을 때", "서버에서 반복적으로 수행되는 알고리즘을 설계하려고 하는데"(라는 말은 반복적으로 실행되는 경우와 한 번만 실행되는 경우가 매우 다르다는 것을 뜻한다. 혹은 입력 데이터로 적당한 계산 결과를 미리 구해놔도 된다는 의미가 될 수도 있다.)

 

2.예제를 직접 그려보기

-명확한 예제를 쓰라

-충분히 큰 예제를 쓰라.

-특별한 예제를 지양하라

 

3.무식한 방법으로 일단 해보기

 

4.최적화

간과한 정보가 있는지? 새로운 예제를 만들기, 틀린 해법을 통해 올바른 해법을 찾아낼 수도 있어 '잘못된 방식'으로 문제를 풀어 보자. 해시테이블을 사용하라. 가능한 최선의 수행 시간이 무엇인지 생각하라

 

5.검토하기

코딩을 시작하기 전에 가능하면 '완벽'에 가까운 상태로 마는 뒤에 실제 코딩에 들어가야 한다. 알고리즘을 다시 한번 훑어 나가면서 코드의 전체적인 구조에 대한 감을 잡으라.

어떤 변수를 사용할 것이고 언제 값을 변경할 것인지 등과 같은 코드의 세세한 부분도 미리 알고 있어야 한다.

(어떻게 적용할까? 의사코드(pseudocode)로 적오보자)

 

6.코드 작성하기

-모듈화된 코드를 사용하라 : 행렬을 초기화해야 한다면 초기화 코드를 작성한다고 시간을 낭비하지 말라. 그냥 initIncrementalMatrix(int size)와 값은 함수가 있다고 가정해도 좋다.

-에러를 검증하라 : 면접관에게 todo를 집어넣고 그냥 여기서 어떤 테스트를 하겠다고 말로 설명하면 된다.

-필요한 경우에 다른 클래스나 구조체를 사용하라

-좋은 변수명을 사용하라 : for루프에서 쓰는 i,j를 제외하고는 한 글자 변수명을 사용하지 않는 것이 좋다. int i=startOfChild(array)와 같은 코드를 작성하려고 한다면 i보다는 startChild와 같은 변수명을 쓰는게 낫다. 그렇다고 변수명이 너무 길면 코딩 속도가 느려지므로 sc로 줄여서 쓰겠다고 면접관에게 설명한다.

 

7.테스트

 

-최적화 및 문제풀이 기술#1: BUD를 찾으라

병목현상 :

병목현상이란 여러분의 알고리즘에서 전체 수행 시간을 잡아먹는 부분을 의미한다. 일반적으로 두 가지 이유 때문에 발생한다. 1) 어떤 부분 때문에 알고리즘이 느려지는 경우 2)검색을 여러 번 하는 것처럼 반복적으로 수행하는 부분이 여러 개 있는 경우

해결하는 것은 전체 수행 시간에 커다란 차이를 만들어낸다.

 

불필요한 작업

 

중복되는 작업

 

-최적화 및 문제풀이 기술#2:스스로 풀어보라 DIY(Do if Yourself)

질문을 받으면, 실제 예제를 통해 직관적으로 문제를 풀어 나가려는 노력을 하길 바란다. 가끔은 예제의 크기가 클수록 문제가 쉽게 풀린다.

예제: 길이가 작은 문자열 s와 길이가 긴 문자열 b가 주어졌을 때, 문자열 b안에 존재하는 문자열 a의 모든 순열을 찾는 알고리즘을 설계하다. 각 순열의 위치를 술력하면 된다.

예제를 크기를 크게 하라는 것은 

s: abbc

b: cbabadcbbabbcbabaabccbabc 을 말한다.

문제를 풀 때 문제에 적합하고, 크기가 크며, 구체적인 예제를 바탕으로 직관적으로(즉 손으로 직접) 문제를 풀어 보길바란다. 그 다음에 여러분이 어떻게 풀었는지 열심히 생각해 보고 그 문제풀이 과정을 역으로 이용해 알고리즘을 설계해 나가면 된다.