프로그래밍/코딩테스트 문제풀이
[Python] 백준 11053. 가장 긴 증가하는 부분 수열 (LIS)
inspirit941
2019. 12. 22. 18:29
반응형
https://www.acmicpc.net/problem/11053
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
www.acmicpc.net
가장 긴 증가하는 부분수열 문제. Longest Increasing Subsequences라고도 불리며, DP로 풀 수 있는 보편적인 문제유형 중 하나라고 한다.
풀이 설명은 아래 블로그에서 그림으로 자세히 볼 수 있다.
https://bitwise.tistory.com/215
백준 11053번: 가장 긴 증가하는 부분 수열
https://www.acmicpc.net/problem/11053 1. 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는..
bitwise.tistory.com
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import sys | |
| N = int(sys.stdin.readline()) | |
| arr = list(map(int, sys.stdin.readline().split())) | |
| result = [1] * N | |
| for i in range(1, N): | |
| for j in range(i): | |
| if arr[j] < arr[i]: | |
| result[i] = max(result[i], result[j]+1) | |
| print(max(result)) |
반응형