코딩테스트 - 패스트캠퍼스 챌린지 06일차

수강한 강의
Chapter 10 자료구조 (트리)
- 이진 탐색 트리 구현과 성능 평가

학습 후기
자료구조 트리에 대해서 배웠다. 트리는 Node와 Branch를 사용하여 사이클을 이루지 않도록 구성한 데이터 구조로 탐색(검색) 알고리즘 구현을 위해 많이 사용된다.
- 주요 용어
Node: 데이터 저장 요소, 다른 노드와의 연결 정보인 Branch 정보 포함
Level: 최상위 노드를 Level 0으로 하여 하위 Branch로 연결된 노드의 깊이를 나타냄
Parent Node: 어떤 노드의 상위 연결 노드
Child Node: 어떤 노드의 다음 레벨 노드
Leaf Node (Terminal Node): Child Node가 하나도 없는 노드
Sibling (Brother Node): 부모가 같은 노드
Depth: 트리에서 Node가 가질 수 있는 최대 Level

이진트리와 이진 탐색 트리
이진트리: 노드의 최대 Branch가 2인 트리
이진 탐색 트리: 이진 트리에 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있는 조건이 추가된 트리이다.
이진 탐색 트리의 장점
데이터 탐색 속도를 개선할 수 있다.

이진 탐색 트리를 직접 구현해보는 강의였는데 Tree에서 사용되는 Node를 클래스

public class Node {
    int value;
    Node left;
    Node right;

    public Node(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

이진 탐색 트리에 데이터를 넣는 insertNode 함수

public boolean insertNode (int value) {
    /* node가 없는 경우 */
    if (this.root == null) {

    /* node가 있는 경우 */
    } else {
        Node targetNode = this.root;
        while (true) {
            /* 현재 Node의 왼쪽에 Node가 들어가야 할 때 */
            if (...) {

            /* 현재 Node의 오른쪽에 Node가 들어가야 할 때 */
            } else {

            }
        }
    }
    return true;
}

주어진 트리에서 데이터를 찾는 search함수

public Node search(int value) {
    /* Node가 하나도 없을 때 */
    if (this.root == null) {
        return null;
    /* Node가 하나 이상 있을 때 */
    } else {
        Node targetNode = this.root;
        while (targetNode != null) {
            // targetNode가 찾던 노드일 때
            if (...) {
                return targetNode;
            /* 찾는 노드 값이 targetNode 노드 값 보다 작을 때 */
            } else if (...) {

            /* 찾는 노드 값이 targetNode 노드 값 보다 클 때 */
            } else {

            }
        }
        return null;
    }
}

여기까지는 경우의 수를 구분하며 쉽게 구현이 가능하였다.
진짜 복잡했던 건 Tree에서 노드를 삭제하는 함수를 구현할 때였다.
경우의 수가 많고 생각해봐야 할 조건들이 많았지만 강의 노트에는 한땀한땀 각 케이스마다 그림으로 그려서 쉽게 설명해주어 이해하기 수월하였다. 노드 삭제 함수를 구현하기 위해 우선 삭제할 노드를 찾고, 삭제할 노드가 Leaf Node인지 Child Node를 가지고 있는지 거기에서 또 Child Node가 하나인지 둘인지... 많은 경우의 수가 있어 강의에서도 각 줄마다 주석이 되어있었고 직접 구현할 때에도 헷갈리지 않게 하기 위해 주석을 써가면서 작성하였다. 그렇게 하고 보니 Tree에서 구현 함수 중 deleteNode 함수가 가장 길었다. 또, deleteNode 함수를 작성하면서 코너 케이스라고 간단하게 판단되는 조건은 가장 최 상단에 넣어 알고리즘 복잡도를 줄이는 쪽으로 구현할 수 있는 방법을 배웠다. 자료구조에서 함수를 구현할 때뿐 아니라 실제 알고리즘 문제를 직접 풀 때에도 코너 케이스를 작성하여 안 되는 케이스는 빨리 빠져나오게 하고 각각의 경우의 수를 잘 생각하여 모든 조건을 빠짐없이 구현하여야겠다는 생각이 드는 강의였다.

수강 인증샷

 

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.