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이 동작한다.
<hide/>
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할 필요없다.
<hide/>
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번 노드로부터 가장 멀리 떨어진 노드의 개수를 반환한다.
<hide/>
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
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
- 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로 만든다.
<hide/>
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;
}
}