[coding interview] big O

서론

알고리즘에서 가장 중요하다고 할 수 있는 Big-O의 개념에 대해 정리하고 넘어가도록 한다. Big-O는 효율성,성능과 가장 밀접한 개념이기도 하다. 알고리즘의 탐색 속도를 측정하는 지표로서 내가 짠 알고리즘이 얼마나 빠르게 결론에 도출했는지를 짐작할 수도 있다.

점근적 실행 시간, 또는 big-O 시간에 대한 개념이다.

알고리즘의 수행 시간을 세 가지 다른 방법으로 나타낼 수 있다. 대부분의 알고리즘은 최악의 경우와 평균적인 경우를 많이 평가한다.

알고리즘에서는 시간뿐만 아니라 메모리(공간) 또한 신경 써야 한다. 크기가 n인 배열은 O(n)의 공간이 필요하고, n X n 크기의 2차원 배열에서는 O(n^2)의 공간이 필요하다. 재귀 호출에서 사용하는 스택 공간 또한 공간 복잡도 계산에 포함된다.

int sum(int n){
  if(n <= 0){
    return 0;
  }
  return n+ sum(n-1);
}

위의 재귀함수 코드는 호출될 때마다 스택의 깊이가 깊어지므로 O(n)만큼의 공간을 사용한다. 하지만 단순의 함수의 호출이 공간을 차지하는 것이 아니라 스택에 쌓여 있는 상황일때의 함수 호출이 공간을 차지한다고 생각하면 된다.

기초적인 자료구조와 알고리즘 지식은 유용하다. 트리,그래프, 리스트, 정렬, 다양한 지식은 쓸 곳이 은근히 많다. 자료구조와 알고리즘 없이 문제풀이 능력을 측정할 수 있는 문제가 거의 없기 때문에 이들을 바탕으로 많이 생성되어 있다.
화이트보드 손코딩 ? 화이트 보드의 장점은 큰 그림을 그리는데 도움을 준다. 자잘한 컴파일 오류를 신경쓰기 보다는 핵심에만 집중하면 된다.
어떤 문제를 출제하는가? 최근 기출을 보는 것은 크게 도움이 안될 수도 있다. 면접관에 따라 질문지가 완전히 다르기 때문이다. 알고리즘 문제는 어느 회사나 전체적으로 비슷하다. -> 핵심적인 알고리즘 유형만 공부해 놓으면 회사별로 준비하지 않더라도 좋은 결과를 낼 수 있다.

사전 면접 (screening interview) 보통 전화로 진행될 경우가 많고 코딩이나 알고리즘 관련 질문들이 나오는 경우가 많고, 생각보다 난이도도 까다로운 편이다.
대면 면접 보통 세번에서 6번 정도의 대면 면접이 실시될 수 있다. 보통 기술적인 질문들이나 코딩,알고리즘, 디자인/설계, 경력 등에 대해 물어보는 편이다.

책에서는 계속해서 각 글로벌IT기업별로 대비해야하는 특징들에 대해 다루고 있고, 이력서 등을 쓰는 요령에 대해서도 설명이 나와있다. 이 부분은 실제 이직을 앞둔 사람들이 보면 유용할 것으로 보인다. 다음에 이어서는 IT기술과 관련된 내용들을 하나씩 정리해보도록 한다.

코딩인터뷰 완전 분석 - 게일 라크만 맥도웰