개발하는데 다 이유가 있겠지

[Silver II] 가장 긴 증가하는 부분 수열 - 11053

문제 링크

성능 요약

메모리: 31120 KB, 시간: 100 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 2월 23일 09:59:36

문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 A_i가 주어진다. (1 ≤ A_i ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

---

문제를 잘못 이해했고 생각했던대로 풀리지 않아서 찾던 중 dp(다이나믹 프로그래밍)으로 푸는 방법을 찾았다.

import sys
input = sys.stdin.readline


def solution():
    # 수열 개수 입력
    n = int(input())
    arr = list(map(int, input().strip().split()))

    # dp 테이블 1로 초기화
    dp = [1] * len(arr)

    # 문제를 잘못이해함(꼭 배수로 증가할 필요는 없음/ 그냥 증가하는 수열이기만 하면 됨)
    for i in range(1, len(arr)):
        for j in range(0, i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    print(max(dp))


solution()

---

다이나믹 프로그래밍(Dynamic Programming, 동적 계획법)

필요한 계산 값을 저장해두었다가 재사용하는 알고리즘 설계 기법

동일한 작은 문제들이 반복적으로 계산되는 경우 문제를 재계산 하지 않고 값을 재사용

조건

• 최적 부분 구조
  : 큰 문제를 작은 문제를 나눌 수 있다. 이러한 작은 문제의 답을 모아 큰 문제를 해결할 수 있다.
• 중복된 하위 문제
  : 동일한 작은 문제를 반복적으로 해결해야 한다.

dp 문제 확인 Tip

• 문제에 최댓값, 최솟값 혹은 모든 경우의 수를 원한다.
• 이전의 선택이 미래에 영향을 준다.

방식

• Top-down(탑-다운, 하향식) : 메모이제이션(memozation)을 사용하여 다이나믹 프로그래밍을 구현
  메모이제이션(memoiztion)이란 한번 구한 계산 결과를 메모리 공간에 메모해두고, 같은 식을 다시 호출하면 메모한 결과 그대로 가져오는 기법
  (재귀함수)
• Bottom-up(바텀-업, 상향식) : 타블레이션(tabulation)을 사용하여 다이나믹 프로그래밍을 구현
  타블레이션(tabulation)이란 하위 문제부터 천천히 해결하면서 더 큰 문제를 해결하는 기법
  (반복문)

참고 링크