백준 알고리즘 강의 후기(코드플러스): 세그먼트 트리와 펜윅 트리
1230 - 세그먼트 트리
11/20 [세그먼트 트리] RMQ ( Range Minimum Query )
공부할땐 앞에 방법도 괜찮지만, 대회에서는 최소값 구할때 무조건 세그먼트 트리. 왜냐하면 이것은 O(sqrt(N))을 O(logN)으로 줄인것이기 때문이다.)
DP는 변경이 복잡해서 세그먼트트리가 무조건 좋다. 매우 중요한 자료구조니까 꼭 스스로 코딩해보세요.
11/23 [참고] 잠이와서 좀.. 소스코드 특히 다시 한번 보자.
12/13 필기하던거 다 날아감.ㅠㅠ
1. 루트N으로 나누기 sqrt decomposition
2. dp - 트리2에서 LCA랑 비슷하다.
앞쪽과 뒷쪽으로 나누는 dp
3. 세그먼트 트리 : 가장 좋은 방법 ( lgN) : 1,2번은 공부용으로 괜찮지만 실제는 무조건 세그먼트트리를 이용해야 한다.
post order
<참고>강의:
첫번째 주제: LCA를 세그먼트트리로 풀기
1. 프리오더로 모든 정점을 기록한다(abcbd이런식으로 돌아온정점도 모두 기록) 1+(n-1)x2 = 2n-1
2. 방문하면서 깊이도 같이 기록한다. 그런데 처음 방문했을때 순서도 기록한다.
3. 찾기, u와 v가 첫 등장한 인덱스 사이에서 깊이가 최소인 정점
두번째주제: 세그먼트 트리의 비재귀 구현-> 속도가 빨라서 사용하는 사람들 많다.
왼쪽의 오른쪽자식, 오른쪽의 왼쪽자식 인 경우에 점프하고, 아니면 그냥 올라다가 교차할때 그만두면됨.
1240 - 펜윅 트리
- 구간 합 구하기 4 : 구간합을 알려줌
- 수들의 합 4: 구간합 diff로 구해도 o(N^2)인것이 문제.
- 변수 cnt[k]를 만들고, 카운트를 해준다음 합이 k가 되는것을 리턴하면된다.
- 나머지 합 :
- 구간 합 구하기 5 // 여기까지가 누적합
- 구간 합 구하기 // 여기부터 펜윅트리
- 구간 합 구하기 3
11/23 [누적합], [펜윅트리]
12/13
세그먼트트리는 최소, 최대, 합을 구할수 있는 반면 펜윅트리는 합을 구할때만 쓴다.
누적합은 간단하지만 변경을 처리하는게 o(N)이다 어떤 값이 바뀌면 그 뒤에를 전부 업데이트 해야하기 때문이다.
2차원누적합.3차원누적합. 모두 포함배제의 원리를 이용해서 구한다. Inclusion-exclusion
다음동영상. 펜윅트리: 최소값을 구할때 사용할 수 없고, 합을 구할때만 사용할 수 있다.
펜윅트리는 누적합과 같지만 업데이트가 훨씬 빠른 lgN이어서 이용하는것이다. leetcode.com/tag/binary-indexed-tree/
2차원펜윅트리
그림보면 복잡하고 그냥 코드로
1차원배열의 1차원배열이 2차원인것처럼, 1차원펜윅트리의 1차원펜윅트리가 2차원펜윅트리다.
1600 - 세그먼트 트리와 펜윅 트리
- 가장 긴 증가하는 부분 수열 2
- 가장 긴 증가하는 부분 수열 3 : 2번과 비교해 수가 너무 크다. 총 20억개라 트리를 만들 수 없다.
- 대소관계를 이용해서 1~N으로 치환한다. 이것을 좌표압축으로 부르고 기하에서 쓰인다.
- NlgM -> NlgN 으로 바뀐다. // 1강 끝
- 공장 // 2강 시작
- 쌍의개수를 세는 문제는 기준을 하나 구해서, 즉 j를 기준으로 그 식을 만족하는 i가 몇개있는지 세어보는것.
- A[i] < A[J] 일때, B[i]>B[J]인것
- 합을 구할 때는 세그먼트 트리와 펜윅트리중에 펜윅트리가 더 빠르다.
- 영화 수집 : 배열해서 이용하면 O(NM)
- 왜 Mlg(N+M)인건가, 펜윅트리라서 그렇다.
- 수열과 쿼리 37 합구하기 강의 보다 말음
- 음주 코딩
- 사탕상자 : 여기부터 k번째 찾기 강의
- 순열
12/13 3가지 응용이 존재한다.
1. 최소값 찾기
2. 합
3. 위의 합을 이용해서 k번째를 찾는 문제
Longest Increasing Subsequence LIS는 O(N^2) dp문제, D[i] = A[i]가 마지막인 LIS의 길이 <- 너무 크다.
세그먼트 트리를 이용하면 되는데, 세그먼트 트리를 이용하는 문제들은 트리에 어떤수를 저장해야하는지 결정해야 한다.
기준은 3가지인데, 세그먼트트리를 이용하려면 구간이 나오도록 해야한다.
- 앞에있으면서 <- 이 조건은, 앞에서부터 차례대로 풀면 된다는 뜻.
- 작은 수 <- 구간으로 볼수 있다. A[i] = [1, A[i]-1]
- LIS길이의 "최대"
dp처럼 인덱스로 하면 안되고, tree[i] = 수 i를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이로 정의함.
8분쯤에 A[i]로 증가하는 부분수열 tree[i]만드는 부분 와우..함.
2강 합구하기: 세그먼트 트리와 펜윅트리를 이용.
1601 - 세그먼트 트리와 펜윅 트리 (연습)
1602 - 세그먼트 트리와 펜윅 트리 (도전)
1610 - 세그먼트 트리와 펜윅 트리 2
1611 - 세그먼트 트리와 펜윅 트리 2 (연습)
1612 - 세그먼트 트리와 펜윅 트리 2 (도전)
