본문 바로가기

알고리즘

 (405)
DP/최단거리 역추적. [14002] [3. 코드]
동적 계획법 - 예제5 [1. 문제 설명] [2. 풀이 접근] [3. 코드]
스위핑/구간트리. [3392] [1. 문제 설명] [2. 풀이 접근] [3. 코드]
원형 큐 [1. 구현 시 유의 사항] 최초 head 와 tail 은 같은 곳을 가리키고 있으며, 이는 empty 한 것을 의미한다. 새로운 원소를 push 할 때, 현재 tail 에 다음에 저장한다. 새로운 원소를 push 할 때, 현재 tail 의 다음이 head 인 경우 queue 가 full 하므로, 푸쉬 할 수 없다. pop 할 때는 head 를 앞으로 한 칸 움직인다. pop 할 때 head 와 tail 이 같은 경우, queue 가 empty 하므로 pop 할 수 없다. 길이 N 만큼을 위한 원형 큐를 생성 할 때, 실제 배열의 길이는 N+1 이 되어야 한다. full 한 경우와 empty 한 경우를 비교하기 위해, 한칸이 비어있어야 한다. head 와 tail 을 앞으로 옮길 때 에는 반드시 모듈러 ..
스위핑/구간트리. [17131] [1. 문제 설명] [2. 풀이 접근] [3. 코드]
펜윅 트리 - 예제 1 [1. 문제 설명] [2. 풀이 접근] [3. 코드]
펜윅 트리 [1. 개요] 구간 합을 빠르게 구하기 위한 구간 트리의 상위 버전으로 볼 수 있는 자료구조 구간 합 대신 부분 합만을 빠르게 계산 할 수 있는 자료 구조를 만들어도 구간 합을 계산 할 수 있다. => 구간 트리가 미리 계산해 저장하는 정보의 상당수가 필요 없다. 하나의 긴 구간 밑에 두 개의 작은 구간이 있을 때, 이 두 구간 중 오른쪽 구간은 항상 지워도 된다. => 필요한 구간의 수는 정확하게 N 개이다. => 구간 트리가 보통 4N 개가 필요하다고 했을 때, 메모리를 조금이라도 덜 사용한다. 또한, 각 구간이 포함하는 오른쪽 끝 원소들이 모두 다르다. => 구간 트리에서 (0, 7) (4, 7) 등 끝나는 구간이 같은 것이 다수 존재함. [2. 구현] tree[i] = 오른쪽 끝 위치가 A[i] ..
좌표 압축 [1. 개요] 매우 넓은 범위의 값이 있지만, 그 개수가 다소 적은 경우 값을 정렬한 뒤, 해당 값을 전체 원소 개수 내 값으로 재매핑하여 표현 [2. 관련 예제] https://testkernelv2.tistory.com/421
스위핑/구간 트리. [5419] [1. 문제 설명] 북서풍으로 인해 현재 위치에서 동쪽과 남쪽 사이의 위치로만 이동 할 수 있을 때 북서풍을 타고 항해 할 수 있는 섬의 쌍의 수를 구하도록 한다. [2. 풀이 접근] 먼저 전체 좌표를 y 의 내림차순으로 정렬한다. 그러면 이전 좌표는 신경쓰지 않아도 된다. 현재 위치에서 남쪽으로만 갈 수 있지, 북쪽으로는 갈 수 없기 때문이다. 이 상태에서 x 를 처리하도록 한다. 기본적인 생각은 x 의 발생 빈도를 구간 트리로 처리하는 것이다. 아래 그림에서 2번 좌표는 최소 31 번까지의 좌표로 이동 할 수 없다. 남쪽으로는 갈 수 있지만, 서쪽으로 이동 하기 때문이다. 즉, 남은 구간에서 현재 x 보다 큰 것의 개수만 구할 수 있다면, 현재 섬에서 동남쪽으로 이동 할 수 있는 점의 개수를 찾을 수..
구간 트리 - 예제 1 [1. 문제 설명] N 개의 표지판에 각 위치 마다 해발 고도가 적혀있고, Q 개의 구간에서 최대 고도와 최소 고도의 차이가 해당 구간의 난이도 일 때 각 구간 별 난이도를 출력하도록 한다. [2. 풀이 접근] 구간 트리가 각 구간 별 고도의 최대/최소를 저장 하도록 한다. 구간 트리를 초기화 하는데 걸리는 시간 : O(N) Q 개의 구간을 조회하는데 걸리는 시간: O(QlogN) [3. 코드]

티스토리툴바