늘 겸손하게

목차 문제명 문제풀이 코드 백준 2565 전깃줄 문제 유형 : LIS (Longest Increasing Subsequence, 최장 증가 부분 수열) 난이도 : 골드 5 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, 과 같..

LIS Longest Increasing Subsequence의 약자 최장 증가 부분 수열 길이가 N인 배열의 원소들을 골라 만든 부분 수열 중, 부분 수열의 원소들이 모두 오름차순으로 정렬되어 있고 가장 길이가 긴 수열이 '최장 증가 부분 수열' 예로, [ 6, 9, 1, 4, 10, 2, 3, 7]의 최장 증가 부분 수열은 [1, 2, 3, 7] 최장 증가 부분 수열의 길이 구하는 방법 1. dp 2. 이분 탐색 1. dp 가장 단순한 방법이지만 O(N^2) 시간복잡도를 가져 배열의 길이가 긴 경우에는 비효율적인 방법 numbers = [ 6, 9, 1, 4, 10, 2, 3, 7] def LIS(arr): N = len(arr) dp = [1 for _ in range(N)] for i in ran..