(4주차) - 문제해결기법

#부분합 문제

 

& 입력

 : 배열 A[n], 두 정수 a, b( 0 <= a, b < n).

 

& 출력

 : Sum(a,b) = A[a] + A[a+1] + .... + A[b]

 

& 갱신

: Update(i,x) : A[i] = x

 

& Brute-force method

 : No preprocessing(전처리없다고)

 : O(n) in the worst case.

 

 

 

 

#O(n) 전처리, O(sqrt(n)) 질의

 

RMQ에서 루트 n개로 묶어줘서 구할 때와 비슷하다.

루트 n개로 나눠주는 것 까진 같은데, 여기서는 각 구간의 합을 미리 구해놓는다.

 

그 이후 sum(a,b) 질의가 주어지면, 양 끝부분의 합을 직접 구하고, 중간 부분은 이미 구한 값을 더해준다.

 

 

 

 

 

 

 

 

#O(n) 전처리, O(1) 질의

 

 - 미리 값 전부 다 계산 O(n)시간에 PrefixSum[i] = A[1] + A[2] +  ,,, + A[I] 계산

 - sum(a, b) = PrefixSum[b] - PrefixSum[a-1]

 

 - 갱신

PrefixSum을 다시 계산. O(n)

 

 

 

 

&바이너리 트리

 

 

 

연습문제 : 달리기

수학적 귀납법으로 풀면 된다.

 

 

 

 

 

 

 

rank(1) = PrefixSum[0] + 1

rank(2) = PrefixSum[1] + 1

...

..

.

 

자세한 설명 나중에 함

 

 

 

 

 

 

 

 

 

 

 

 

 

 

<트리지름>

 

 

 

& 입력

 : 트리

 

& 출력

 : 트리의 두 정점 u,v의 거리(이 둘을 잇는 간선의 개수) 최대값

 

 

#O(n^2) Algorithm

 

& Brute-force method

 : 모든 가능한 u,v 의 조합을 다 해본다

 : O(n^3)?

 : u를 고정하고 *BFS하면 O(n^2)

 

 

*BFS : 너비우선탐색 

 -  노드의 개수와 에지의 개수 한만큼.

 -  하나의 정점으로부터 시작하여 모든 정점들을 한 번씩 방문하는 것.

 

(알고리즘 들은 지 너무 오래되서 기억안난다)

 

 

 

 

 

 

 

 

 

#O(n) Algorithm

 

1.  Tree에서 임의의 정점 x를 선택.
2.  x에서 가장 먼 정점 y를 찾는다.(BFS)
3.  y에서 가장 먼 정점 z를 찾는다.
4.  y와 z가 가장 멀리 떨어져 있는 정점의 쌍이다.

 

 

(proof)

 

원하는 답이 두 정점 u와 v라고 하자. 그렇다면 세 가지 가능성이 있다. x를 정한 뒤 여기서 가장 먼 점이 y라고 하면,

 

1. x= u (or v)

2. y = u (or v)

3. x, y, u, v 가 모두 다른 경우

 

1, 2 는 위 알고리즘 답이 자명하다. 3의 경우가 발생할 경우는 u~y의 경로와 u~v의 경로가 걸가 같은 경우 외에는 없어야 한다.

 

 

 

 

 

<과반수 찾기>

 

&입력

 :  정수의 배열 A[n]

 

&출력

 : 만약 A[n]에서 n/2번 이상 나오는 원소 x가 있다면 x

 

&Brute-force method

 : 각 원소마다 자기 뒤에서 나오는 횟수를 세어본다

 : O(n^2)in the worst case.

 

 

 

 

 

#O(n log n) Algorithm

 

1. 원소들을 정렬.

2. 차례대로 원소를 읽으면서 바로 직전 원소와 같은 지 비교.

 

정렬에 O(nlogn), 원소를 읽는데 O(n)

 

 

 

#O(n) Algorithm

 

 

이해도안되고

아 하기싫다.

퇴근