기존의 DP 방법으로 풀이를 하면, 각 나오는 숫자마다 이전의 모든 증가수열에 들어가는지 여부를 확인해야 해서 O(N^2)이 걸린다.
LIS는 이진 탐색을 이용해 이 확인 과정을 O(n)에서 O(logn)으로 줄여 총 O(nlogn)만에 문제를 해결할 수 있게 했다.
먼저 새로운 배열 L을 만든다.
이 L에는 원소들이 정렬되어 있어 이진 탐색이 가능하다.
L의 각 자리에는 해당 길이를 가지는 증가 수열의 마지막 원소(해당 수열에서 가장 큰 수) 중 가장 작은 원소가 저장된다.
그리고 lower bound라는 개념이 새로 나오는데, lower bound란 배열에서 자기 자신보다 큰 최소 숫자를 말한다.
LIS를 찾는 알고리즘에서는 이진 탐색을 통해 lower bound를 찾는다.
1. 처음에 L에 배열의 첫 원소를 넣는다.
2. 반복문을 돌면서 L의 맨 마지막 요소와 arr[i]를 비교한다. 만약 arr[i]가L의 마지막 요소보다 크다면, 이는 이제까지 나온 가장 긴 증가수열의 가장 큰 요소보다 arr[i]가 더 크다는 뜻이므로, arr[i]를 LIS의 맨 뒤에 추가하면 LIS의 길이를 하나 더 늘릴 수 있다는 뜻이다.
따라서 L의 마지막에 arr[i]를 추가한다.
3. 만약 L의 마지막 원소 > arr[i]라면 L의 원소중 arr[i]의 lower bound(L[j]라고 하자)를 찾고, 이를 arr[i]로 교체한다. 이를 찾는 이유는 L에서 arr[i]의 lower bound 이전의 수(L[j - 1])는 arr[i]를 마지막으로 가지는 증가 수열이다. 그런데 여기에 arr[i]를 추가해 길이가 j가 된다면, j의 길이를 가지는 증가수열의 마지막 수 중 가장 작은 수는 arr[i]가 되기 때문이다.
이를 반복해 주면 결국 L의 길이가 수열에서 LIS의 길이가 된다.
3. 배운 점
탐색 -> 이진탐색 주로 사용
이진 탐색하려면 -> 정렬 내지 정렬된 배열 필요 (정렬을 할 필요가 없을 수도 있다는 뜻)
n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai+ aj= x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.
> 풀이
idea 1) memorization
길이가 k+1인 배열을 만들고 (memory[x+1], memory[x]에 쌍 개수 저장할 것)
입력받은 숫자들을 하나씩 순회하며 (arr[0]~ arr[n-1])
만약 memory[]의 그 숫자에 해당하는 칸이 존재한다면 (memory[arr[i]]) 1을 집어넣는다.
그리고 memory[x - arr[i]] 에 1이 담겨 있다면, 쌍이 존재한다는 의미이므로 memory[x]의 값을 1 증가시킨다.
memory[x]의 값을 출력한다.
이처럼 길이가 x+1인 배열을 만들고, 두 수의 합으로 x를 만들 수 있는 쌍이 ai, aj가 다르면 유일하다는 점을 이용해 memory에 각각 x를 구성하는 ai - aj가 존재함을 저장해 ai마다 x를 만들 수 있는 aj가 있는지 확인하는 방법으로 문제를 해결할 수 있다.
// Baekjoon No. 3273 두 수의 합
// Time Complexity O(n)
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, x;
int i;
cin >> n;
vector<int> arr(n);
for (i = 0; i < n; i++)
cin >> arr[i];
cin >> x;
vector<int> memory(x + 1, 0);
// solving
for (i = 0; i < n; i++) {
if(arr[i] < x)
memory[arr[i]] = 1;
if (x - arr[i] > 0 && arr[i] * 2 != x && memory[x - arr[i]])
memory[x] ++;
}
cout << memory[x];
return 0;
}
idea 2) 투 포인터
그리고 문제 유형에 적혀 있는 투 포인터 방식을 이용하는 방법이 있다.
쌍 개수를 저장할 cnt 변수를 0으로 초기화한다.
배열 arr[]에 ai 값들을 입력받는다.
arr[]을 오름차순 정렬한다. (시간복잡도 O(nlogn)
정렬한 arr에서 arr[0]이 arr[n-1]이랑 더했을 때 x보다 큰지 작은지 확인한다.
만약 그 값이 x보다 크다면, arr[0] + arr[n - 1 - i] 가 x보다 작거나 같을 때까지 i를 0부터 증가시킨다. (arr의 오른쪽 idx--)
만약 그 값이 x와 같다면, cnt++, arr의 오른쪽 idx -- (또는 왼쪽 idx ++)
만약 그 값이 x보다 작다면, arr의 왼쪽 idx ++
이대로 arr의 오른쪽 idx와 왼쪽 idx가 겹칠 때까지 반복을 수행한다.
언뜻 보면 arr[l] (왼쪽 idx)를 증가시켰을 때 arr[r]과의 합이 x보다 커버리는 경우가 생길 수도 있다고 생각할 수 있지만, 애초에 arr[l]을 증가시키는 경우는 arr[l] + arr[r] < x인 경우이므로 이 경우에는 r--을 해주어야 한다.
> 결론
- 투 포인터를 이용하면 O(nlogn), memorization을 이용하면 O(n)
- 배열을 다룰 때 idx 범위를 조심할 것 (memorization에서 0 < arr[i] < x, 2*arr[i] != x)
1. 첫 번째 풀이 : 처음에는 이전의 계단 오르기 문제랑 동일하다고 생각해서 그때의 문제풀이를 바탕으로 arr[i]에 wines[i-1] + arr[i-3] 이랑arr[i-2]랑 더 큰 수를 더하는 방법을 사용했다. 그런데 이렇게 문제를 풀면 반례가 존재하여 문제풀이에 성공할 수 없었다.
2. 두 번째 풀이 : 질문에 있던 반례를 참고하여 1.에서 사용했던 방법은 2개의 포도주를 건너뛸때 반례에 걸린다는 것을 이해했다. 그래서 arr[i] 에 wines[i] + wines[i-1] + arr[i-3] 이랑 wines[i] + arr[i-2], wines[i] + wines[i-1] + arr[i-4]중 제일 큰 수를 더해주는 걸로 고쳤다.
* 그리고 arr[n-1] 이랑 arr[n-2]랑 마지막에 비교해서 출력해줘야 하는데, 그건 arr[n-2]가 최고인 경우도 존재하기 때문이다.(arr[n-1]에 1을 마지막에 붙인 경우)
> 느낀 점
같은 유형에 비슷한 조건이라고 해서 문제풀이까지 완전히 똑같지는 않다는 것을 깨닫게 되었다. 앞으로는 비슷한 유형의 문제를 보면 그 풀이를 그대로 따라하지 맣고 참고만 하여 새로운 문제풀이 방법을 만들어낸다는 생각으로 PS를 진행해야겠다.
문제 요약 : 총 n개의 방문자 수가 주어질 때, x일간 방문한 최대 방문자수와 그 방문자수가 있는 구간의 개수를 구하여라.
> 풀이들
첫 번째 풀이 : 구간 x 안에 있는 사람들의 합을 각각 구하고, 그걸 n - x + 1번만 반복하면 되는 줄 알았다. 하지만 시간 초과가 떠서 다른 방법을 생각해야만 했다. (시간 복잡도가 O(n-x+1) * O(x) => O(x*n)이 나와버림)
두 번째 풀이 : 구간 x 안에 있는 사람들의 합을 DP를 이용해 구하면 O(1)만에 구할 수 있다. arr[0] = arr[0], arr[1] = arr[0] + arr[1], arr[2] = arr[2] + arr[1], ... 이런 식으로 가다 보면 i번째부터 i+x-1번째 사람까지의 합은 arr[i+x-1] - arr[i-1]이다. => O(1)만에 해결 가능!
