[백준] 11053번, 가장 긴 증가하는 부분 수열

✏️  문제

✏️  아이디어

처음에는 {10, 20, 10, 30, 20, 50}의 예시로 살펴보았을 때 중복을 제거해서 문자열 길이를 재면 되는게 아닌가라고 생각했다.

하지만 그렇게 엄청 쉬운 문제는 아니였으며 문제를 다시 파악한 결과 하나를 기준으로 뒀을때 뒤의 숫자들이 증가하면 count를 올려주는 방법으로 시도해야한다.

 

✓ 사용 알고리즘

- DP[동적 계획법]

 

- 사용 이유 

일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산

 

- 사용 조건

1) Overlapping Subproblems (겹치는 부분 문제) : 동일한 작은 문제들 반복
2) Optimal Substructure (최적 부분 구조) : 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있다.

 

- 사용법

1) DP로 풀 수 있는 문제인지 파악
2) 문제의 변수 파악(state)
3) 변수 간 관계식 만들기(점화식)
4) 메모하기(Memoization) 변수의 값에 따른 결과를 저장해야한다.
5) 기저 상태 파악 하기
6) 구현하기 

    (1) 반복문 사용

    (2) 재귀 사용

 

- 구현 방법

1) Bottom-Up 방식
    - 아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식
    - dp[0]이 기저 상태이고 dp[n]을 목표 상태라 했을때 dp[0]부터 dp[n]까지 값을 전이시켜 재활용
2) Top-Down 방식
    - dp[n]값을 찾기 위해 위에서부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용

 

- 대표적인 DP 사용 피보나치 예시

memoization = [0] * 100
def fibo(x):
    if x == 1 or x == 2:
        return 1
    if memoization[x] != 0:
        return memoization[x]
    memoization[x] = fibo(x-1) + fibo(x-2)
    return memoization[x]
print(fibo(6))

 

💡 최종 코드

N = int(input())
length = list(map(int, input().split()))

dp = [1] * N

for i in range(N):
    for j in range(i):
        if length[i] > length[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

💙 마무리 

여전히 문제를 보고 이러한 알고리즘을 사용해야겠다~ 라고 떠올리는 것은 어려운 것 같다.

더 많은 연습이 필요할 것 같다.