Part 09 Tree

  - tree는 규칙이 없던 그래프와 다르게 규칙이 있다.

 

1. Bynary tree

  - Bynary tree: child는 두 개만

  - 왼쪽부터 빠짐없이 채우면 => Complete Binary Tree

  - 빈 칸 없이 다 채우면 => Perfect Binary Tree

 

 

2. Tree읽는 방법

  1) DFS

  - In Order Travel: left -> root -> right

  - Pre Order Travle: root -> left -> right

  - Post Order Travel: left -> right -> root

 

  2) BFS

  - Level Order Travel

 

 

3. Heap

  - root에는 항상 최솟값이 있어야한다. => "Min heap'

  - root에는 항상 최댓값이 있어야한다. => "Max heap' 

  - 자바에서 "PriorityQueue"의 형태로 제공

    -> 작은 값부터 poll()  => Min heap

    -> 큰 값부터 poll() => reverseOrder()

  - Binary SearchTree를 이용하는 것은 대소관계를 사용한다는 것을 의미

 

  

  Note) 

  - 값이 set에 존재하는 지 확인할 때 대소관계를 확인한다.

    -> comparable이 필요하다. 

    -> comparable이 있어야 TreeSet이 동작한다.

java

열기 줄바꿈

import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;

public class BinarySearchTree {
	public static void main(String[] args){
	
		// sort: O(nlogn), binary : O(logn)
		Queue<Integer> queue = new PriorityQueue<>();		// 최댓값(최솟값) 유지
		// 괄호에 Comparator.reverseOrder()를 넣으면 내림차순
		Random r = new Random();
		
		for(int i = 0; i < 20; ++i) queue.offer(r.nextInt(50)); 
		System.out.println(queue);
		
		List<Integer> sorted = new LinkedList<>();
		while(!queue.isEmpty())  sorted.add(queue.poll());	//heap sort
		System.out.println(sorted);
	}
}

 

 

  Ex) 더 맵게

  - 스코빌 지수를 나타내는 배열과 정수k가 주어진다. 이 때 모든음식의 스코빌 지수를 K이상으로 만들기위해

  - 섞어야하는 최소횟수를 리턴한다.

  - list.remove(0): 0번째 값 꺼내기

  - answer : 섞은 횟수

  - sort를 매번 하지 않도록 min heap을 이용한다.

  - min heap이므로 sort할 필요없다.

java

열기 줄바꿈

import java.util.*;
class Solution {
    public int solution(int[] scoville, int K) {
        
        Queue<Integer> list = new PriorityQueue<>();        // Queue 구조로된 list를 만든다. (자동 오름차순 정렬)
        for(int s : scoville ){ list.add(s); }              // 스코빌의 모든 원소를 list에 복사한다.
        int answer = 0;         // 초기값 0 설정
        
        while(list.size() >= 2 && list.peek() < K){         // LIST의 사이즈가 2보다 크고  PEEK한 값이 K보다 작으면 반복실행
                
            int s1 = list.poll();
            int s2 = list.poll();
            int s3 = s1 + 2 * s2;
            
            list.offer(s3);    // s1, s2를 뽑아내고 새로운 s3을 추가한다. 
            ++answer; 
        }
        
        if( list.peek() < K)    return -1;    // WHILE문 반복한 후에도 PEEK한 값(가장작은값)이 K보다 작다면 -1 반환
        return answer;
    }
}

 

 

  Ex) 가장 먼 노드

  - n개의 노드가 있는 그래프가 있다. 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구한다.

  - 1번 노드로부터 가장 멀리 떨어진 노드의 개수를 반환한다.

java

열기 줄바꿈

import java.util.*;
class Solution{
    
    class Node{
    
        int n;
        int dist;
        boolean visit = false;
        List<Node> links = new LinkedList<>();
        
        Node(int n) {
            this.n = n;
        }
    }
    
    public int solution(int n , int[][] edge){

        List<Node> list = new LinkedList<>();
        
        for(int i = 0 ; i < n; ++i) list.add(new Node(i + 1));
        
        for(int []e: edge){		// 엣지 정보로 각 노드를 서로 연결한다.
            
            Node n1 = list.get(e[0] - 1);	// 1을 빼면 인덱스
            Node n2 = list.get(e[1] - 1);
            
            n1.links.add(n2);        // list 아니고 links!
            n2.links.add(n1);		// 쌍방향으로 연결한다.
        }
        int maxDist = 0;		// 최대길이를 구하기 위해서
        
        // BFS로 푼다.
        Queue<Node> queue = new LinkedList<>();
        
        Node first = list.get(0);   // list의 첫번째 행?? first
        first.visit = true;			// 방문여부 표시
        queue.offer(first);         // Queue에 넣는다
        
        while(!queue.isEmpty()){
            
            Node now = queue.poll();    // Queue에서 pop한 값을 now에 저장
            
            for(Node node: now.links){	// 연결된 모든 노드를 큐에 넣는다.
                if(node.visit) continue;
                node.visit = true;
                node.dist = now.dist + 1;
                queue.offer(node);
                maxDist = Math.max(maxDist, node.dist);	// 최대 거리
            }
        }
        
        int answer = 0;
        for(Node node: list){
            if(node.dist == maxDist) ++answer;		
            // 맥스 디스턴스 거리에 있는 노드를 카운트
        }
        return answer;
    }
}

 

 

  Ex) 순위 - 정확히 순서를 매길 수 있는 선수의 수를 반환

https://school.programmers.co.kr/learn/courses/30/lessons/49191

프로그래머스

  - n명의 권투 선수, 대회 참여, 

  ex)  n = 5,  [ [4, 3] ,[ 4, 2 ], [3, 2], [1, 2], [2, 5] ] return = 2;

    -> 4번 선수가 3, 2 번 선수를 이김, 3번이 2번을 이김, 2번이 5번을 이김, 1번이 2번을 이김

  - 경기횟수가 가장 많은 선수들의 순위를 알아낼 수 있다.

  - 노드를 만들고 시작

  - 선수 번호에 따라서 arrayList로 만든다.

java

열기 줄바꿈

import java.util.*;
class Solution {

    class Node{
        int n;
        int win = 0, lose = 0;
        boolean visit = false;
        List<Node> links = new LinkedList<>();
        Node(int n){this.n = n;}		// 선수 번호
    }
    
    public int solution(int n, int[][] results){
 
        List<Node> list = new LinkedList<>();
        for(int i = 0; i < n  ; ++i) list.add(new Node(i + 1)); // 선수 번호 1 ~ n번
    
        for(int [] result : results){
            
            Node winner =  list.get(result[0] - 1);   // 이긴 애들, 인덱스로 꺼내온다.
            Node loser =  list.get(result[1] - 1);  // 진 애들
            winner.links.add(loser);	// 일방향으로만 연결한다. (방향성 있기 때문에)
        }
        
       for( Node winner: list){
        
           for(Node node: list) node.visit = false; // 시작되기 전에 visit을 초기화시킨다.
           Queue<Node> queue = new LinkedList<>();
           
           winner.visit = true ;        // 위너 트루
           queue.offer(winner);	//위너부터 시작
           
           while(!queue.isEmpty()){
               
               Node now = queue.poll();
               for(Node loser : now.links){    
                   if(loser.visit) continue;
                   loser.visit = true;
                   queue.offer(loser);
                   winner.win += 1;		// 승자의 win 카운드 +
                   loser.lose += 1;		// 패자선수의 lose 카운트 + 
               }
           }
       }
        int answer = 0;
        for(Node node: list){
            if(node.win + node.lose == n - 1) ++answer;		// 최대경기횟수: n - 1
        }
        return answer;
    }
}

 

출처: https://programmers.co.kr/learn/courses/13577