HJW's IT Blog

Segment Tree는 배열과 같은 자료구조에서 주어진 구간의 질의를 빠르게 처리하기 위해 사용되는 자료구조 이다. Segment Tree는 트리구조를 사용하여 구간을 나누어 저장하며 각 노드는 자식노드들의 정보를 이용하여 자신의 정보를 계산한다. 다음은 segment tree 의 예제인데, 노드 내부의 숫자는 어디서부터 어디까지의 합을 나타내는지를 보여준다 Segment Tree 에서 - 리프노드: 배열의 수 그 자체 - 다른 노드: 왼쪽, 오른쪽 자식의 합 Segment Tree로 특정구간 [a,b] 의 합을 구하려면 다음을 점검한다. [a,b] 와 [left, right] 이 겹치지 않는다 do nothing [a,b] 가 [left, right] 을 포함 미리 구해둔 [left, right]의 ..

욕심쟁이 기법은 최적해를 구하는데에 사용되는 알고리즘중 하나로, 매 단계에서 가장 최선의 선택을 하여 최종 결과물이 최적해에 가까워 지도록 하는것이다. 욕심쟁이 기법은 매우 직관적이며 구현하기 쉽지만 최적해를 보장하지는 않는다. 예시) 회의실 배정 문제 한 개의 회의실이 있는데, n개의 회의 일정이 있고 이 회의실을 이용하여 회의한다. 각 회의 i에 대해 시작시간 Si 와 끝시간 Fi 가 주어진다. 각 회의가 겹치지 않으면서 가장 많은 횟수의 회의를 할 수 있도록 일정을 구하라. 해법: 가장 빨리 끝나는 회의부터 넣는다. 증명: 회의들이 끝나는 시간에 따라 {1,...,n} 이라고 하자. 정답은 1을 포함하거나 포함하지 않는다. 1을 포함하지 않는다면... 정답의 첫번째 답이 1과 겹치지 않는다면 1을 ..

Brute Force Method 자신보다 뒤에 나오는 수 가 자신과 같다면 카운팅 해가며 찾는방법 O(n^2) O(n log n) 방법 원소들을 정렬한다 (O(n log n) 의 시간) 정렬전: 3 1 2 2 1 1 1 1 2 1 3 2 1 1 1 2 정렬후: 1 1 1 1 1 1 1 1 1 2 2 2 2 2 3 3 등장 횟수를 검사하는데에 O(n)의 시간 전체 시간: O(n log n) O(n) 방법: Boyer-Moore 다음과 같이 작동한다: 같은 수라면 skip, 다른 수라면 상쇄 다음 숫자열에 대해 작동 과정을 살펴보자 3 1 2 2 1 1 1 1 2 1 3 2 1 1 1 2 3 1 2 2 1 1 1 1 2 1 3 2 1 1 1 2 (상쇄) 2 2 1 1 1 1 2 1 3 2 1 1 1 2 (..

트리의 지름이란 트리의 두 정점 u 와 v 를 잇는 거리의 최대값이다. 즉, 트리 내에서 가장 먼 두 정점 사이의 거리를 의미한다. Brute-Force Method 모든 가능한 u, v 의 조합을 다 해본다 이 때 걸리는 시간은 O(n^3) --> 비효율적 O(n) 알고리즘 트리에서 임의의 정점 x를 선택한다 x에서 가장 먼 정점 y를 BFS 를 통해 찾는다 y 에서 가장 먼 정점 z를 찾는다 y 와 z 가 가장 멀리 떨어져 있는 정점이다. 위 방법의 증명은 다음과 같다 원하는 답이 u 와 v 라고 하자. 이때, x를 정한 뒤 가장 먼 점이 y라고 한다면 3가지 가능성이 존재한다 x = u (or v) y = u (or v) x,y,u,v 는 모두 다른 경우 x = u (or v) 나 y = u(or ..