[책] 프로그래밍 면접 이렇게 준비한다 - Ch4. 프로그래밍 문제 접근법

풀이 분석

빅 오 분석

• 최선, 평균, 최악 고려

1. 입력값을 확인하고 무엇을 n으로 놓을지 결정
2. 알고리즘에서 수행해야 할 연산 횟수를 n의 식으로 표현
3. 차수가 제일 높은 항만 남기기
4. 모든 상수 인수 없애기

어떤 알고리즘이 나을까?

성능이 좋은 순

• O(1)
  • 상수 실행 시간 (constant running time)
  • 상수 실행 시간
  • 입력의 개수와 무관

• O(log n)
  • 로그 알고리즘 (logarithmic algorithm)
• O(n)
  • 선형 알고리즘 (linear algorithm)
• O(n log n)
  • 준선형 알고리즘 (quasilinear algorithm)
• O(n^c)
  • 다항식 알고리즘 (polynomial algorithm)
• O(c^n)
  • 지수 알고리즘 (exponential algorithm)
• O(n!)
  • 팩토리얼 알고리즘(factorial algorithm)
  • n이 작아도 거의 쓰기 힘든 수준으로 느려짐

메모리 용량 분석

• 알고리즘의 메모리 용량
  • 공간 복잡도
• 구현 방법의 메모리 사용량
  • 특히 가상머신에서 돌아가는 자바, c# 에서 중요
  • 얼마나 정확하게 맞추는지 (X)
  • 실제 자료구조가 어떻게 구현되는지 제대로 이해하고 있는지(O)
  • C++ 의 경우 어떤 구조체나 클래스에 필요한 메모리에 대한 질문 받을 수도
    • 메모리 정렬, 구조체 패킹 등을 잘 이해하고 있는지
• 메모리 최적화와 속도 최적화 사이에는 보통 상충적인 면이 있음. 언급할 필요 있음

요약

• 정확하고 완전한 답 하도록 최선을 다하기
• 문제가 어려워지면. 면접관에게 힌트를 받는 상황이 있을 수도
• 자신이 사용할 언어를 잘 선택하고 꼼꼼히 익혀두기
• 문제를 풀 때는 의사소통을 활발하게
  • 문제 분석, 코딩의 단계에서 자신이 무슨 생각을 하고 있는지 알릴 수 있게
  1. 문제를 확실히 이해하기
  2. 예를 시도해 제대로 이해했는지 확인하기
  3. 적절한 알고리즘 선택 후 확인
  4. 특별 케이스 주의
  5. 막히면 다른 예나 다른 알고리즘
     • 언어의 특수 기능, 고급 기능 떠올리기
  6. 성능 질문
     • 빅오 : 상수 ~ 준선형 안에 실행
     • 메모리