다이나믹 프로그래밍 기법
한 번 해결된 부분 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 문제 해결 기법.

탑다운 방식
재귀 함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
바텀업 방식
반복문을 이용하여 작은 문제를 먼저 해결하고, 해결된 작은 문제를 모아 큰 문제를 해결하는 방식

백준 18353번

✅ 문제

N명의 병사가 무작위로 나열되어 있습니다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 합니다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 합니다.
또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용합니다. 그러면서도 남아 있는 병사의 수가 최대가 되도록 하고 싶습니다.
병사에 대한 정보가 주어졌을 때, 남아 있는 병사의 수가 최대가 되도록 하기 위해서 열외시켜야 하는 병사의 수를 출력하는 프로그램을 작성하세요.

입력 예시

7
15 11 4 8 5 2 4

출력 예시

2

내가 작성한 파이썬 코드 (틀린 코드)

어디가 틀린 건지 모르겠고, 맞는 코드 같은데 백준에 제출하면 틀렸다고 나온다...

N = int(input())

data = list(map(int, input().split()))

# 앞에 있는 병사 중에 자신보다 전투력이 높은 병사의 수 (자신 포함)  
d = [0] * N

d[0] = 1

for i in range(1,len(data)):
    # 앞에 있는 병사의 전투력이 더 높으면 + 1
    if data[i-1] >= data[i]:
       d[i] = d[i-1] + 1
    else :
        # 앞에 있는 병사 중에 자신보다 전투력이 높은 병사 찾아서 + 1 
        for j in range(i, -1, -1):
            if data[j] > data[i]:
                d[i] = d[j] + 1
                break
            else:
                d[i] = 1

print(N - max(d))

설계

앞에서부터 병사들을 순서대로 확인하며 앞에 있는 병사가 자신보다 전투력이 높으면 앞에 있는 병사의 d의 값에 1을 더해준다. 앞에 있는 병사의 전투력이 자신보다 작으면 더 앞에 있는 병사를 확인해 나보다 전투력이 높은 병사를 찾아 병사의 d의 값에 1을 더해준다. 앞에 있는 병사 중에 자신보다 전투력이 높은 병사가 없으면 1을 d에 넣어준다.
리스트 d는 자신을 포함한 앞에 있는 병사 중에 자신보다 전투력이 높은 병사들의 수를 저장한다.

➕ 다른 풀이

가장 긴 증가하는 부분 수열

N = int(input())

data = list(map(int, input().split()))

data.reverse()

d = [1] * N

for i in range(1,N):
    for j in range(0, i):
        if data[j] < data[i]:
            d[i] = max(d[i], d[j] + 1)
   
print(N - max(d))

📝 정리

내 풀이에서 틀린 부분을 찾지 못하였다. 내가 생각한 풀이와 책에 나와 있는 풀이가 같은 접근인 거 같은데 왜 내 풀이는 틀린걸까..