[TIL] 2019-11-28

undefcat·2019년 11월 27일
0

TIL

목록 보기
78/231

2019-11-28 목요일

알고리즘

종만북

조합탐색

  • 완전탐색이 기본 뼈대. 이 후, 여러 최적화 기법으로 답을 찾는다.
  • 핵심은 가지치기
    1. 현재까지의 최선의 답을 이용해 가지치기
    2. 휴리스틱 함수를 이용하여 가지치기
    • 남은 경로로 답을 구성했을 때, 최선의 답의 후보가 될 수 있는지?
      - 비관적, 낙관적 휴리스틱
      - MST
    1. 탐욕법으로 탐색시작
    • 좋은 답이 빨리 나올 수록 가지치기가 더 효율적
    1. 현재까지의 경로를 가지치기
    • 현재까지 지나온 경로에 간단한 조작을 했을 때, 더 좋은 값이 나오면 탐색 중단
    1. 마지막단계 메모이제이션
    • 조합탐색은 크기가 커서 DP를 활용못할 때 사용
      • 마지막 단계에서 메모이제이션을 하면 효율이 극대화
      • 단, 가지치기로 인해 메모이제이션이 하기가 힘드므로 DP함수를 따로 구현하고, 일정한 값부터는 DP함수로 탐색을 구현
      • 보통 메모이제이션되는 값이 작을 것이므로 map을 활용한 캐시도 고려할만 하다.
profile
초보개발자니뮤ㅠ

0개의 댓글