Lis2 [S2] 백준 11568 - 민균이의 계략 (Python3) https://www.acmicpc.net/problem/11568 해결방법 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)의 기초 문제이다. 이전에 이 시리즈를 풀어본 경험이 있어서 풀이의 틀은 쉽게 잡았다. 나는 시간복잡도가 O(n^2) 인 알고리즘으로 문제를 풀었다. arr의 길이가 최대 1,000 이므로 O(n^2)은 1,000,000이라 제한시간(1초) 안에 충분히 통과가 가능하다. 더 빠른 방법은 O(n log n) 있다. n=1000 일때, n log n = 3000 이므로 더 빠르게 통과할 것이다. 풀이 이 문제의 풀이는 arr에 있는 각 원소를 주목해야 한다. arr에 있는 원소들을 반복문으로 앞에서부터 차례차례 접근할 것이다. 이때 그 원소가 이 .. 2023. 1. 15. [2022 하계 모각코] 7주차 1회 계획 및 결과 7주차 1회 계획 : 최장증가부분수열(LIS) 탐구 이번주는 최장증가부분수열알고리즘에 대해 탐구할 계획이다. 평소에는 기존에 알고 있는 알고리즘에서 확장적으로 알아나가려 했다. 이번 기회에 전혀 모르던 알고리즘을 집중적으로 파고들어 보았는데, 정말 신선한 경험이었다. 최장증가부분수열(LIS, Longest Increasing Subsequence)이란? 주어진 수열에서 순서대로 증가하는 가장 긴 부분수열이다. 예로 알아보자. '1, 2, 7, 4, 3, 9' 의 수열이 있다. 증가하는 부분수열을 뽑아보면 '1, 7, 9', '2, 7, 9', '4, 9', '2, 4', ... 가 있다. 이 부분수열들 중 길이가 가장 긴 수열이 바로 최장증가부분수열이다. 위에서 주어진 수열에서의 LIS는 '1, 2, 7.. 2022. 8. 10. 이전 1 다음
