TIL : 23-07-02

오늘 한 일

• 코딩테스트 > 트리

---

코딩테스트 > 트리

트리로 풀어야 할 코딩테스트 문제로는 무엇이 있을까?

아래는 트리 중에서도 이진 탐색에 적합한 문제 유형들입니다.
이진 탐색에 대해 간단히 설명하자면...

• 이진 탐색은 정렬된 배열이나 리스트에서 특정 요소를 빠르게 찾는 알고리즘으로,
• 탐색 범위를 반으로 나누어가면서 효율적으로 탐색을 진행합니다.

1. 정렬된 배열에서 요소 찾기: 주어진 정렬된 배열에서 특정 값을 찾는 문제입니다. 배열을 반으로 나누어 찾고자 하는 값이 있는 범위를 좁혀나가면서 탐색합니다.

2. 특정 값의 존재 여부 확인: 주어진 정렬된 배열에서 특정 값의 존재 여부를 확인하는 문제입니다. 값을 찾는 대신 값의 존재 여부만 확인하면 되므로, 탐색 과정에서 값이 정확히 일치하는지를 확인하는 조건문을 추가로 사용합니다.

3. 정렬된 배열에서 특정 값의 인덱스 찾기: 정렬된 배열에서 특정 값의 인덱스를 찾는 문제입니다. 값을 찾는 대신 값의 인덱스를 반환하거나, 값이 존재하지 않을 경우 -1과 같은 특정 값을 반환하는 방식을 사용합니다.

4. 최솟값 또는 최댓값 찾기: 주어진 정렬된 배열에서 최솟값이나 최댓값을 찾는 문제입니다. 이진 탐색을 활용하여 탐색 범위를 좁혀가면서 최솟값 또는 최댓값을 찾을 수 있습니다.

5. 결정 문제: 주어진 조건을 만족하는 최솟값 또는 최댓값을 찾는 문제입니다. 이진 탐색을 이용하여 값을 찾는 것이 아니라, 조건을 만족하는지 여부를 결정하고자 하는 문제입니다.