LIS2 [BOJ 2352] 반도체 설계 https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자. www.acmicpc.net 위 그림에서 왼쪽의 포트가 연결된 오른쪽 포트의 번호를 A[i]라고 하고, 선택된 오른쪽 포트를 모아놓은 리스트를 L이라고 두면, 가장 많은 포트를 고르기 위해서는 리스트 L의 원소들이 정렬되어 있는 상태에서 크기가 가장 커야 한다. 예를 들어, 왼쪽 포트 1부터 차례대로 선택할 때, 오른쪽의 3번 포트가.. 2020. 4. 8. 가장 긴 증가하는 부분 수열, LIS(Longest Increasing Subsequence) LIS는 어떠한 수열에서 증가하는 부분 수열중 길이가 가장 긴 수열를 뜻합니다. LIS를 찾는 알고리즘은 다이나믹 프로그래밍을 이용한 O(N^2) 알고리즘과 이보다는 좀 더 복잡한 O(N log N) 알고리즘이 있습니다. 부분 수열이란 어떠한 수열에서 일부 숫자를 지워서 만들 수 있는 새로운 수열을 의미합니다. O(N^2) O(N^2) 알고리즘은 비교적 간단하게 구현할 수 있습니다. dp[i] = i 번째 원소를 마지막으로 하는 LIS의 길이 dp[i]를 구하는 법은 1 ~ (i - 1)까지의 원소들 중 i번째 원소보다 값이 작은 것들 중 dp의 값이 가장 큰 것에 1을 더하면 된다. 즉, j = 1 ~ (i - 1)을 순회할 때, a[i]보다 a[j]가 작다면, dp[i] = max(dp[i], dp[.. 2020. 4. 7. 이전 1 다음
