603 다이나믹프로그래밍

source
type 📌 개발노트
parent_topic 600-알고리즘 & 코딩테스트
types 이론

중복되는 연산을 줄이고 한번계산한 문제를 다시 계산치 않도록한다

  1. 탑다운 : 큰문제해결위해 작은문제를 호출
    • 보통 재귀로
    • 메모리제이션 방식이라고함
    • recursion depth : 재귀함수 깊이 오류 발생가능
  2. 보텀업 : 작은문제에서 순서대로 차근차근 해결
    • 단순반복문,
    • DP테이블을 통해서 결과 저장

점화식을 세워보는 것도 좋은 것 같다.
선택하느냐 마느냐

case가 내생각에는 2가지가잇음

  1. 특정 지점에 올때까지 최대값(주어진조건)
  2. 배낭문제 st : 최대값을가지면서 특정값미만이어야함
    • 제한된 용량 내에서 가치를 최대화하는 문제
    • 1처럼햇을때 계속 최대치를 추구하게되면 되는데 안되는경우가 발생할수잇음
    • 특정값을 배열로가져서 특정값이 되는경우중 최대값을 구하면됨

특징

  1. 중복적인 연산이 많음
  2. dfs,bfs,재귀 로가능하지만 시간초과가 나는경우(케이스가 너무많은경우)

https://www.youtube.com/watch?v=0bqfTzpWySY

LIS 최장 증가 수열

단일 배열에서 가장 긴 “증가하는” 수열을 찾을 때 사용하며, 순서가 중요한 문제에 적합합니다.
이전수열중에 나보다 작은것중에 가장 숫자가큰(연속된다는 값이 큰) 것 +1

LCS 최장 공통 문자열

두 개의 배열이나 문자열에서 공통적으로 나타나는 가장 긴 부분 수열을 찾는 데 사용하며, 두 데이터를 비교하고 공통 패턴을 찾는 데 적합합니다.