반응형 이진 탐색2 [Algorithm][Python]최장 증가 부분 수열(LIS) 알고리즘 + 코드 이번에 알아 볼 알고리즘은 최장 증가 부분 수열, 통칭 LIS(Longest Increasing Subsequence)입니다. 어떤 수열이 입력으로 주어질 때 해당 수열에서 증가하는 부분 수열의 최대 길이를 구하는 문제에서 볼 수 있습니다. 약간 변형을 해서 사용하면 LCS 알고리즘과도 비슷합니다. 사실 구현만 한다고 했을 때는 굳이 따로 포스팅을 해야할 만큼 거창한 풀이 방법이 있는 것은 아닙니다. 동적 계획법이 익숙하신 분들에게는 그냥 우리가 머리로 생각하듯이 처음부터 원소를 하나씩 순차적으로 탐색하면서 부분 수열의 길이를 세면 되는 거라 코드 작성도 쉬운 편이라고 생각하지만, 제 개인적인 경험으로는 그냥 이런 걸 처음봐서 증가 부분 수열이 무슨 소린지 이해하는 것이 시간이 더 걸렸던 것 같습니다. .. 2023. 10. 5. [BOJ][Python]11054 풀이 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net def f(n, arr): dp = [1 for _ in range(n)] for i in range(n): for j in range(i): if arr[i] > arr[j]: # 현재 원소가 처음부터 비교해오는 원소보다 크면 if dp[i] < dp[j]+1: dp[i] = dp[j]+1 return dp n = int(input()) a = list(map(int, input().split())) dp = f(.. 2023. 10. 4. 이전 1 다음 반응형