• DP 2020.01.17

동적계획법(DP)

  • 상향식 접근
  • 최하위 해답을 구하고, 해당 결과값을 이용해 상위 문제 해결
  • Memoization 기법 사용 (이전 계산값 저장하는 기법)
  • 문제를 쪼갤 때, 부분 문제 중복(재활용)  (ex> 피보나치 수열)

분할 정복 (divide & conquer) 

  • 하향식 접근
  • 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답 구함
  • 재귀함수로 구현
  • 문제를 쪼갤 때, 부분 문제 중복 X (ex> 병합 정렬, 퀵 정렬)
  • Memoization 기법 사용 X

 

'코딩테스트' 카테고리의 다른 글

알고리즘 풀이 블로그  (0) 2020.07.15
코딩인터뷰완전분석 - 알고리즘 설계의 5가지 접근법  (0) 2020.06.12
백트래킹, N Queen  (0) 2020.02.17
DFS, BFS  (0) 2020.01.23
코테 에러 분석  (0) 2020.01.07

+ Recent posts