각박한 세상에서 정신체리

글로벌 시대에 당연히 알고리즘의 영어 이름도 알아야겠다고 생각해서 검색해보았다. 그런데, 한국어로 검색했을 때는 대부분 트리 지름, 트리의 지름으로 키워드가 검색되었는데 영어로 검색했을 때는 Diameter of Binary Tree 였다. 트리의 지름 유형에서는 어쩌면 당연한 이야기일지도?

트리의 지름이란?

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 

그런데 왜 지름이라고 하는 거지? 가장 긴 트리 사이의 경로라던가

백준 1967번 문제의 설명을 보면 좀 더 직관적으로 받아들일 수 있다.

풀이: 탐색 2번

1. 이진 트리가 있다.
2. 임의의 노드 p에서 DFS를 실행하여 p로부터 가장 먼 거리의 노드 a를 구한다. 
3. 노드 a에서 DFS를 다시 실행하여 a로부터 가장 먼 거리의 노드 b를 구한다.
4.  a→b 의 거리가 트리의 지름이다.

증명

(가정) 트리에서 $dis(u, v)$의 경로가 트리의 지름이다. 임의의 노드 x에서 가장 먼 노드는 y이다.

이때 케이스를 나눠보자. 

$i.$ x가 u 또는 v인 경우
$ii.$ y가 u 또는 v인 경우
$iii.$ x, y, u, v가 서로 다른 경우

Case1. x가 u 또는 v인 경우

가정에 따라 x에서 가장 먼 노드인 y까지의 거리는 트리의 지름이다. 

왜냐하면 x가 이미 트리 지름의 한 쪽 끝이기 때문에 dfs를 돌릴 경우 다른 트리의 끝 점으로 가는 것이 당연하다. 

Case2. y가 u 또는 v인 경우

가정에 따라 x에서 가장 먼 노드인 y까지의 거리는 트리의 지름이다.

Case3. x, y, u, v가 서로 다른 경우

이 경우 다시 케이스를 두 가지로 나눌 수 있다.

$dis(u, v)$의 경로와 $dis(x, y)$의 경로가 한 점 이상 공유하는 경우

x에서 DFS를 수행할 경우 가정에 따라 가장 먼 노드는 y이다. 

가장 먼 노드가 y라는 것은 $dis(x, t)$값은 고정되어 있으므로 d1, d2, d3를 비교하였을 때 최대값이 d3라는 의미이다.

이때, $d1 \neq d2$를 가정해보자.

$i.$ $d1 > d2$ 인 경우

우리는 위에서 $d3$가 최대임을 알아냈으므로 $d3 \geq d1 > d2$가 성립한다. 

그런데 가정에 따라 $dis(u, v)$가 트리 지름이므로 $d1 + d2 > d1 + d3$임을 알 수 있다.

양변의 $d1$을 소거할 경우 $d2 > d3$이고 이는 위의 $d3 \geq d1 > d2$와 모순이다. 

$ii.$ $d1 < d2$ 인 경우

마찬가지로 우리는 위에서 $d3$가 최대임을 알아냈으므로 $d3 \geq d2 > d1$가 성립한다. 

그런데 가정에 따라 $dis(v, u)$가 트리 지름이므로 $d2 + d1 > d2 + d3$임을 알 수 있다.

양변의 $d2$을 소거할 경우 $d1 > d3$이고 이는 위의 $d3 \geq d2 > d1$와 모순이다. 

따라서 귀류법을 통해 $d1 = d2 = d3$임을 알 수 있다.

따라서 이후 y에서 두 번째 dfs를 수행할 경우 y에서 가장 먼 정점까지의 거리를 구하면 2d로 트리의 지름과 같아지게 된다.

즉즉 트리의 지름을 구할 수 있게 된다. 

$dis(u, v)$의 경로와 $dis(x, y)$의 경로가 한 점 이상 공유하지 않는 경우

x에서 DFS를 수행한다. 이때 가장 먼 노드가 y이려면

$dis(x, a)$가 고정이므로 $dis(a, y) \geq dis(a, b) + dis(b, v)$여야 한다. 

그럼 노드 u에서 가장 먼 정점을 찾아보자.

$dis(u, b)$가 고정이므로 $dis(b, v) \geq dis(b, a) + dis(a, y)$여야 한다. (by. 가정)

이때 두 부등식을 더해보면

$dis(a, y) + dis(b, v) \geq dis(a, b) + dis(b, v) + dis(b, a) + dis(a, y)$

양변을 소거해보면

$0 \ge dis(a, b) + dis(b, a)$

이므로 모순이다.

Case3의 결론 :$dis(u, v)$의 경로와 $dis(x, y)$의 경로가 최소 한 점 이상 공유한다. 그리고 이때 귀류법에 의해 겹치는 경로에서부터 y, u, v까지의 거리가 모두 같고 이때 두 번째 dfs를 통해 트리의 지름을 구할 수 있다. 

백준(BOJ) 문제

• 1967번: 트리의 지름

[백준 1967 | C++] 트리의 지름 :: 트리의 지름

• 1167번: 트리의 지름

2025.01.06 - [BOJ] - [백준 1167 | C++] 트리의 지름 :: 트리의 지름

참고 자료 및 사이트

• 트리의 지름 구하기

CCW의 활용편이라고 할 수 있는 선분 교차 판별

먼저 CCW의 개념 이해하기는 필수!!

[알고리즘] CCW(Counter Clock Wise) (tistory.com)

문제 상황 : 두 선분이 주어졌을 때 두 선분은 교차하는가?

벡터의 외적값은 선분의 점을 어떻게 잡느냐에 따라 부호가 바뀔 수 있다. 따라서 한 벡터의 부호, 예를 들어 벡터v0의 부호를 기억하는 것이 아니라 세트가 되는 두 벡터(v0과 v1, v2와 v3)의 곱의 결과에 따라 판별하는 것이 중요하다.   

보통 결론만 외우고 끝인 경우가 많은데, 그럼 금방 잊어버릴 것 같다!

해당 결론이 나오게 된 원리를 정확히 알아두면 오래오래 기억나고 좋을 듯.. 그리고 무엇보다 결론을 까먹었을 때 원리만 이해하고 있다면 결론을 스스로 도출해낼 수 있을 것이라고 생각한다. 

기하적 의미를 살펴보면 해당 알고리즘이 나오게 된 경위를 더 쉽게 이해할 수 있다. 

두 선분이 교차하지 않는 경우도 기하적 의미를 따져보면 금방 이해할 수 있다. 

17386번: 선분 교차 1 (acmicpc.net) (골3)
17387번: 선분 교차 2 (acmicpc.net) (골2)

27718번: 선분 교차 EX (acmicpc.net) (플5) 

 
CCW는 3개의 점 A, B, C가 있을 때 이 세 개의 점을 이은 직선의 방향을 판별할 때 유용한 기하 알고리즘이다.
 
외적의 결과 값이 
음수이면 시게 방향,
0이면 직선,
양수이면 반시계 방향이다.
 

11758번: CCW (acmicpc.net)

1. 이분탐색이란?

"반으로 쪼개기"라는 원리를 기반으로 하며, 탐색 범위를 지속적으로 반씩 줄여나가면서 값을 찾는다.

시간복잡도 : O(logn)

2. 예시

left = mid + 1 / right = mid - 1로 업데이트 하는 이유?

• mid 값이 이미 target보다 작기 때문에, target은 최소한 mid + 1 위치에 있을 수밖에 없기 때문!
• mid 값이 이미 target보다 크기 때문에, target은 최소한 mid - 1 위치에 있을 수 밖에 없기 때문!

3. 주의점

정렬된 배열에서만 사용 가능하다.

이분탐색의 원리를 생각해보면 당연하다.

우리가 이분탐색을 가능하게 하는 이유가, 다시 말해서 left, right값을 업데이트할 수 있는 이유가, 그 사이에는 우리가 원하는 숫자가 없을 것이라는 '믿음'을 가지고 건너뛰는 것이기 때문이다.

그렇다면 이런 의문을 제기할 수 있다.

정렬되기만 하면 되는 거 아닌가요? 내림차순으로 정렬되면요? 

불가능하지는 않다. 하지만 관습적으로 오름차순 배열을 사용한다. 하고 싶으면 하세요!

4. 코드(c++)

bool binary_search(vector<int>& arr, int len, int target){
	int left = 0, right = len - 1;
    
    while(left <= right){
    	int mid = (left + right) / 2;
        
        //원하는 값을 찾았다면 true 반환
        if(target == arr[mid])	return true;
        
        // 원하는 값이 더 작다면 검사 범위를 더 낮게 잡아야 한다.
        if(target < arr[mid]){
        	right = mid - 1;
        }
        // 원하는 값이 더 크다면 검사 범위를 더 크게 잡아야 한다.
        else if(target > arr[mid]){
        	left = mid + 1;
        }
    }
    return false; // 마지막까지 못찾는다면 false 반환
}

만약 예시 상황에서 left,right가 겹쳤을 때, 그리고 그때의 arr[mid]가 우리가 원하는 값이 아니었다면? 

코드에 따라, 우리는 다시 한번 left 또는 right값을 업데이트 했을 것이고, 이때 left와 right값이 역전되므로 while문을 탈출하게 된다.

우리가 while문을 돌 동안 원하는 값을 찾지 못했으므로 결국 배열에는 target이 애초에 존재하지 않았던 것이다. 따라서 false를 반환한다.

1. 정리 요약본

2. Repeated Squaring

2.1 정의와 쓰임새

한국어로는 '분할 정복을 이용한 거듭제곱'

어떤 상황에서 이 알고리즘을 쓰냐? x의 y거듭제곱(mod s)을구해야 할 때 주로 쓴다. 

2.2 x^(y) : Naive하게 구하기

비효율적이지만 가장 단순하게 구할 수 있는 방법이다.

x를 y번 곱하면 된다.

하지만 이 방법은 최소 y-1번의 연산이 필요하다. 

2의 16승을 구해보자. 우리는 2를 16번 곱하면 된다.

하지만 만약 2의 10^9승을 구하고 싶다면? 마찬가지로 10^9번 연산해야 한다.

당신은 이미 시간초과 판정을 받았다...

2.3 x^(y) : 효율적으로 구하기

거듭제곱의 성질을 통해 주어진 예시를 이해해보자

마찬가지로 우리는 2^16을 구하려고 한다!

2^16 = 2^8 * 2^8  (지수 : 16 = 8+8)
2^8 = 2^4 * 2^4    (지수 : 8 = 4+4)
2^4 = 2^2 * 2^2    (지수 : 4 = 2+2)
2^2 = 2^1 * 2^1    (지수 : 2 = 1+1)

'지수를 쪼개서 계산하기'가 핵심이다

~이번에는 지수가 홀수인 경우를 계산해보자~

2^15 = 2^7 * 2^7 * 2  (지수 : 15 = 7+7+1)
2^7 = 2^3 * 2^3 * 2    (지수 : 7 = 3+3+1)
2^3 = 2^1 * 2^1 *2    (지수 : 3 = 1+1+1)

핵심은 같은 지수를 가진 두 거듭제곱을 서로 곱해준다는 것이다.

따라서 지수가 홀수인 경우 마찬가지로 같은 지수를 가진 두 거듭제곱을 곱해준다.

그리고 부족한 지수 1은 따로 곱해준다.

2.4 x^(y) (mod s)

2.4.1 전제 조건 

모듈러 연산의 성질이다.

a1 (mod m) = r1
a2 (mod m) = r2
라고 할 때, 양변을 각각 곱하면
a1*a2 (mod m) = r1*r2 (mod m)

[예시]
11 (mod 3) = 2, 7 (mod 3) = 1   ->   77 (mod 3) = 2

2.4.2 앞서 구한 x^(y) 식에 모듈러 연산 추가

모듈러 연산의 성질을 그대로 적용하면 된다.

우리는 이후 재귀를 통해 구현할 것이기 때문에 가장 깊은 곳, 즉 2^1부터 연산이 시작된다.

모듈러 연산 값도 따라서 2^1부터 시작해보겠다!

// 2^16 (mod 101) 구하기

2^1 (mod 101) = 2
2^2 (mod 101) = 2*2 (mod 101) = 4 (mod 101) = 4
2^4 (mod 101) = (2^2)*(2^2) (mod 101) = 4*4 (mod 101) = 16 (mod 101) = 16
2^8 (mod 101) = (2^4)*(2^4) (mod 101) = 16*16 (mod 101) = 256 (mod 101) = 54
2^16 (mod 101) = (2^8)*(2^8) (mod 101) = 54*54 (mod 101) = 2916 (mod 101) = 88

이렇게 타자로 치니까 눈이 좀 어지러운 것 같다. 

정리 요약본 보시면 됩니다...! 

3. 코드 작성(C++)

비재귀 코드

long long modpow(long long x, long long y, long long s) {
	long long r = 1;
	for (; y; y >>= 1) {
		// 오른쪽으로 한 비트씩 시프트하는 연산
		// y를 2로 나누는 것과 동일한 효과
		if (y & 1)
			// y is odd : y & 1 == 1
			// y is even : y & 1 == 0
			r = 1LL * r * x % m;
		x = 1LL * x * x % m;
	}
	return r;
}

4. 추천 백준 문제

24059번: Function (acmicpc.net)

5. 참고 자료

https://youtu.be/5IyqMDg7jN0?si=KM5K-ANnKViSWlDp

https://youtu.be/RkaOkKg-hpM?si=nbucVFMPIy8t4zWR