Day12

Day12

트리(Tree)

• 문제 : 트리 순회
• 정답코드 ```javascript

## 우선순위 큐(Heap)

- 우선순위가 높은 요소가 먼저 나가는 특징을 가진다.
- 루트가 가장 큰 값이 되는 최대 힙(Max Heap)과 루트가 가장 작은 값이 되는 최소 힙(Min Heap)이 있다.
- javascript 에서는 직접 구현해야 한다.

- 문제 : [더 맵게](https://school.programmers.co.kr/learn/courses/30/lessons/42626)
- 정답코드
```javascript

트라이(Trie)

• 문자열을 효율적으로 탐색하기 위한 트리 형태의 자료구조
• 검색어 자동완성, 사전 찾기 등에 응용될 수 있다.
• 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있다.
• L이 문자열의 길이일 때, 삽입은 O(L)만큼 걸린다.
• 각 정점이 자식에 대한 링크를 전부 가지고 있기 때문에 저장 공간을 더 많이 사용한다.
• 루트는 비어있다.
• 각 간선은 추가될 문자를 키로 가진다.
• 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가진다.

• 해시 테이블과 연결 리스트를 이용하여 구현할 수 있다.

• 문제 : 가사 검색
• 정답코드 ```javascript

- 문제 : [자동완성](https://school.programmers.co.kr/learn/courses/30/lessons/17685)
- 정답코드
```javascript

정렬

• 정렬 기준은 사용자가 정할 수 있다.
• 크게 비교식과 분산식 정렬로 나눌 수 있다.
• 대부분의 언어가 빌트인으로 제공해준다.
• 비교식 정렬
  • 버블 정렬 : 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘, O(n²)의 시간 복잡도를 가진다.
  • 선택 정렬 : 선택한 요소와 가장 우선순위가 높은 요소를 교환하는 정렬 알고리즘, O(n²)의 시간 복잡도를 가진다.
  • 삽입 정렬 : 선택한 요소와 삽입할 수 있는 위치를 찾아 삽입하는 방식의 정렬 알고리즘, O(n²)의 시간 복잡도를 가진다.
• 분산식 정렬
  • 합병 정렬 : 분할 정복 알고리즘을 이용한 최선과 최악이 같은 안정적인 정렬 알고리즘, O(n log n) 시간 복잡도를 가진다.
  • 퀵 정렬 : 분할 정복 알고리즘을 이용한 매우 빠르지만 최악의 경우가 존재하는 불안정한 정렬, O(n log n) 시간 복잡도를 가진다.
• 문제 : 가장 큰 수
• 정답코드

function solution(numbers) {
    let answer = numbers.sort((a, b) => `${b}${a}` - `${a}${b}`).join('');
    return answer[0] === '0' ? '0' : answer;
}

이진 탐색

• 정렬 되어있는 요소들을 반씩 제외하며 찾는 알고리즘, O(log n)만큼 시간복잡도가 걸린다.
• 반드시 정렬이 되어있어야 사용할 수 있다.
• 배열 혹은 이진 트리를 이용하여 구현할 수 있다.
• O(log n) 시간복잡도인 만큼 상당히 빠르다.
• 최악의 경우 한쪽으로 편향된 트리가 될 수 있다.
• 그런 경우 순차 탐색과 동일한 시간 복잡도를 가진다.
• 이를 해결하기 위해 다음과 같은 자료 구조를 이용할 수 있다.
  • AVL 트리
  • 레드-블랙 트리
• 문제 : 입국심사
• 정답코드

// 로그 시간 = 이진 탐색
// times -> 선형 로그 시간으로 충분히 가능!
// 우리는 특정 값을 찾는 것이 아님
// 우리가 찾는 것은 최소 몇 분에 모든 심사가 끝나는가?
// 결정문제 = 이진 탐색 = 파라매트릭 서치(Parametric Search)

// 최소 1분에서 (10억 * n)분
// 면접관들이 몇 명을 처리하는가?
// 처리 가능한 입국자 n보다 작다면 분을 올려야되고 입국자가 n보다 크다면 분을 낮춘다.
// 면접관이 시간대비 몇 명을 처리할 수 있는가?
// 시간 / 심사시간 = 심사관 당 처리 가능한 입국자 수

function solution(n, times) {
    // 이진 탐색을 이용하기 위해 정렬해줌.
    const sortedTimes = times.sort((a, b) => a - b);
    let left = 1;
    let right = n * sortedTimes[sortedTimes.length - 1];

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        // sum(시간 / 심사시간)
        const sum = times.reduce((acc, time) => acc + Math.floor(mid / time), 0);

        if(sum < n) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return left;

}