[알고리즘|기초] 문제 해결 접근법

[1단계] 문제 이해

• 문제를 잘 읽고 정확하게 이해했는지 확인합니다.
• 문제와 관련된 모든 정보들을 기록하는것이 좋습니다.
• 최적 알고리즘을 설계하기 위해서 모든 정보가 필요할 수 있습니다.
• 아래 체크 포인트로 반드시 문제를 제대로 확인하고 다음 단계로 넘어갑니다.
  • 입력 / 출력은 무엇인가?
  • 시간복잡도, 공간복잡도, 메모리 사용량 등 요구되는 제약 조건은 무엇인가/
  •  이 문제에서 가장 중요한 값은 무엇인가?
  •  이 문제에 목표는 "xxxxxxxxx" 가 맞는가?

[2단계] 구체적인 예제들

• 예제를 직접 손으로 그려보며 내가 문제를 제대로 이해했는지 다시 한번 확인합니다.
• 예제를 만들 때는 다음 체크 포인트를 다음으로 넘어갑니다.

[3단계] 계획 수립 및 알고리즘 설계 - 무식하게 풀기

• 적용해볼만한 패턴이나 알고리즘이 없다면, 우선은 가장 무식한 방법 (brute force)으로 문제를 풉니다.
• 문제 해결 패턴을 찾거나 알고리즘의 효율을 높이려고 미리 애쓰지 않도록 합니다.
• 내가 설계한 알고리즘과 시간 복잡도를 정리한 후에 4단계로 넘어갑니다.

[4단계] 계획 수립 및 알고리즘 설계 : 최적화

접근 방식을 되짚어 보며 "BUD" 방식으로 최적화를 합니다.

• 병목현상 (Bottlenecks)
  • 병목현상이란 전체 수행시간의 대부분을 잡아먹는 현상을 의미합니다.
  • 병목현상이 발생하는 이유 - 코드 실행에서 특정 부분이 매우 느린경우
  • 검색을 여러번 하는 것 처럼 반복적으로 수행하는 부분이 많은 경우
• 불필요한 작업 (Unnecessary work)
• 중복되는 작업 (Duplicated work)

 [5단계] 검토하기

• 최적 설계한 알고리즘을 다시 한번 자세하게 검토합니다.

[6단계] 알고리즘 구현

• 가독성, 모듈화를 고려해서 코드를 작성합니다.
• 모듈화 할 수 있는 코드는 처음부터 분리 하는 것이 좋습니다.

[7단계] 테스트