1517번
각 숫자 보다 오른쪽에 큰 숫자가 몇개있는지 구해서 다 더하면 될거 같다.
생각 나는 방법1.
그냥 오른쪽으로 쭉 가면서 갯수를 다 세어본다. -> 이건 시간초과;
문제 카테고리상 세그먼트 트리이다.
세그먼트 트리는 분할 정복의 느낌이 조금 있는거 같다.
음 모르겠다. 노드 두개를 병합해서 새로운 노드를 만들때 어떠한 정보를 저장해야 답을 구할 수 있을 텐데 그것을 모르겠다.
12015번 : LIS 방법
6
10 20 10 30 20 15
1 2 1 2 1 1
1 2 1 3 2 2 dp[n] : n번째까지 가장 긴 부분 수열의 길이. dp[n] = (이전에 가장 긴 부분 수열의 연장됨(가장 긴 수열의 마지막 위치와 수를 저장하자) , 현재의 n번째가 처음 시작 수열로 한다)
dp에 도대체 무슨 값을 저장해야 되는 걸까?
현재 위치에서 현재 위치 앞에 자기보다 가장 가까운 값의 위치를 찾아야한다.
-> https://seungkwan.tistory.com/8
가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence)
어떠한 수열에서 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence)를 찾는 문제는 꽤나 유명한 문제입니다. 다이나믹 프로그래밍을 공부할 때 예시로 자주 나오는 문제이고, 프로그래밍 대회에도 종종..
seungkwan.tistory.com
보니까 dp는 원래 n^2이였다.
블로그는 dp까지만 읽어 보고 아래는 안봤다.
세그먼트 트리를 사용해서 logn으로 다시 해보자.
현재 노드의 lower bound를 찾아야한다.
근데 세그먼트 트리로 특정 값의 lower bound를 저장하는게 말이 되나. 그래서 블로그에서는 이분 탐색으로 logn 시간에 현재 노드의 lower bound를 찾는거 같다. 근데 이게 정렬 안되있는데 찾을 수 있나?
새로운 알고리즘인데 한 50프로 밖에 이해가 안된다.
L[i]를 i 길이로 만들 수 있는 증가하는 부분 수열에서 현재 위치(마지막)에 올 수 있는 원소들중 가장 작은 값을 저장한다.
L[i]로는 단지 가장 긴 부분 수열의 길이만 알 수 있다.
arr[i]는 i에 주어진 수를 저장한다.
그리고 P[i]를 통해서 해당 수열을 찾는다. P[i]는 i번째 배열의 L에서의 인덱스를 저장한다.
그러므로 찾을때는 최종적으로 L에서 갱신된 것을 가져오면 되므로 백트레이스 방법으로 구한다.
이 방법을 보고 생각한건 구하려는 부분 수열을 저장하는 새로운 배열을 만들고 저장하는 방법을 이분탐색을 이용할 수 있도록 한 것이 매우 인상 깊었다............
12015번 : 세그먼트 트리 방법 ?
https://www.geeksforgeeks.org/lis-using-segment-tree/
LIS using Segment Tree - GeeksforGeeks
You are given an array of integers, you need to find the length of the longest increasing sub-sequence. There can be 4 approaches for solving… Read More »
www.geeksforgeeks.org
봐도 이해가 잘 안된다 ㅠㅠ
'알고리즘 문제 풀기' 카테고리의 다른 글
| 백준 1103번 게임 , 1256번 사전 (0) | 2020.02.10 |
|---|---|
| 백준 2504: 괄호의 값, 1722번 순열의 순서, 13251번 조약돌 꺼내기. (0) | 2020.02.07 |
| 백준 : 4358번 생태학 ,17837번 새로운 게임2 (0) | 2020.01.25 |
| 프로그래머스 - 가장 먼 노드, 정수 삼각형 (0) | 2020.01.23 |
| 백준 9934번: 완전 이진 트리 / 프로그래머스(카카오) : 길 찾기 게임 / 백준 12909번: 그래프 만들기. (0) | 2020.01.21 |