[Python] 백준 알고리즘 11053번 - 가장 긴 증가하는 부분 수열 문제 출처 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 접근방법 가장 긴 증가하는 부분수열 이번에는 메모이제이션 기법을 이용해서 기존 수열과의 길이 비교에 사용된다. 메모이제이션을 사용하는 동적계획법의 이번 문제의 시간복잡도는 for문의 반복 첫번째 반복문에서 n번 그 다음 반복문은 i..

백준 알고리즘 11726 - 2 x n 타일링 문제 출처 : 11726번: 2 ×n 타일링 (acmicpc.net) 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 접근 다이나믹 프로그래밍, 즉 동적 계획법을 바탕으로 접근을 해야 하는 문제이다. n이 늘어나는 경우에 맞춰 점화식을 세우고 그에 맞춰서 코드를 진행하였다. 점화식에 대해 접근을 해보자. 해당 점화식의 경우 피보나치 수열과 유사한 점화식이 등장한다. 점화식의 경우 본인의 인덱스를 i라고 하자. 그럼 i - 2 와 i - 1의 경우의 수를 합산하면 해당 인덱스의 경우의 수..