[Python] 백준 문제풀이 - 11053번

이형래·2022년 7월 25일
0

백준문제풀이

목록 보기
32/36

백준 문제풀이 - 11053 번


링크 -> https://www.acmicpc.net/problem/11053


1. 요약 및 풀이방법

수열이 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 동적 프로그래밍 알고리즘의 대표적인 문제입니다.

이 문제는 특정 인덱스에서 증가하는 부분 수열을 구해놓은 dp 리스트를 이용해 현재 인덱스보다 앞의 상황에서 증가하는 부분 수열의 최대 길이를 저장해둠으로써 연산 횟수를 줄였습니다.


2. Code

def main():
    N = int(input())
    arr = list(map(int, input().split()))
    dp = [1] * N

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

if __name__ == "__main__":
    main()

3. 학습 내용

동적 프로그래밍은 간단하게 약간의 메모리를 더 사용해서 속도 효율을 높이는 방법입니다.
한번 계산했던 것은 다시 계산하지 않고 저장되어있던 값을 사용합니다.
동적 프로그래밍은 주로 아래와 같은 상황에서 사용합니다.

  1. 큰 문제를 작은 문제로 쪼갤 수 있고,
  2. 작은 문제의 결과가 큰 문제에서 동일하게 쓰일 때

4. 결과

profile
머신러닝을 공부하고 있습니다. 특히 비전 분야에 관심이 많습니다.

0개의 댓글