cotton 블로그 cotton 블로그

1912

• 백준 DP 문제 풀이 (Silver) 11053번, 1932번, 1912번, 9461번 python

  알고리즘 2023. 7. 21. 15:03

  1. 가장 긴 증가하는 부분 수열 (11053번) 숫자 수열이 주어질 경우 가장 길게 증가하는 부분 수열의 길이를 구하는 문제입니다. 예시) {10,20,10,30,20,50} 인 경우 가장 긴 증가하는 부분 수열은 {10,20,30,50}이고 길이는 4입니다. 앞에서부터 차례로 자신을 포함하는 가장 긴 부분 수열을 구하면 됩니다. 자신을 포함한 가장 긴 수열을 구하는 방법은, 자신보다 앞에 위치하면서 자신보다 작은 숫자 중 현재 가장 긴 증가하는 부분 수열을 가지는 숫자에 자신을 붙이면 됩니다. 위의 예시 중 4번째 인덱스의 30을 포함한 부분 수열을 구하는 예를 들어보겠습니다. 30보다 앞에 위치한 숫자 중 30보다 작은 10,20,10 중 증가하는 부분 수열 중 가장 긴 숫자는 20입니다. 그러므로..

  Read More