홍쌍의 블로그

문제(Baekjoon)

내 코드(Github)

작성예정

문제(Baekjoon)

내 코드(Github)

자, 여기 N개의 회사가 있다. 각각의 회사에는 최고위 인사, 즉 모두에게 직간접적으로 상사인 사람이 하나 있고, 나머지 직원들은 모두 각각 자신의 상사를 가지고있다. Y가 X의 직접적인 상사이거나, 또는 X의 상사가 Y의 부하직원 일 경우 모두 X는 Y의 부하직원이라고 하기로 한다.

어느 날 인사팀에서는 회사에 급여 불균형이 얼마나 심한지 조사해보기로 했다. 주어진 인사정보에서, 사원 A에 대한 급여 불균형은 A및 A의 모든 부하직원의 급여 중 최대값과 최소값의 차를 말한다.

인사팀은 모든 사원들에 대한 급여 불균형을 빠르게 계산할 수 있기를 원한다. 그러나, 조사 도중 어느 사원 및, 해당 사원의 모든 부하직원의 급여가 오르는 경우가 있기 때문에, 이는 굉장히 복잡한 작업이다. 좀 도와주실 수 있는지?

입력으로는

- 회사 수 (최대 20)

그리고 각 회사에 대해

- 사원 수 (2 <= N <= 1,000,000)

- 각 사원의 상사 번호 (모든 사원은 1부터 N까지의 유일한 번호가 매겨진다. 해당 라인의 입력은 N-1개의 숫자가 주어지며 K번째 번호는 K+1번의 번호를 가진 사원의 상사를 뜻한다.)

- 각 사원의 급여 (N개의 숫자, K번째 번호는 K번 사원의 급여를 뜻한다.)

- 처리할 명령의 수 (1 <= Q <= 10,000)

그리고 각 명령에 대해

- 처리할 명령의 이름 및 그에 따르는 숫자

  - 'Q'의 경우, 같은 라인에 주어지는 다음 숫자의 사원에 대한 급여 불균형 조사 (ex, Q 2)

  - 'R'의 경우, 같은 라인에 주어지는 다음 숫자의 사원 및 해당 사원의 모든 부하직원의 급여를 사원 번호 다음의 숫자만큼 인상 (ex, R 4 2)

K번호를 가진 사원의 상사의 번호는 K보다 작다. 초기 급여는 1부터 1000까지이다. 급여 인상은 1000을 넘지 않는다.

출력으로는

각각의 급여 불균형 조사에 대해 한 라인에 하나씩 결과를 출력.

내 가정:

다시 트리 문제인듯 하다.

인접 리스트로 각각의 사원에 대해 직속 부하직원에 대한 단방향 그래프를 만들어주었다 (Q 명령에 대해 아래로 탐색해 나가기 위해서)

또 각 사원의 급여 정보는 배열로 관리하였다.

매 Q 명령마다 트리를 탐색하여, Min-max heap에 넣어 최대값 및 최소값을 도출하였다.

R의 명령 역시 트리를 탐색하며 급여 정보를 수정해주었다.

결과는 역시 시간초과.

매 명령마다 트리를 탐색하는게 문제인거같은데, DP로 접근하는 방법이 있으려나?

10/01/2018

이 상황에서 Min-max heap이 의미가 있는지? Min-max heap을 떼어내고, 순회했던 트리에 대해 최소값과 최대값을 기억하도록 해보았다.

X에 대한 Q 명령이 주어졌을 때, 리프 노드에서 X 노드까지 최소값 및 최대값을 전달, 기억하여, X의 서브트리에 대해 Q 명령이 다시 주어질 경우 다시 순회를 하지 않아도 되도록 해보았다.

R 명령이 주어졌을 때에는 X 서브트리를 순회하며 해당 사원들의 salary를 모두 올려주고, 만약 노드가 기억하고 있는 최소값 및 최대값이 있을 경우 해당 값 또한 salary 인상값만큼 올려주었다(해당 노드의 서브트리가 갖는 모든 노드에 해당하는 사원의 salary가 올랐으므로)

그리고 다시 X로 돌아와, 부모 노드가 기억하는 최소값과 최대값이 존재할 경우(X 서브트리를 포함하여 최소값 및 최대값 조사가 이루어진 적이 있음을 뜻함) 계속 부모 노드로 거슬러 올라가며 최소값과 최대값을 새로 갱신해주도록 하였다.

그래서 결과는? 시간초과

10/30/2018

세그먼트 트리를 이용하는 문제였다.

Q 명령이 주어졌을 때, 살펴야 하는 범위를 구하기 위해 각 사원의 번호들을 재정의해 줄 필요가 있다.

트리를 구성한 후, 오일러 트리 순회를 통해 방문하는 노드 순서로 각 사원의 번호를 재정의해주고, 해당 사원이 갖는 부하직원들의 번호 범위 또한 정의해 줄 수 있다.

또한 R 명령의 경우에 Lazy approach를 적용하면 제한시간 내에 문제를 해결할 수 있다.

문제(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하여 가장 큰 코스트를 출력하였다.