알고리즘 문제 접근법

1. 문제를 집중해서 듣기

문제 설명과 관련된 것이라면 어떤 정보든지 아주 집중해서 들어야 한다.

2. 직접 테스트 케이스를 만들기

주어진 예제들은 크기가 아주 작거나 특별한 사례인 경우가 많다. 직접 예제를 만들어 디버깅하자.

3. 무식하게 풀기

우선은 빠르게 brute force 방식으로 풀자. 효율을 높이려고 미리 애쓰지마라. 아주 단순한 알고리즘 및 시간 복잡도를 먼저 말한 다음 최적화를 시도하라.

4. 최적화

BUD 최적화

Bottlenecks : 병목현상 Unnecessary Work : 불필요한 작업 Duplicated Work : 중복되는 작업

BUD 최적화를 통해 무식하게 푼 방법을 개선하거나 아래의 방법을 시도해 본다.

• 간과한 부분이 있는지 생각해 보자. 보통은 문제에서 언급된 정보를 모두 사용해야한다.
• 예제를 손으로 풀어 본 뒤 사고 과정을 되짚어보자.
• “잘못된" 방법으로 문제를 풀어 본 뒤 왜 알고리즘이 틀렸는지 생각해 보자. 여기서 발견된 문제들을 해결할 수 있는가?
• 시간과 공간의 비용-이익 관계를 고려하라. 이때 해쉬테이블이 특히 유용하다.

5. 검토하기

최적 해법을 찾았다면 다시 한번 자세하게 검토해보라.

6. 구현하기

코드를 모듈화시키고 아름답지 않은 부분은 리펙터링해서 깔끔하게 만들어라.

7. 테스트