study coding_interview 기술적 문제 BCR 합격한 뒤에

기술적 문제(2) 가능한 최선의 수행 시간

Best Conceivable Runtime

7일차

게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 p.108 ~ p. 130

내용 정리

7. 기술적 문제

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

BCR이 무엇일까 생각해 보는 것으로도 문제를 푸는데 유용한 힌트를 발견할 수 있다.

가능한 최선의 수행시간(Best Conceivable Runtime): 상상할 수 있는 모든 해법 중 가장 빠른 알고리즘의 수행 시간을 의미

최선의 경우의 수행 시간(Best Case Runtime): 특정 알고리즘이 가장 빠르게 동작할 경우의 수행 시간을 의미

따라서 둘은 아무 관계가 없다.

예제 : 정렬된 배열 두 개가 주어졌을 때 공통으로 들어 있는 원소의 개수를 찾아라. 두 배열의 길이는 같고 하나의 배열 안에서 동일한 원소는 하나만 존재한다.

brute force로 하면 O(N^2)이 걸린다. A의 모든 원소를 B에 검색하는 것이다.

현재 파악한 수행시간 : O(N^2)

이 문제의 BCR은 O(N)이다. 원소는 총 2N개 있고, 모든 원소를 적어도 한번씩은 살펴봐야 하기 때문이다. 다 순회하지 않는 알고리즘은 해법이 될 수 없다.

BCR : O(N)

수행 시간은 객관식 문제가 아니므로 O(N^2),O(NlogN) 등 자주 나오는 몇 가지들 중 소거법으로 찾아선 안된다. 특히 면접에선 직접 유도해야한다. 수행시간을 O(N x N) 에서 O(N) 이나 O(NlogN)으로 줄인다는 것은 두 번째 O(N)을 O(1) 이나 O(logN)으로 줄인다는 것이다. 두번째 수행시간이 O(N)인 이유는 탐색때문이었다. 문제의 조건에 따라 배열이 정렬되어 있으므로 이진 탐색을 통해 이 수행시간을 O(logN)으로 줄일 수 있다.

현재 파악한 수행시간 : O(N^2) -> O(NlogN)

하지만 BCR을 위해선 이 수행시간을 O(1)로 줄여야 한다. 그렇다면 B의 원소를 해시테이블에 모두 넣으면 된다. 해시테이블을 찾는 과정은 O(1)이기 때문이다. 면접관이 여기서 더 줄이길 요구한다면 이미 BCR까지 도달하였으므로 ‘공간 복잡도’를 생각하면 된다.

그런데 해시테이블을 사용하면 ‘정렬’과는 무관한데 왜 정렬되어 있다는 조건이 있는걸까? 조건을 다시 생각해보자.

  • 가능한 O(1) 공간을 사용해야 한다. 이미 우리는 O(N) 공간에서 최선의 수행시간을 사용하는 방법을 구했다. 공간을 더 줄여야 하므로 지금 사용한 해시테이블 방식은 포기한다.
  • 가능한 O(N) 시간을 사용해야 한다. 더 빠를 순 없다.
  • 배열이 정렬되있다는 조건을 이용한다.

현재까지 최선의 알고리즘 중 추가 공간을 사용하지 않는다면 이진 탐색이다. 이 과정을 살펴보자.

  1. A[0]을 B에서 이진 탐색
  2. A[1]을 B에서 이진 탐색
  3. A[3]을 B에서 이진 탐색
  4. …(반복)

여기서 이전에 배운 BUD를 써본다면? 어떤 A[i]를 B[x]에서 찾았다고 해보자. 그렇다면 이제부턴 B[x] 이전의 것은 탐색할 필요가 없다. 정렬되어 있기 떄문이다! 오름차순이기 때문에 더 적은 값이 있을게 뻔한 앞은 당연히 볼 필요가 없다. 이 논리라면 이진탐색을 쓸 필요 없이 선형 탐색(Linear search)로도 할 수 있고, 전체 시간이 선형 시간에 가능하다.

이 알고리즘은 O(N)의 시간과 O(1)의 공간을 사용하게 된다. 수행시간은 BCR과 같고 최소한의 공간을 사용한다. 따라서 이보다 개선할 수 없다.

오답에 대한 대처법

  • 면접에서 답을 평가할 때 O/X로 평가하지 않는다. 얼마나 근접했는가, 얼마나 시간이 걸렸는가, 코드가 깔끔한가도 중요하다.
  • 상대평가다. 남들보다 덜 틀리면 된다.
  • 아무리 실력있어도 단번에 모범 답안을 내긴 어렵다.

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

사실대로 말하는게 맞나…? 애초에 알고 있는 문제가 있긴 할까..

면접용으로 ‘완벽한’ 언어

  • 널리 사용되는 언어
  • 언어 가독성
  • 잠재적인 문제점
  • 언어가 얼마나 장황한지
  • 사용하기 쉬운 언어

라는 기준들로 선택하자.

어떤 코드가 좋아 보이나

정확도, 효율성, 간략화, 가독성, 관리 가능성에서 높은 점수를 받을 수 있어야 한다. 적절한 자료구조를 사용하고, 적절한 코드를 재사용하며, 모듈화를 통해 유연하고 튼튼한 코드를 만들자. 오류 검사도 잊지 말자.

포기하지 말라

압도적으로 어렵더라도 어떤 태도를 보이는지도 면접관이 분명 확인하는 부분이다.

8. 합격한 뒤에

합격 또는 거절 통지에 대처하는 요령

  • 입사 결정기한과 연장 : 필요하다면 연장을 요청해보자
  • 입사 제안 거절 : 괜히 척지지 말고 솔직하고 공손하게 말하자
  • 탈락 통보 대처 : 적 만들지 말자

입사 제안 평가

  • 재정 관련 사항
  • 경력 개발
  • 회사의 안정성
  • 행복도

등을 종합적으로 고려하자.

연봉 협상

  • 그냥 용감하게 해라
  • 빠져나갈 구멍 마련해라
  • 구체적으로 요구해라
  • 많이 불러라
  • 연봉 이외의 사항도 고려해라
  • 꼭 만나서 할건 없다.

입사 후

  • 큰 그림을 그리고 일정을 세워라.
  • 튼튼한 관계 수립해라
  • 원하는 것을 요구해라
  • 꾸쭌히 면접 봐라.

읽고 나서

BCR은 처음 알게 된 부분이라 의미있었다. 뒷부분은.. 생각해야 할 날이 왔으면 좋겠다.

CATALOG
    coding_interview