메뉴 닫기

[알고리즘]알고리즘 설계의 다섯가지 접근법

코딩인터뷰 완전분석 (게일 라크만 맥도웰 지음 ) 을 공부하면서 작성하는 글입니다.

알고리즘 문제를 풀기위한 설계는 5가지의 접근법이 있다.

  1.  예증
    일반적 규칙을 유도해내서 문제를 해결한다.
    ex) 거리, 시간 그리고 속도에 관한 문제 해결
  2. 패턴매칭
    기존의 문제와 유사한 문제를 떠올리고 그 문제의 해답(가령 알고리즘)을 수정해서 적용한다.
  3. 단순화와 일반화
    자료형이나 데이터 양과 같은 제약조건을 변경해서 문제를 단순화 해본다.
    단순화 된 버전의 문제를 해결한다면 최종적으로 일반화해서 찾은 알고리즘을 복잡한 형태로 다듬어 간다.
  4. 초기사례로부터의 확장
    초기사례(n=1)에 대해 문제를 푼다. 후에 n=2에 대한 문제를 풀어보고 n=3를 풀어본다.
    이후 N-1을 안다면 N을 어떻게 찾을 수 있을지 고민해보고 규칙을 찾아 문제를 해결한다.
  5. 자료구조 브레인스토밍
    일련의 자료구조를 차례대로 적용해보고 적절한 알고리즘을 찾아나가는 방법이다.
    연결리스트? 이진트리? 힙? 처럼 여러 자료구조를 이해하고 적응시킬 수 있는 능력이 중요하다.

이렇게 5가지 접근법으로 문제를 풀어나가 보자. 물론 기본적인 자료구조에 대한 이해는 반드시 필요하다.

출처 : 코딩인터뷰완전분석