문제링크 : 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
작성코드
해설
LIS (Longest Increasing Subsequence)알고리즘이라고 불리는 문제로서 dp 혹은 이분탐색으로 풀 수 있는 문제이다.
수열에서 가장 긴 부분 수열을 찾는 문제인데 기존 dp에서 값을 넣어 연산하는 방식과 조금 다르게 랭크을 넣어 순서를 구해준다.
※
만약 해당 순서의 원소들을 알고 싶다면 아래와 같이 수열을 담을 배열을 만들어 준 뒤 랭크 최대치 부터 감소하면서 하나씩 탐색하면 된다.
리스트를 돌면서 앞에 본인보다 작은 수가 있다면 해당 수의 랭크 +1을 현재 랭크에 해준다.
예를 들어 A = [7, 8, 1, 2, 9, 3] 을 넣어줄 경우 아래 표와 같이 dp(랭크)가 저장된다.
이렇게 랭크를 매겨줄 경우 dp(랭크) 최대 값 == 가장 긴 증가하는 수열의 길이가 된다.
'백준 > Python' 카테고리의 다른 글
| [백준] 2559 수열 (python 파이썬) (0) | 2022.12.07 |
|---|---|
| [백준] 11054 가장 긴 바이토닉 부분 수열 (python 파이썬) (0) | 2022.12.07 |
| [백준] 2156 포도주 시식 (python 파이썬) (0) | 2022.12.01 |
| [백준] 2579 계단 오르기 (python 파이썬) (0) | 2022.12.01 |
| [백준] 26073 외로운 곰곰이는 친구가 있어요 (python 파이썬) (0) | 2022.11.30 |