[백준] 11053 - 가장 긴 증가하는 부분 수열 (C++)
문제 출처: www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이: 필자가 생각하기에 이 문제의 핵심은 증가수열의 첫 부분 정하기 뒷부분에서 만들어지는 증가 수열이 기존에 만들어진 증가수열의 일부분(중복되는 부분) 인지 체크 때문에 cache 자료구조를 만들어서 방문한 자리를 체크해주었다. 이렇게 해주어도 괜찮은 이유는 예제를 보면서 알아보자 arr 10 20 10 30 20..
2021. 3. 26.
