문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다. 풀이 DP를 사용하여 LIS를 구하는 기존 문제에 부분 수열의 길이뿐만 아니라 부분 수열을 요소까지 출력하는 문제이다. 따라서 증가하는 부분 수열의 요소를 담는 것을 함께 구현해야 한다. 증가하는 부분 수열의 요소를 담는 리스트를 생성하고 dp가 증가할 때 함께 업데이트 되도록 한다. 알고리즘 n과 a 수열을 입력받는다. 1로 초기화된 dp를 생성한다. 부분 수열의 요소를 담을 b 리스트를 생성한다. A 수열에서 뒤의 요소가 앞의 요소보다 크고 부분 수열의 길이도 더 길어질 때, 부분 수열의 길이를 업데이트 하면서 부분 수열의 요소도 업데이트 해준다. 가장 긴 부분 수열의 길이를 찾아 출력하고, 해당 위치와 동일한 부분 수열의..
[백준 BOJ / Python] 1965번 상자넣기 DP
문제 상자의 크기가 입력된 배열이 주어졌을 때, 앞에서부터 작은 상자를 뒤의 큰 상자에 넣는다면 최대 몇 개의 상자를 겹칠 수 있는지 개수를 묻는 문제이다. 풀이 왼쪽의 작은 상자를 오른쪽의 큰 상자에 넣는다는 것은 오른쪽으로 이동하면서 오름차순으로 증가하는 상자를 골라야 한다고 말할 수 있다. 즉, 상자배열 내에서 가장 긴 증가하는 부분 수열 (LIS) 을 구한다면, 겹칠 수 있는 최대 상자의 개수를 알 수 있다. 알고리즘 겹치는 상자의 개수를 담는 dp 를 1로 초기화한다. 상자의 크기가 담긴 box 배열을 순회한다. 해당 상자의 이전에 있는 상자들과 비교하면서 담을 수 있는 상자라면, 이전 상자에 담기는 상자의 개수(dp[j])에 1을 더한 값과 현재 dp[i]에 담긴 값을 비교하여 더 큰 값을 d..
[백준 BOJ / Python] 2565번 전깃줄 DP
문제 두 전봇대 A와 B 사이에 몇 개의 전깃줄을 제거해야 교차하는 전깃줄이 없는지 구하는 문제이다. 즉, 최소한의 제거할 수 있는 전깃줄의 개수를 도출해야 한다. 풀이 서로 전깃줄이 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구해야 한다. 예를 들어, A-1번과 B-8번이 연결된 전깃줄보다 A-3번과 B-9번이 연결된 전깃줄이 더 아래 있는 것을 알 수 있다. 이를 통해 A의 번호가 순차적으로 커질 때, 각각의 A와 연결된 B의 번호도 더 커진다면 교차하지 않는 전깃줄의 개수를 구할 수 있음을 알 수 있다. A의 정렬된 번호를 리스트의 인덱스로 두고, B의 번호를 가지고 가장 긴 증가하는 수열(LIS)을 구함으로써 교차하지 않는 전깃줄의 최대 개수(c)를 구할 수 있다...
[알고리즘 / Python] 가장 긴 증가하는 부분 수열 (LIS)
가장 긴 증가하는 부분 수열 알고리즘 이란, 왼쪽에서 오른쪽 방향으로 탐색할 때 오름차순으로 증가하는 부분 수열 중 가장 길이가 긴 부분 수열을 찾는 알고리즘이다. 0 1 2 3 4 5 6 10 40 20 50 30 40 60 위의 리스트에서 증가하는 부분 수열은 {10,40,50,60}, {10,20,50,60}, {10,20,30,40,60}, {40, 50, 60} 이 있다. 여기서 가장 긴 증가하는 부분 수열은 {10,20,30,40,60}이며, 부분 수열의 길이는 5가 된다. LIS 알고리즘은 두 가지 방법으로 구성될 수 있다. DP 활용 방법 이분탐색 활용 방법 1. LIS 알고리즘 (DP 활용) 시간복잡도: O(N**2) 1.1. DP 초기화 DP에는 부분 수열의 길이가 담기기 때문에 DP는..