면접 때 어떤 언어를 사용할까?
- 사람들이 많이 알고
- 언어를 전혀 모르는 사람들이 보더라도 어느 정도 내용 파악이 가능하면서
- 버그가 발생할 가능성이 적고
- 코드의 길이가 길어지지 않는 편이고
(하지만 길어지더라도 축약을 통해 어느정도 해결 가능)
- 사용할 수 있는 기능이 많은
(python과 같은 언어가 대표적. 하지만 우리가 임의로 이러한 기능을 하는 메서드가 있다고 치는 것으로 어느정도 해결 가능)
기술 면접 준비 방법
- 혼자 힘으로
- time & space complexity를 고려하며
- 종이 위에 문제를 푼다.
- 테스트 또한 종이 위에다 한다.
- 종이 위에 푼 답안을 컴퓨터에 옮겨 적고 에러를 확인하고 다시는 동일한 실수를 하지 않도록 조심한다.
- mock interview를 많이 한다.
좋은 알고리즘을 짤 때 고려할 것들
- 구조체를 새로 만드는 행위를 겁내지 말아라.
- 응용시킬 수 있는 형태로 함수 만든다.
- 특정 기능을 갖는 단독 함수를 만들어서 main을 깔끔하게 만든다.
- 문제를 일반화할 수 있다면 그래도 좋다.
- 조건문을 통해서 error가 발생하지 않도록 한다.
Best conceivable runtime(BCR)
- 어느 부분을 어떻게 개선할 것인지 대략적으로 파악이 가능하다.
- 현재 time complexity 이하의 작업 단위는 자유롭게 할 수 있다.
- 더 이상 개선할 수 없는 경계를 파악할 수 있다.
- time complexity가 더 이상 개선 불가한 지점에 다다랐다면 space complexity를 고려하자. space의 최소값은 O(1)이다.
문제를 풀 때 가져야 하는 태도
- 문제를 주의깊게 읽으면서 중요한 조건들을 모두 체크한다.
- 적당한 예제를 통해 문제를 제대로 이해한다.
적당한 예제란, 유효하고, 충분히 크기가 크면서, 특별하지 않은 예제를 말한다.
- 가장 단순한, 어떻게 보면 무식하다고도 할 수 있는 알고리즘을 작성하자.
작성한 알고리즘의 time & space complexity를 계산한다.
- 알고리즘을 개선한다.
- 빼먹은 조건은 없는지?
- 알고리즘이 설명할 수 없는 새로운 예제는 없는지?
- time과 space를 tradeoff해서 runtime을 더 줄일 수는 없는지?
- 데이터를 다른 방식으로 정의하거나 계산 순서를 바꿈으로써 runtime 단축이 가능하지는 않은지?
- hash table을 사용해보자.
- 최적의 runtime을 생각해보자
-
검토하자
알고리즘에 대한 이해를 굳히는 과정이다. 본격적인 코딩 전에 최대한 완벽한 답안을 다져야 나중에 시간 낭비가 발생하지 않는다.
-
모듈화
- 초기화 코드를 작성한다고 시간을 낭비하지 말라. 핵심만 설명하기에도 바쁘다.
- error check.
- 필요하다면 classes, structs를 만들어서 사용해도 좋다. 역시나 이것들을 정의한다고 시간 낭비를 하지는 말도록 하자.
- 변수명은 최대한 정확하게 작성한다. 변수명이 너무 길다면 줄여쓰겠다고 면접관에게 말하면 된다.
- 테스트하자
- 내가 의도한 대로 코드가 작성되었는지?
- weird looking code가 있지는 않은지?
- base case가 없는 recursive functions, NULL node 등의 실수는 없는지?
- small test cases
- special cases
버그가 발생했다면 당연히 수정을 해야한다. 수정하는 경우, 왜 버그가 발생하는지, 내가 고치려는 방법이 최적이라고 생각하는 이유에 대해서도 설명하도록 하자.
알고리즘 개선 방법
- BUD(Bottlenecks, Unnecessary work, Duplicated work)가 있는지 확인하고, 있다면 제거한다.
- 실생활에 가까운 예제로 바꿔서 생각해보자.
- 문제를 단순화해서 해결한 후 그 해결법을 확장해보자.
- base case에서 시작해보자.
- 여러개의 자료구조를 나열하고 각각이 문제에 적합한지 고민해보자.
해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.