Skip to content

Latest commit

 

History

History
175 lines (152 loc) · 8.08 KB

180708.md

File metadata and controls

175 lines (152 loc) · 8.08 KB
Raw

트리와 이진 탐색

관련 문제들

[issue]에 대한 정리

[#issue1] 트리의 개념과 적용 사례

tree

* 트리란
    * 비선형 자료구조로 계층적 관계를 표현한다.
        * 디렉터리 구조
        * 조직도
    * 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다.
    
* 트리 관련 용어
    * 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
    * 단말 노드(leaf node): 자식이 없는 노드
    * 내부(internal) 노드: 단말 노드가 아닌 노드
    * 긴선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
    * 형제(sibling): 같은 부모를 가지는 노드
    * 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
    * 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
    * 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
    * 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
    * 트리의 차수(degree of tree): 트리의 최대 차수
    * 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이
    
* 트리 특징
    * 노드가 N개인 트리는 항상 N-1개의 간선(edge)을 가진다.
    * 루트에서 어떤 노드로 가는 경로는 유일하다. 
    * 임의의 두 노드 간의 경로도 유일하다.
    
* 트리의 표현 방법
    * 그래프의 한 종류이므로, 그래프 표현 방법을 이용
    * 인접 배열 이용
        1. 1차원 배열에 자신의 부모 노드만 저장하는 방법
            * 트리는 부모 노드를 0개 또는 1개를 가지기 때문
            * 부모 노드를 0개: 루트 노드
        2. 이진 트리의 경우, 2차원 배열에 자식 노드를 저장하는 방법
            * 이진 트리는 각 노드가 최대 두 개의 자식을 갖는 트리이기 때문
            * Ex) A[i][0]: 왼쪽 자식 노드, A[i][1]: 오른쪽 자식 노드
    * 인접 리스트 이용
        1. 가중치가 없는 트리의 경우
            * ArrayList< ArrayList<Integer> > list = new ArrayList<>();
        2. 가중치가 있는 트리의 경우
            1) class Node { int num, dist; // 노드 번호, 거리 } 정의
            2) ArrayList<Node>[] list = new ArrayList[정점의 수 + 1];

[#issue1-1] 트리의 지름 개념과 구하는 방법

* 트리의 지름: 모든 경로 중에서 가장 긴 것의 길이

* 탐색 2번으로 구할 수 있다.
    * 1. root에서 모든 정점까지의 거리를 구한다. 
        이때, 가장 먼 거리였던 정점을 A라고 한다.
    * 2. A를 root라고 하고 다시 모든 정점까지의 거리를 구한다. 
        이때, 가장 먼거지인 정점과의 거리가 ‘트리의 지름’이다.

[#issue1-2] 트리와 그래프의 차이점

* 트리
    * 그래프의 특별한 케이스이며 '최소 연결 트리'라고도 불린다. 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.
    * loop나 circuit이 없다. 당연히 self-loop도 없다.
    * 한 개의 루트 노드만이 존재하며 모든 자식노드는 한 개의 부모 노드만을 가진다.
    * 부모-자식 관계이므로 흐름은 top-bottom 아니면 bottom-top으로 이루어진다.
    * 순회는 Pre-order, In-order 아니면 Post-order로 이루어진다. 이 3가지 모두 DFS/BFS안에 있다.
    * 트리는 DAG(Directed Acyclic Graphs)의 한 종류이다. DAG는 사이클이 없는 방향 그래프를 말한다.
    * 트리는 이진트리, 이진탐색트리, AVL 트리, 힙이 있다.
    * 간선은 항상 정점의 개수-1 만큼을 가진다.
    * 트리는 계층 모델이다.
* 그래프
    * 2개 이상의 경로가 가능하다. 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
    * self-loop 뿐 아니라 loop/circuit 모두 가능하다.
    * 루트 노드라는 개념이 없다.
    * 부모-자식 관계라는 개념이 없다.
    * 순회는 DFS나 BFS로 이루어진다.
    * 그래프는 순환(Cyclic) 혹은 비순환(Acyclic)이다.
    * 그래프는 크게 방향 그래프와 무방향 그래프가 있다.
    * 간선의 유무는 그래프에 따라 다르다.
    * 그래프는 네트워크 모델이다.

[#issue1-3] 이진 트리의 순회(전위, 중위, 후위 순회)

  1. 중위 순회(in-order traversal): 왼쪽 가지 -> 현재 노드 -> 오른쪽 가지
void inOrderTraversal(TreeNode node) {
      if(node != null) {
          inOrderTraversal(node.left);
          visit(node);
          inOrderTraversal(node.right);
      }
}
  1. 전위 순회(pre-order traversal): 현재 노드 -> 왼쪽 가지 -> 오른쪽 가지
void preOrderTraversal(TreeNode node) {
      if(node != null) {
          visit(node);
          preOrderTraversal(node.left);
          preOrderTraversal(node.right);
      }
}
  1. 후위 순회(post-order traversal): 왼쪽 가지 -> 오른쪽 가지 -> 현재 노드
void postOrderTraversal(TreeNode node) {
      if(node != null) {
          postOrderTraversal(node.left);
          postOrderTraversal(node.right);
          visit(node);
      }
}

[#issue2] 이진 탐색의 개념

* 이진 탐색이란
    * 정렬된 자료를 반으로 나누어 탐색하는 방법이다.
    * 데이터가 오름차순 으로 정렬되어 있어야 한다. 
    * 시간복잡도: O(log N)
    
* 이진 탐색 알고리즘 과정
    크기가 n인 리스트 data에서 target 이라는 특정 요소를 찾아낸다고 가정했을 때,
    1. low = 0, high = n-1 로 초기화한다.
    2. mid = (low + high) / 2 로 초기화한다.
    3-1. data[mid] 와 target이 같으면 탐색을 종료한다.
    3-2. data[mid] > targer 이면 high = mid-1 로 업데이트 한 후, 2번으로 돌아간다.
    3-3. data[mid] < targer 이면 low = mid+1 로 업데이트 한 후, 2번으로 돌아간다.

public int binarySearch(int[] data, int target) {
    int low = 0;
    int high = data.length - 1;
    int mid;
    
    while (low <= high) {
        mid = (low + high) / 2;

        /* 1. 구체적인 수를 찾는 경우 */
        if (target == data[mid]) 
            return mid;
        
        if (target < data[mid])
            high = mid - 1;
        else
            low = mid + 1;
        
        /* 2. 조건을 만족하는 값 중 최댓값을 구하는 경우 */
        if (target <= data[mid]) // 부등호 처리
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

Reference

🏠 Go Home