2022 02 18

2022-02-17

알고리즘 문제풀이 - 냅색 알고리즘

• DP란?
  • 테이블로 기억하기 프로그래밍!
  • 더 좋은 방법으로 테이블을 갱신해나가자!
  • 작은 문제들을 풀어두고 값을 저장해뒀다가 재사용하는 기법!

• DP의 일종!
  • DP 문제를 접근할 때에는 dy[i]를 만들어 특정 조건들을 기록하자!
    • ex. dy[i]: 금액 i를 만드는데 드는 최소 동전의 갯수
  • 기록을 더 해둠으로써 DFS (O(2^n)) 로 풀던 것을 DP (O(n^2)) 로 풀 수 있음!

• 동전 문제
  • 잔액을 거슬러줘야하는데 어떤 동전들로 거슬러줄래? 1. DFS로 모든 경우의 수 따져서 푸는 법
    • "이걸 넣을까 말까"의 경우의 수 : O(2^n) 2. DP로 접근하는 방법
    • dy[i]: i를 만드는데 드는 최소의 동전 갯수를 기록해두자!
    • 동전의 갯수 하나씩 돌면서 해당 i원을 만드는데 최소의 동전갯수를 구하기
    • 경우의 수 : O(n^2)

• 냅색 문제
  • 결국 이중 for문으로 돌아야해
    • 첫번째 for는 고려해야 할 조건 (동전의 갯수, 문제의 시간 등)
    • 두번째 for는 테이블 돌면서
  • 조건이 유한하다면 두 번째 for문 뒤 -> 앞!
  • 조건이 무한하다면 두 번째 for문 앞 -> 뒤!
    • j가 한문제만 풀게 하려면 뒤에서 부터 돌게 하라!