[TIL] 타임어택 알고리즘, 트리, 배열로 이진탐색트리 구현

*20221116의 회고

 

   오늘은 오전 9시부터 11시까지 두시간동안 알고리즘 문제를 푸는 것으로 하루를 시작했다. 총 4문제가 출제되었는데, 프로그래머스의 코딩테스트 입문 단계 문제들로 구성이 되어 있어서 쉽게 풀 수 있었다. 딱 이 수준까지는 문제없이 풀 수 있는 것 같다! 여기서 이제 어려워지면 어렵다...ㅎㅎㅎ 아무튼 별 탈 없이 문제를 풀고 난 후, 어제와 이어서 오늘도 남은 알고리즘 자료구조 강의를 수강하였다. 오늘 배운 부분은 트리, 힙 부분이다. 개념적으로는 이해하는데 어려울 게 없었는데, 이진 탐색 트리를 구현하는 실습을 하면서 하루를 다 소비한 것 같다. 몇 번은 강의를 돌려 본 것 같다. 아직도 완벽히 이해했다고는 할 수 없고, 어렴풋이 알 것 같은 느낌이다.

 

   이진탐색트리를 구현하고 이해하는게 어려웠던 이유를 뽑아본다면, 두가지를 뽑을 수 있을 것 같다. 첫번째 이유는, 재귀함수의 개념을 명확히 알지 못하는 것에서 오는 것 같다. 재귀함수 자체의 개념은 알겠는데, 사용하는 모습을 보면 신기하다. 어떻게 이렇게 짧은 코드로 여러 과정을 생략할 수 있는지... 또한 이번 이진탐색트리를 구현하는 과정에서 사용한 재귀함수의 동작은 머릿속으로는 상상이 잘 안돼서 노트에 과정을 그려가면서 이해했다. 그랬더니 과정이 눈에 보여서 이해에 큰 도움이 되었다. 그러나 손으로 그려가는 과정 없이 코드만 보면 이해하기가 어렵다. 그렇기에 어떻게 이렇게 척 척 재귀함수를 이용해서 코드를 구현하는지, 또 코드만 보고 어떻게 머릿속에 과정을 그려내는지 신기하다. 아직 프로그래밍적 사고를 가지기엔 많이 멀었나보다 ㅠㅠ

   두번째 이유는, 자바의 클래스형 객체를 다루는 데 있어서 경험이 부족하다. 그래서 클래스형 객체의 멤버변수로 본인의 클래스형 변수를 선언하는게 낯설었다. (ex) Node 클래스의 멤버변수로 Node형 객체 생성...?!??!?!?) 이부분은 스택, 큐, 해시테이블을 구현할 때도 등장한 모습이였으나, 봐도 봐도 낯설다..ㅎㅎ 나보고 이런 코드를 짜라고 하면 못짤 것 같다 흑흑.... 그래도 보다보면 익숙해 질 테니, 계속 공부해 나가다 보면 나중에는 이러한 개념도 자유자재로 이해하고 사용하게 될 날이 올거라고 생각한다. 역시 꾸준함이 답이다! 

 

   아래는 오늘 구현한 배열을 이용한 이진탐색 트리 구현코드이다. 유튜브의 '엔지니어대한민국' 채널의 강의를 참고하였다.

public class MyTree { //배열을 이진 검색 트리로 만들기
    class Node {
        int data;
        Node left;
        Node right;
        Node (int data) {
            this.data = data;
        }
    }
    Node root; //트리가 시작되는 노드

    public void makeTree(int[] a) { //배열 정보를 받아서 트리를 만드는 일을 시작해주는 함수
        root = makeTreeR(a, 0, a.length -1); //재귀 호출를 반복적으로 실행하기에 앞서서 재귀호출에 필요한 데이터를 처음으로 던져주는 일을 함
        //재귀 호출이 끝나면 가장 꼭대기에 있는 루트노드의 주소를 받아서 멤버변수에 저장
    }
    public Node makeTreeR(int[] a, int start, int end) { //재귀함수
        if (start > end) return null; //재귀호출에서 무한루프에 빠지지 않을 조건문
        int mid = (start + end) / 2; //받은 시작지점과 끝지점으로 중간지점 계산
        Node node = new Node(a[mid]); //그 중간지점에 저장된 값으로 노드를 생성
        node.left = makeTreeR(a, start, mid - 1); //a배열의 시작지점부터 중간값 바로 앞까지의 서브트리를 현재 노드의 왼쪽에 저장
        node.right = makeTreeR(a, mid + 1, end); //중간값 바로 다음 방부터 end지점까지의 데이터로 만든 서브트리는 오른쪽에 저장
        return node;
    }
    public void searchBTree (Node n, int find) {
        if (find < n.data) {
            System.out.println("Data is smaller than " + n.data);
            searchBTree(n.left, find);
        }
        else if (find > n.data) {
            System.out.println("Data is bigger than " + n.data);
            searchBTree(n.right, find);
        }
        else System.out.println("Data found!");
    }

    public static void main(String[] args) {
        int[] a = new int[10];
        for(int i = 0; i < a.length; i++) {
            a[i] = i; //{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 배열 생성
        }
        MyTree t = new MyTree();
        t.makeTree(a);
        t.searchBTree(t.root, 2);
    }
}

코드의 실행 결과