알고리즘매일매일

https://www.acmicpc.net/problem/2352

1번 포트부터 n번 포트까지 연결이 꼬이지 않게 최대로 연결해야 하는 문제로 최장 증가수열문제이다.

12015번 가장 긴 증가하는 부분 수열 2 문제(문제 링크)와 똑같은 코드로 nlogn만에 풀 수 있다.

(12015번 문제 풀이 링크)

https://www.acmicpc.net/problem/12738

12015번 가장 긴 증가하는 부분 수열 2 문제(문제 링크)와 거의 똑같은 LIS 문제이다. (12015번 문제 풀이 링크)

두 문제의 차이는 수열의 값의 범위뿐이다. 이번 문제에서는 범위가 (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) 으로 처음에 벡터에 넣어놓는 값으로 -1,000,000,000보다 작은 값을 넣어놓기만 하면 된다.

https://www.acmicpc.net/problem/12015

LIS 문제이지만 11053번 가장 긴증가하는 부분 수열문제처럼 dp로 풀 수 없다.

dp로 풀면 시간 복잡도가 n제곱이 나오는데 이 문제는 n의 최댓값이 1,000,000이므로 n제곱으로 풀면 시간초과가 난다.

이분 탐색을 이용하여 nlogn만에 풀 수 있다.

0. 우선 입력으로 들어오는 최솟값보다 작은 값을 벡터에 넣어놓고 시작한다.

1. 값을 입력 받는다.

- 벡터의 맨 마지막 값보다 크다면(증가하는 순서라면) 입력받은 값을 벡터에 넣는다.

- 그렇지 않다면 이분탐색으로 벡터에 입력받은 값 이상의 값이 처음으로 나타나는 위치에 입력받은 값을 넣어준다.

(lower_bound를 이용하여 쉽게 구할 수 있다. )

2. 입력이 끝나면 벡터의 사이즈 -1한 값이 가장 긴 증가하는 부분 수열의 길이가 된다.

(처음에 넣어 놓은 값을 제외하기 위해 1을 뺀다)

https://www.acmicpc.net/problem/11053

문제 제목 그대로 가장 긴 증가하는 부분 수열 LIS (Longest increasing Subsequence) 문제이다.

일반적으로 dp 식을 사용해서 풀 수 있다.

dp[i]는 수열의 i번째 값을 마지막으로 하는 가장 긴 증가하는 부분 수열이다.

dp[i]값을 구하기 위해서는 첫 번째 값부터 i-1번째 값( j )까지를 검사한다. -> 시간 복잡도는 n제곱이 된다

(먼저 dp배열은 자기 자신을 부분 수열로 하면 최소 길이가 1이므로 1로 초기화해준다)

1. j번 수열의 값이 i번 수열의 값보다 작고 (증가하는 수열이어야 하므로)

2. dp[j]값은 현재 dp[i]값보다 같거나 커야 한다(가장 긴 수열)

위의 조건을 만족한다면 dp[i] 는 dp[j] + 1 값을 가지게 된다(수열의 길이가 1 늘어남) 

문제에 나온 예시를 그림으로 보면 처음에 첫 번째 값(i가 0)인 10은 최대 길이가 1이므로 1인 상태로 다음 수열로 넘어간다.

수열의 다음 값(i가 1)은 20인데 앞의 값은 10 밖에 없다. 10은 20보다 작고 dp값도 같기 때문에 dp[i]값은 +1 된다.

그다음 값은 10인데 앞의 값들(10과 20) 중 10보다 작은 값이 없으므로 길이는 그대로 자기 자신인 1이 된다.

그리고 i는 증가해서 30 값을 가리킨다. 현재 i가 3이므로 0번부터 2(i-1) 번까지의 값을 보면 된다.

0번부터 2번까지의 값은 각각 10, 20, 10으로 모두 30보다 작다.

이중 dp배열의 가장 큰 값+1이 dp[i]값이 되므로 dp[1]값인 2에서 1을 더한 3이 dp[3]에 저장된다.

i값이 4가 되고 이제 j는 0부터 3까지의 값을 검사한다.

이 중 20보다 작은 값은 0번째와 2번째이다. 둘 다 10이고 dp의 값도 1로 현재 dp[i]와 같으므로 dp[i]는 dp[j]에 1을 더한 값인 2가 된다.

마지막 값인 50과 앞의 값들을 비교해보면 모두 50보다 작다. 그러므로 가장 큰 dp값인 dp[3] + 1 한 값인 4가 dp[5]에 저장된다.

마지막 값이 작은 값인 경우에는 마지막 위치에 최댓값이 저장되지 않을 수 있으므로 dp배열을 모두 검사해서 최댓값을 찾아야 한다.