홍쌍의 블로그

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

<인접 매트릭스>

<인접 리스트>

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

이는 트리에서 임의의 정점을 택하고, 해당 정점에서 가장 멀리 떨어진 정점 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))가 되겠다.

문제(Baekjoon)

내 코드(Github)

상부에 조르고 졸라 드디어 내 도시에도 고속도로가 들어서게 되었다. 만세!

문제는, 그냥 다들 한곳에 모여살면 좋을것을 서로 원수라도 졌는지 공동체들이 여기저기 흩어져 있다는 것.

공동체들은 각각 유일한 번호로 이름지어져 있고, 각 공동체들을 잇는 도로가 존재한다.

한 공동체에서 다른 공동체로 갈 수 있는 경로는 꼭 하나만(가) 존재한다.

우리는 이 도로중 일부를 대체할 하나의 선으로 이루어진 고속도로를 짓는다. 고속도로에서 떨어져있는 공동체는 어쩔 수 없이 기존에 존재하던 도로를 이용해 고속도로에 접근해야한다.

고속도로에서 가장 멀리 떨어진 공동체에서 고속도로까지의 거리를 최소화하는 방향으로 고속도로를 건설하였을 때, 그 거리는 얼마인가?

내 가정:

각 노드에서 다른 노드까지의 경로가 단 하나만(가) 존재한다는 것으로 보아 이 그래프는 트리이다.

고속도로는 그래프의 한 종단노드에서 다른 종단노드까지의 경로를 잇는 선이다.

각 종단노드들을 루프토드로 잡고 아래로 탈탈 털어 트리모양으로 만든 후, 각 루프노드에서 각 리프노드까지 경로의 코스트를 구한 경우의 수들 중, 코스트가 가장 큰 경로^[각주:1]를 우리가 지을 고속도로로 한다.

이제 고속도로가 지나는 노드 중, 고속도로에 접하지 않은 노드를 갖는 노드들을 루프노드들로 하고, 고속도로가 이어지지 않은 리프노드들까지의 코스트들을 구해 가장 큰 값을 취한다.

09/24/2018

풀이:

트리의 지름을 구하는 문제이다.

트리의 지름의 각 끝점이 되는 두 종단노드를 구한 후, 해당 두 종단노드를 잇는 경로에서 두 종단노드를 제외한 다른 종단노드까지의 거리중 가장 큰 값을 구하면 된다.

트리의 지름의 각 끝점이 되는 두 종단노드 x, y를 구한 후, x, y를 잇는 경로의 cost를 0으로 설정, x부터 시작해 트리를 DFS하여 가장 큰 코스트를 출력하였다.

1/8/2018 10:40 PM

어느덧 새해가 밝고 일주일이 지났다.

크리스마스부터 새해 첫날까지 이어진 휴가 후엔 근 2000마일이라는 경이로운 마일리지 기록과 그에 비해 약간 초라한 세개의 페이스북 상태메세지를 가장한 여행기만 남았다. 원래 여행이란 피곤한 법, 그 상태에서 그럴싸한 여행기까지 남기겠다고? 어림없는 이야기였지.

라스 베가스에서, 잠들기 전에

데스밸리, 미친듯이 야간주행 후 허름한 Motel6 안에서, 새벽

로스 앤젤레스, 동행이 공항으로 떠난 후 코인세탁소에서 빨래하다 다 털림

여행한 경로, 데스밸리 안에서 돌아다닌것과 도시 내 주행을 합치면 근 2000마일쯤 된다.

여기에서 못다한 도시들의 감상을 짧게나마 써내려보고자 한다.

다운타운에 위치한 블루보틀, 그리고 그곳에서 브런치

휘유! 샌 프란시스코!

나는 솔직히 모든 도시가 드라마 실리콘 밸리에서 본 것처럼 주택으로 되어있고, 잘 정돈된 도로에, 전기차가 돌아다니고 있는 도시를 생각했다.

실제로는? 어림도 없는 이야기지, 다운타운이 언덕에 위치해 있어 차는 오르락 내리락, 도로 양옆은 사방팔방이 공사중인 곳에, 주차할 곳은 터무니 없이 적다. 가게, 호텔의 주차장은 꿈에도 생각 못하고 다닥다닥 차가 움직여야하는 최소한의 공간을 빼고 모든곳이 주차공간인, 그리고 그 모든곳에 차가 들어차 있는  주차타워만이 유일한 주차공간.

사람들은 어땠는가 하면, 자신은 지성인이라 철썩같이 믿는 사람들이(이 사람들이 지성인이 아니라는 뜻은 아니다) 바쁜 일과시간 후, 마음맞는 동료 한명과 일곱명 남짓이 들어갈만한 일식집에 들어가 초밥 세네그릇, 맥주 한잔으로 저녁을 채우는 전형적인 도시 깍쟁이의 느낌...?

이게 무척 낯설고 힘들었다기 보단 LA 광역권 한적한 도시에 살고있는 나에게는 무척 신선하게 다가왔다. 이게 바로 미국 어반라이프인가?

샌디에고, 과거 군항에 위치한 USS 미드웨이 항모. 안에는 퇴역 군인분들께서 안내를 하고 계신다. 그분들께 말씀을 여쭐땐 꼭 Sir를 말끝마다 붙이도록 하자.(아님)

샌디에고는 사실 여행으로 간 것이기 보단 그냥 함께 인턴으로 온 친구들도 만나고, 슬렁슬렁 맛난것도 먹고 적당히 쉬려고 갔다.

에어비앤비로 예약했던 숙소는 정말이지 내가 경험했던 그 어느 숙소보다도 최고의 숙소였다. 할머니 한분이 살고계시는 아파트였는데, 집 안 곳곳에 사랑이 가득했고, 깨끗했고, 따뜻했다. 동화에 나오던, 할머니를 찾아간 손주의 느낌이 이런 것일까.

그리고 한가지 특이했던게, LA는 거대한 원 안에 모든것을 모아놓고, 그 사이사이를 고속도로로 연결한 느낌이라 하면, 샌디에고는 점점이 흩뜨려놓고 그 점들을 고속도로로 이었다는 느낌일까, 어디를 가려면 꼭 고속도로를 타야하는데, 고속도로를 타면 들판, 숲, 언덕들을 달리고 조금 달리다 보면 주거지역이라던가, 상권이라던가, 도심이라던가가 나오는걸 보면...