treecode

public int getMax(TreeNode node) {
    if (node == null) {
        return 0;
    }
    int leftVal = Math.max(0, getMax(node.left));
    int rightVal = Math.max(0, getMax(node.right));

    max = Math.max(max, node.val + leftVal + rightVal);

    return node.val + Math.max(leftVal, rightVal);
}

이어진 노드중 가장 큰 값을 구하는 문제로 먼저 재귀 호출을 계속 하면서 트리 끝까지 이동한다.

끝에서부터 음수인 값(leftVal, rightVal)은 더하지 않고 양수인 값만 더해간다.

반환하기 전에 해당 노드 기준으로 max 값을 갱신

자식 노드가 양수더라도 부모 노드 음수 값이 더 크면 해당 노드는 짤린다.

중간에 아니다 싶을때 뚫린 구멍 막는 식으로 풀지 말고 다시 생각해보기..!

부모 노드와 자식 노드 값 차이의 절대값중 가장 큰 값을 구하는 문제로 Map<Integer, List<Integer>> 를 만들어서 노드마다 자식 노드 값을 저장했더니 효율성이 처참하게 나왔다. 

public void DFS(TreeNode node, int max, int min) {
    if (node == null) {
        return;
    }
    int newMax = Math.max(max, node.val);
    int newMin = Math.min(min, node.val);

    answer = Math.max(answer, Math.abs(newMax - newMin));

    DFS(node.left, newMax, newMin);
    DFS(node.right, newMax, newMin);
}

최대값, 최소값을 갱신하면서 재귀로 호출하면 현재 노드부터 최상위 노드중 최대값, 최소값의 차이를 구하기 때문에 노드마다 일일이 계산할 필요가 없다.

프로세스와 스레드

프로세스는 실행 중인 프로그램으로 디스크로부터 메모리에 적재되어 CPU를 할당 받으며 프로그램을 실행한다. 운영체제로부터 주소 공간, 메모리 등을 할당 받으며 운영체제는 프로세스를 관리하기 위해 프로세스마다 PCB(Process Control Block)를 생성하는데 프로세스 전환시 필요한 정보들을 저장해둔다.

스레드는 프로세스의 실행 단위(CPU 수행 단위)로 하나의 프로세스 내에는 여러 개의 스레드를 생성할 수 있다.

스레드는 프로세스의 Code, Data 영역, OS 자원과 같은 공통 자원을 공유하면서 독립적으로는 Stack 영역과 PCB에 현재 코드의 어느 부분을 실행하고 있는지를 가르키는 PC(Program Counter), 레지스터 값들을 가지고 있는다.

프로세스의 공통 자원 공유를 통해 여러 개의 프로세스를 생성하지 않고 자원을 효율적으로 사용할 수 있으며 프로세스 컨텍스트 스위칭에 비해 오버 헤드가 줄어든다. (프로세스 간 컨텍스트 스위칭과 달리 캐시 메모리를 비울 필요가 없다.)

멀티 스레드는 프로세스 내의 공간을 공유하고 Heap 영역을 통해 스레드 간에 데이터도 주고 받을 수 있어 프로세스 간에 통신보다 훨씬 간단하다. 하지만 여러 스레드가 하나의 프로세스 공간을 공유하기 때문에 다른 스레드에서 사용중인 변수나 자료구조에 접근해서 문제를 일으킬 수가 있다. 그래서 동기화 작업을 통해 작업 처리 순서와 공유 자원에 대한 접근을 컨트롤해야 되는데 이 경우에도 과도한 제한으로 인해 병목 현상의 위험이 있다. 그리고 하나의 스레드에 문제가 발생할 경우 위험이 전파되는 등의 단점도 있기 때문에 멀티 프로세스 방식과 상황에 따라 적합한 방식을 사용해야 한다.

12월에 면접 준비랑 다른 시험도 겹치고 우테코 파이널 준비에만 집중할 수 없어서 정신이 없다.

파이널을 볼 수 있을지 모르겠지만 그래도 할 수 있는만큼 해보려 한다.

이전 파이널 시험 문제를 풀어보았는데 페어 매칭 문제로 크루들의 이름이 담긴 파일을 읽어서 매칭을 하는 프로그램이다.

시험이라 생각하고 하다보니 차곡차곡 발전시키면서 구현해나가기보다 기능을 구현하는데 정신이 없었다.

급하게 하려다보니 요구 사항을 제대로 안 읽어서 실수한 부분도 많았고 바로 손부터 대니까 오히려 나중에 시간이 더 걸리고 꼬여버렸다.

그리고 기본으로 주어지는 테스트 코드도 먼저 보고 하면 좋을 것 같은데 셔플 함수를 String이 아닌 Crew 클래스를 만들어서 사용하니까 기본으로 주어지는 테스트 코드가 계속 실패해서 멘붕이 왔었다.

그리고 이번에는 저번 코드 리뷰를 통해 Dto를 만들어서 활용하니 도메인을 그대로 노출시키지 않고 필요한 값만 처리할 수 있어서 많은 이점을 느낄 수 있었다. 다음 문제를 풀 때는 요구 사항을 더 꼼꼼히 읽고, 어떤 식으로 구현할지 생각을 하는데 투자를 더 해봐야겠다.