[TIL] 🌱 2023.04.26 - Async

🛹 목표

목표	난이도	달성 여부
IT 관련 기사 읽기	下	✔️
패스트 캠퍼스 강의 듣기	上	✔️
알고리즘 문제풀이	上	✔️

---

📋 공부 내용 & 기록

@Async에 대한 이해

GitHub - lmw7414/practice-async

알고리즘 문제풀이

프로그래머스

임의의 숫자를 포화 이진트리로 만들 수 있는지에 관한 문제이다.

 

이 문제를 해결하기 위해 알고 있어야하는 내용

 

1. 포화 이진트리(Perfect Binary Tree)의 정의

포화 이진트리는 모든 높이(레벨)에서 노드들이 꽉 차 있어야 한다. 즉 리프 노드를 제외한 부모노드는 2개의 자식을 가지고 있다.

높이 h(루트 높이 0 기준)에서 가질 수 있는 노드의 수는 2^(h+1) - 1로 1 → 3 → 7 → 15 →31 ··· 순으로 점점 커진다.

 

2. 십진수를 이진수로 변환하는 알고리즘

자바에서는 변환 메서드를 제공한다.

int a = 15;
String binaryA = Integer.toBinaryString(a);          // 1111
int binaryToDecimal = Integer.parseInt(binaryA, 2);  // 15

 

3. 중위 순회

루트 노드의 왼쪽 자식 노드를 먼저 탐색 후, 루트 노드를 탐색하고, 오른쪽 자식 노드를 탐색한다.

 

문제를 풀기 위한 알고리즘 [코드 포함]

1. 십진수를 이진수로 변환 후, 포화 이진트리로 만들기

public static String toPBT(long num) {
    String bNum = Long.toBinaryString(num);
    int depth = findDepth(bNum.length()) + 1;          
    long n = (long)Math.pow(2, depth) - 1;              // 포화 이진 트리의 사이즈
    String zero = "0".repeat((int)(n - bNum.length())); 
    return zero + bNum;  // 이진수를 포화 이진트리로 만들기 위해 왼쪽에 0 추가 후 리턴
}
        
public static int findDepth(int length) {
    int i = 0;
    while(true) {
    	if((long)Math.pow(2, i) > length)
            return i - 1;
        i += 1;
    }
}

 

변환된 이진수를 포화 이진트리를 만들기 위해서는 이진수의 길이가 포화 이진트리의 크기와 같아야 한다. 즉 1 → 3 → 7 → 15 →31 ···으로 커지는 포화 이진트리의 크기와 일치해야한다. 해당 이진수에 맞는 포화 이진 트리의 크기를 구하고 크기에서 이진수의 길이를 제외하고 남은 부분을 0으로 채웠다. 

 

2. 해당 이진수가 포화 이진트리인지 탐색

public static boolean dfs(String bNum, int rootIdx, int depth) {
    int lIdx = rootIdx - (int)Math.pow(2, depth - 1);
    int rIdx = rootIdx + (int)Math.pow(2, depth - 1);
    if(depth == 0)
        return true;
    if(bNum.charAt(rootIdx) == '0') {
        if(bNum.charAt(lIdx) == '1' || bNum.charAt(rIdx) == '1')
            return false;
    }

    boolean left;
    boolean right;
    // 왼쪽 서브트리
    left = dfs(bNum, lIdx, depth - 1);
    // 오른쪽 서브트리
    right = dfs(bNum, rIdx, depth - 1);

    return left && right;
}

해당 메서드에서 핵심은 부모노드가 0일 경우 자식 노드 중에 1이 있으면 안된다는 조건이다.

깊이가 0인 경우는 이미 자식 노드에 도달한 것이므로 자식이 0 이든 1 이든 상관없으므로  조건을 만족한다.

---