programmer life guidance 101

www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 8696 3378 2574 43.421% 문제 반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다. 예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의..

Longest Increasing Subsequence) 최장 증가 부분 수열 임의의 수열이 주어졌을 때, 이 수열에서 몇 개의 수 들을 선택해 부분수열을 만들 수 있는데, 이 때 만들어진 부분수열 중 오름차순으로 정렬 된 가장 긴 수열을 최장 증가 수열이라고 한다. 여기서의 부분 수열은 반드시 연속적이거나 유일하지 않아도 된다. 예를 들어 arr[ ] = {10, 20, 10, 30, 20, 50}의 수열이 있다고 할 때 여기서의 LIS는 {10, 20, 30, 50}이고 길이는 4일 것이다. 이제 이를 O(N2)과 O(nlogn)의 시간복잡도를 가지는 두 가지 방법을 알아보자. 1. DP 풀이 과정은 아래와 같다. i번째 인덱스에서 끝나는 최장 증가 부분 수열의 마지막에 arr[k]를 추가했을 때의 ..