홍쌍의 블로그

Show tabs in one row 체크 해제

✔Open declaration source in the same tab

Scheme: High Contrast

Identifier under caret

Background: F64436

Error stripe mark: FF0D25

Identifier under caret (write)

Background: F64436

Error stripe mark: FF0D25

그 외 유용한 Plugins

Java Bean to Json

Lombok

---------------------------------

2020.07.17 위의 설정을 다 때려치우고 Material Theme UI의 Dracular 기반에다가 엑센트 설정을 조금 바꿔준 세팅을 업로드.

App Store에서 다운로드 가능

Runner:

✔Parrot

Settings:

✔Show CPU Usage

✔Show Memory Usage

✔Flipped Horizontally

https://www.mowglii.com/itsycal/ 에서 다운로드 가능

Appearance:

✔Use outline icon

✔Show month in icon

✔Show day of week in icon

✔Theme: Dark

✔Show event dots

    ✔Use colored dots

✔Show event location

✔Show calendar weeks

✔Use larger text

App Store에서 다운로드 가능

https://pqrs.org/osx/karabiner/ 에서 다운로드 가능

ps. ⌘키를 누르고 드래그 하면 메뉴바 상의 위치 수정 가능

'소멸자는 왜 virtual 키워드를 가져야 하는가?'

한창 취업 준비중인 요즘, 모사의 면접에 가서 들은 질문이다. 그리고, C 스타일의 코드를 써놓고 C++을 써봤다고 우겨왔던 나는 제대로 답하지 못헀다.

같은 면접장에 있던 다른 지원자의 말을 들을 순 있었지만, 아무래도 긴장때문인지 이해가 잘 안됐고, 집에 와서 직접 찾아보고서야 알 수 있었는데, 예시와 함께 보도록 하자.

class A {
public:
	void test() {
		printf("A");
	}
};

class B: public A {
public:
	void test() {
		printf("B");
	}
};

int main() {
	B b;
	A& a = b;
	a.test();
}

다음의 경우 출력 결과가 어떻게 돼야 하고, 어떻게 될까?

레퍼런스 a가 가진 인스턴스는 클래스 b의 객체이고, test 함수는 오버라이딩 되었으므로, 결과로 "B"가 출력되어야 하지만, 아쉽게도 "A"가 출력이 된다.

이는 함수 주소값들이 모두 정적으로 바인딩되어, 레퍼런스 a가 가진 인스턴스의 타입에 상관없이 레퍼런스 a의 타입인 클래스 A의 test 함수를 호출하였기 때문이다. 이런 문제를 피하기 위해 virtual 키워드가 존재한다.

virtual 키워드를 가진 함수가 클래스 내에 존재할 경우, 해당 클래스 인스턴스 생성시 인스턴스들은 모두 virtual function table 포인터를 가지며, virtual 키워드를 가진 함수가 호출되었을 경우 정적으로 바인딩된 함수주소를 참조하여 호출하지 않고, virtual function table을 살펴 (동적으로 바인딩 된)함수를 호출하게 된다.

자, 여기서 소멸자가 virtual 키워드를 가져야 하는 이유를 알 수 있는데, 부모 클래스 타입의 레퍼런스 또는 포인터가 자식 클래스의 인스턴스를 가지고 있는 상태에서 소멸자를 호출할 경우, 해당 자식 클래스의 소멸자가 호출되지 않고 부모 클래스의 소멸자가 호출된다. 만약 자식 클래스에서 따로 할당된 메모리가 있을 경우 해당 메모리의 할당 해지가 이루어지지 않아 메모리 누수가 발생하는 것이다.

추가로, 자바에선 virtual 키워드를 어떻게 처리할까?

public class A {
    public A() {
        System.out.println("A created");
    }

    public void test() {
        System.out.println("A test called");
    }
}

public class B extends A {
    public B() {
        System.out.println("B created");
    }

    public void test() {
        System.out.println("B test called");
    }
}

public class Main {
    public static void main(String[] args) {
        A a = new B();
        a.test();
    }
}

이 경우 B test called가 호출된다. 자바는 모든 함수가 virtual 키워드를 갖는다.

무엇이 이 두가지 차이를 만든것일까?

자바는 객체지향 언어이고, C++는 객체지향의 성격을 갖는 언어이다. 자바는 객체지향 언어이므로 다형성에서 오는 문제들을 언어 스스로 처리할 수 있어야 했지만, C++는 그보다는 성능에 초점을 두어(virtual fuction table 참조에 의한 성능저하?), 프로그래머들이 직접 이를 정하게 하였다... 라고 봐도 될까?

SyntaxHighlighter를 분명 제대로 설정해놨다고 생각했는데 잘 작동하지 않는다. 쓰기도 영 불편하고, 다른 방법을 찾아봐야겠다.

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

하세 다이어그램은 유한부분순서집합을 표현하기 위한 도표, 도형이다. 집합의 각 요소들은 정점으로 표현되며, 정점간의 관계는 각 정점의 상대적 높이, 그리고 정점을 잇는 선분으로 표현된다. 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값을 가지게 된다.