코딩 인터뷰 완전분석 | 7. 기술적 문제 - 최적화

VII. 기술적 문제

최적화 및 문제풀이 기술

1. BUD 찾기

병목현상 (Bottlenecks)

전체 수행을 잡아 먹는 부분을 찾아 최대한 시간 줄이기

- 알고리즘이 느려지는 경우

- 반복적으로 수행하는 부분이 여러개 있는 경우

불필요한 작업(Unneccssary Work)

중복되는 작업(Duplicated Work)

2. 스스로 풀어보기 DIY (Do It Yourself)

크기가 크고 구체적인 예제를 활용해 직관적으로, 손으로 직접 문제를 풀기

그 과정을 생각해보고 역으로 알고리즘을 설계하기

3. 단순화, 일반화하기

1) 자료형 같은 제약 조건을 단순하게 만들거나 변형하기

2) 단순화된 버전의 문제를 풀기

3) 단순화된 문제 알고리즘이 완성되면 보다 복잡한 형태로 만들어 나가기

4. 초기 사례로부터 확장하기 (build)

n=1 같은 초기 사례 문제를 푼 다음, n=3, n=4 같이 점차 확장하여 해법 구하기

주로 재귀 알고리즘으로 구현되는 경우가 많음

5. 자료구조 브레인스토밍

문제를 보고 자료구조를 차례로 살펴보며 접근하기

 

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

BCR: 상상할 수 있는 모든 해법 중 가장 수행 시간이 빠른 알고리즘, 이보다 더 빠른 해법은 없다

- 문제, 입출력 함수에 관한 것으로 알고리즘과는 무관

 

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

- 특정 알고리즘에 관련된 것

 

BCR 보다 수행 시간이 빠르거나 같은 작업은 전체 수행 시간에 영향을 주지 않음

BCR  이후엔 공간 복잡도를 개선하는 방향으로 고려하기