민균이의계략1 [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. 이전 1 다음
