[BOJ] 다이나믹 프로그래밍

sundays·2021년 6월 30일
0
  • 큰문제를 작은 문제를 나눠서 풀어야 함
    1. DP : 중복이 발생함
    2. 분할 정복 : 중복이 발생하지 않음
  • 겹치는 부분(작은) 문제 예) 피보나치 수열, 문제의 정답은 일정
    • memorization 방식을 사용하면 속도가 향상 된다
    • 모든 문제를 한번씩만 풀면된다 = 문제의 개수 x 문제 1 개를 푸는 시간 (=함수의 시간복잡도)
  • 최적 부분 구조 => 문제의 정답을 작은 문제의 정답에서 찾을 수 있음
  • 해결방법
    1. top-down : 재귀
    2. bottom-up : 반복문
  • 연습문제

    1. 가장 긴 바이토닉 부분 수열
      https://www.acmicpc.net/problem/11054
      수열 A 가 주어졌을때 그 수열의 바이토닉 부분 수열 중에서 가장 긴것을 구하는 문제
      - D[k] + D2[k] - 1

    2. 연속합 2
      수열의 연속합 중 가장 큰 합을 구하는 문제
      수는 하나 제거할 수 있다. 제거하지 않아도 된다
      시간복잡도 O(n) n<=100000
      D[I] = I번째에서 끝나는 연속합
      D2[i] = i번째에서 시작하는 연속합

    3. 타일 채우기
      https://www.acmicpc.net/problem/2133

profile
develop life

0개의 댓글