홍쌍의 블로그

그래프를 표현하는 방법 중에는 매트릭스를 이용한 인접 매트릭스와 리스트를 이용한 인접 리스트가 있다.

<인접 매트릭스>

<인접 리스트>

트리에서 두 정점을 잇는 경로 중 가장 큰 가중치(긴 거리)를 갖는 경로를 트리의 지름이라고 한다.

이는 트리에서 임의의 정점을 택하고, 해당 정점에서 가장 멀리 떨어진 정점 w를 찾고, 다시 정점 w에서 가장 멀리 떨어진 정점 d를 찾으면 쉽게 구할 수 있다.

p는 점 또는 선이다.

x에서 가장 멀리 떨어진 정점 w가

1. w일 경우:  d, w는 트리 내에서 가장 멀리 떨어진 점이므로 다음으로 찾을 정점은 d가 될것이다.

2. d일 경우: 상동.

3. d, w가 아닌 다른 정점 y일 경우: a, b사이의 거리를 d(a, b)라 할때, d(y, p) > d(d, p), d(w, p)가 되므로 y가 트리의 지름에 속해야 옳다.

문제(Baekjoon)

내 코드(Github)

세로, 가로 각각 R, C의 크기을 갖는 매트릭스 안에서 세로, 가로 각각 H, W의 크기로 (1 ≤ H ≤ R, 1 ≤ W ≤ C) 구성가능한 모든 서브매트릭스들의 중앙값들 중 가장 작은 값을 찾아야 한다.

매트릭스의 각 요소 k의 값은 1 ≤ k ≤ R * C이고 유일하다. H, W는 모두 홀수이고 R, C는 각각 1에서 3000 사이의 수이다.

내 가정:

왼쪽 위 서브매트릭스부터 오른쪽 아래 서브매트릭스까지 전수 조사, 중앙값은 파이썬 list의 sort 함수를 이용해보았다. 역시 실패.

sort가 문제일까?, 중앙값 찾는것을 이진탐색퀵셀렉션으로 바꾸어보았다. 실패.

전수조사가 문제겠군... 한번 서브매트릭스 내에 지금까지 구한 최소값보다 작은 값이 있을경우에만 중앙값을 구하도록 해보자. 실패.

이제 어떻게 바꾸지 도무지 종을 잡을 수 없던 도중, 고맙게도 해당 문제에 대해 질문을 해주신 분을 통해 특정 값을 미리 지목 후 해당 값이 답이 될 수 있는지 조사하는 방법도 있다는걸 깨달았다. 내일 해봐야겠다. 이 글이 푼 문제로 이동하길 바라며.

9/22/2018

틀린 단어 수정: 이진탐색->퀵셀렉션, 이진탐색은 정렬된 배열에서 특정한 수를 찾는것(O(log(n))). 퀵셀렉션은 정렬되지 않은 리스트에서 k번째 크기의 수를 찾는것(좋은 pivot의 경우 O(n), 나쁜 pivot의 경우 O(n^2)).

문제 링크 수정

09/24/2018

풀이:

부분합을 이용하여 어느 값 x (1 ≤ x ≤ R * C)에 대해 x가 중앙값이 될 수 있는지, 또 x보다 작은, 중앙값이 될 수 있는 값이 있는지 탐색가능하다.

O(RC + (R-H)(C-W)) 시간 소요.

위 매트릭스는 해당 문제에 대한 예제 입력중 하나이다. 3x3 서브매트릭스에 대해 x=13값이 중앙값이 될 수 있는지 살펴보자.

먼저 요소에 k에 대해 k = x일 경우 0을, k < x일 경우 -1을, k > x일 경우 1을 매핑해주자.

결과로 다음과 같은 매트릭스가 나온다. 이제 우리는 서브매트릭스의 SUM값에 따라 해당 서브매트릭스에서 값 x가 중앙값인지(SUM=0), x보다 작은값이 중앙값이 될 수 있는지(SUM < 0)를 알아낼 수 있다.

그러나 모든 서브매트릭스에 대해 일일이 SUM을 수행할 경우 O(RCHW)라는 무지막지한 시간이 소요된다.

이를 부분합을 통해 O(RC + (R-H)(C-W))로 줄일 수 있다.

부분합 매트릭스의 경우 다음과 같이 나온다. 이 때 밝은 부분이 나타내는 서브매트릭스의 SUM값을 D-C-B+A를 수행해 구할 수 있다.

이를 통해 값 x에 대한 모든 서브매트릭스의 SUM값 탐색을 (R-H)(C-W)번으로 수행할 수 있다.

이 때

1. 0보다 작은 SUM값이 있을 경우: 더 작은 x값에 대한 중앙값 가능 여부 탐색.

2. 0보다 작은 SUM값이 없고, 0이 되는 SUM값이 있을 경우: 해당 값이 답.

3. 그 외(SUM값이 모두 0보다 크다): 더 큰 x값에 대한 중앙값 가능 여부 탐색.

을 수행하면 된다.

x값 탐색에 대해서는 이진 탐색을 이용할 경우 해당 문제에 대한 시간 복잡도는 총 O((RC + (R-H)(C-W))log(RC)) -> O(RClog(RC))가 되겠다.