홍쌍의 블로그

문제(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를 적용하면 제한시간 내에 문제를 해결할 수 있다.

하세 다이어그램은 유한부분순서집합을 표현하기 위한 도표, 도형이다. 집합의 각 요소들은 정점으로 표현되며, 정점간의 관계는 각 정점의 상대적 높이, 그리고 정점을 잇는 선분으로 표현된다. x, y를 잇는 선분의 경우, 자기 자신 이외의 다른 선분을 교차하는 것이 가능하나, 해당 선분이 나타내는 관계에 포함된 두 정점 이외의 정점을 가로질러서는 안된다.

y 정점이 x 정점보다 높은 곳에 위치하고, 두 정점은 선분으로 이어져 있을 경우. x < y이며 x < z < y 인 정점 z가 존재하지 않음을 나타낸다.

하나의 유한부분순서집합에서 나올 수 있는 다양한 하세 다이어그램(출처 : 영문 위키피디아)

위에서 볼 수 있듯 표현하고 싶은 관계가 직관적으로 나타나는 하세 다이어그램을 그리는것이 중요하다.

또한 그래프 그림과는 독립적으로, 하세 다이어그램은 일방향 비순환 그래프를 뜻하기도 한다?

구현(자바)

참조문헌1

참조문헌2

Min-max heap은 min heap과 max heap의 장점을 취해 구현한 완전이진트리이다.

홀수번째 깊이의 노드들은 min heap을, 짝수번째 깊이의 노드들은 max heap을 구성한다.

기존 min heap, max heap과 같이

• 삽입, 삭제에 대해 로그 시간복잡도
• 초기 구축에 선형 시간복잡도

을 가지면서도 min, max값에 대해 모두 상수 참조시간을 갖는 매력적인 자료구조이다.

구현에는 

• 원소를 트리 위에서 아래로 내리는 TrickleDown (heapify 및 삭제에 쓰인다)
• 원소를 트리 아래에서 위로 올리는 BubbleUp (삽입에 쓰인다)

함수가 필요하다.

heapify 연산의 경우 첫번째 인덱스를 1로 갖는 배열로 구현한 트리의 경우

기존 힙과 같이 인덱스 size(tree) / 2 부터 1까지(자식을 갖는 노드들을 아래에서 위로 거슬러 올라감, n번째 깊이의 노드들은 n-1번째 깊이의 노드들보다 먼저 연산되어야 한다) 거꾸로 TrickleDown 연산을 수행해주면 된다.

TrickleDown 연산을 보자

procedure TrickleDown(i)
  i는 array내의 위치를 뜻함
  if i는 min level then
    TrickleDownMin(i)
  else
    TrickleDownMax(i)
  endif

procedure TrickleDownMin(i)
  if A[i]가 children을 가지고있음 then
    m := A[i]의 children 및 grandchildren 중
           (존재하는 경우에) 가장 작은 요소의 인덱스
    if A[m]이 A[i]의 grandchild임 then
      if A[m] < A[i] then
        swap(A[m], A[i])
        if (A[m] > A[m의 부모]) then
          swap(A[m], A[m의 부모])
        endif
        TrickleDownMin(m)
      endif
    else A[m]이 A[i]의 child임
      if A[m] < A[i] then
        swap(A[i], A[m])
      endif
  endif

TrickleDownMax의 경우 TrickleDownMin에서 부등호의 방향만 다르게 구현해주면 된다.

해당 자료구조가 갖는 성질에 비해 구현이 매우 쉽고 간단하다.

기본적으로 A[i]의 grandchild, child를 살펴 가장 작은값(A[m])을 살펴 swap할지를 결정하는데,

A[i]가 그 어느값보다 작을 경우:

  이미 해당 min level의 성질을 만족함, 더이상 연산을 수행할 필요 없음.

A[m]이 child일 경우:

  A[i]와 A[m]의 위치만 swap 후 종료, 삭제의 경우 이미 트리는 min-max heap의 성질을 만족하는 상태이며,

  heapify중일 경우에는 heapify 연산이 아래 레벨부터 위의 레벨 순서로 TrickleDown을 수행하기 때문에 swap된 기존 A[m]값은 자연히 올라갈것임.

A[m]이 grandchild일 경우:

  A[i]와 A[m]의 위치를 바꾸고, 또 A[m]의 부모와 비교하여 값이 A[m]이 더 클경우 A[m]과 A[m의 부모]를 swap한다.

  이는 기존의 A[i]값이 max heap level에 속해야 할 값이었을 경우 leaf노드 끝까지 내려갔다가 다시 올라오는 연산을 할 수고를 덜게해준다.

  기존 A[i]값이 더 상위의 max heap level에 속해야 할 값이라면, heapify 연산중에는 상기한 바와 같이 자연히 올라가게 될 것이다.

  삭제의 경우에는 이미 트리는 min-max heap의 성질을 만족하는 상태이기에, 이전 i의 grandparent의 TrickleDownMin 연산에서 max heap level에 속했어야 옳다

  마지막으로 grandchild와 swap에 성공했을 경우엔 TrickleDownMin을 또 다시 호출하여 min-max heap의 성질을 만족할 때까지 내려가도록 한다.

procedure Deletion(i)
  A[i] := A[length]
  length := length - 1
  TrickleDown(i)

procedure Insertion(K)
  A[length] := K
  BubbleUp(length)
  length := length + 1

마지막으로 insertion에 쓰이는 BubbleUp의 경우 TrickleDown보다도 더 간단하다.

procedure BubbleUp(i)
  i는 array내의 위치를 뜻함
  if i는 min level then
    if i의 부모 존재 then
      if A[i] > A[i의 부모] then
        swap(A[i], A[i의 부모])
        BubbleUpMax(i의 부모)
      else
        BubbleUpMin(i)
      endif
    endif
  else
    if i의 부모 존재 then
      if A[i] < A[i의 부모] then
        swap(A[i], A[i의 부모])
        BubbleUpMin(i의 부모)
      else
        BubbleUpMax(i)
      endif
    endif
  endif

procedure BubbleMinUp(i)
  if A[i]가 grandparent를 가짐 then
    if A[i] < A[i의 grandparent] then
      swap(A[i], A[i의 grandparent])
      BubbleUpMin(i의 grandparent)
    endif
  endif

역시 BubbleMaxUp의 경우 부등호의 방향만 다르게 해주면 된다.

먼저 A[i]자신의 min, max level 여부를 살피고 반대되는 성질의 level(A[i]의 parent가 위치한 level)에 진입할 수 있는지를 확인한다 

A[i]가 min level이고 A[i]의 parent보다 클 경우 : max heap level로 진입

A[i]가 min level이고 그 외 : min heap level로 진입

A[i]가 max level이고 A[i]의 parent보다 작을 경우 : min heap level로 진입

A[i]가 max level이고 그 외 : max heap level로 진입

그리고 BubbleMinUp, BubbleMaxUp 각각에서는 min-max heap의 성질을 만족할 때까지 계속 grandparent와 비교하며 요소를 위로 swap해주면 된다.

이렇게 구현된 min-max heap의 경우 root노드는 min값을, 그리고 root의 자식노드 둘 중 하나가 max값을 가지게 된다.