etc - GitDeveloperKim/DreamEach GitHub Wiki

• 응용해서 같이 나올만한 기타 알고리즘 정리

희소테이블 (sparse table)

• sparse table 확인 필요 click
• Sparse Table 에서 arr[i][j] = arr[ arr[i][j-1] ][j-1]
• j 값은 총 log2(노드 수) 로 계산
• 총 15칸 올라가야 한다면 (8칸 -> 4칸 -> 2칸 -> 1칸)
• 메모리를 조금 더 사용하여 각 노드에 대하여 2^i 번 부모에 대한 정보를 기록 / 시간복잡도 O(MlogN)
• click
• click
• click

스위핑

• TBD
• 백준 2170

투포인터

• 리스트에 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리하는 알고리즘

1. 시작점(start)과 끝점(end)의 첫번째 원소의 인덱스를 가리키도록 한다.
2. 현재부분 합이 M과 같다면, 카운트 한다.
3. 현재 부분합이 M보다 작다면 end를 1 증가 시킨다
4. 현재 부분합이 M보다 크거나 같다면, start를 1 증가 시킨다
5. 모든 경우를 확인할 때까지 2번부터 4번까지 과정을 반복한다

• 백준3273
• 3273 소스코드

sliding window

-TBD

접두사 합

• 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해놓은것

1. N개의 수 위치 각각에 대하여 접두사 합을 계산하여 P에 저장
2. 매 M개의 쿼리 정보를 확인할 때 구간합은 P[Right] - P[Left-1]

• 10, 20, 30, 40, 50
• 0, 10, 30, 60, 100, 150

1. left=1, right=3 -> p[3] - p[0] = 60
2. left=2, right=5 -> p[5] - p[1] = 140
3. left=3, right=4 -> p[4] - p[2] = 70