[알고리즘] 6강 - 탐색(1)

✅ 1. 순차 탐색

(1) 탐색 관련 기본 개념

• 탐색: 여러 개의 원소로 구성된 데이터들 중 원하는 값을 갖는 원소를 찾는 것을 의미함.
• 데이터 형태: 주어지는 여러 개의 원소들은 리스트, 트리, 그래프 등의 여러 데이터의 집합의 형태를 가짐.
• 탐색의 종류: 외부 탐색, 내부 탐색 으로 구분이 가능함.
• 관련 연산: 탐색을 통해 원하는 원소를 찾아서 초기화, 삽입, 삭제 등의 연산을 추가적으로 진행 할 수 있음.

(2) 순차 탐색 이란?

• 순차 탐색: 리스트 형태로 주어진 데이터들을 처음부터 하나씩 순차적으로 비교하면서 원하는 값을 찾는 방법

(3) 순차 탐색 - 탐색 연산

• 탐색 연산: 배열의 크기만큼 반복을 돌면서 찾고자 하는 값과 순차적으로 비교하면서 탐색을 진행하며 데이터를 찾음.

(4) 순차 탐색 - 삽입 연산

• 삽입 연산: 단순하게 마지막 원소에 데이터를 삽입하는 연산임.

(5) 순차 탐색 - 삭제 연산

• 삭제 연산: 삭제할 원소 순차 탐색으로 찾고 삭제를 진행 한 뒤, 마지막 원소를 삭제 된 인덱스에 넣는 연산임.
• 마지막 원소를 삭제 된 인덱스에 넣는 이유는, 배열 중간에 빈 공간이 생기면 안되기 때문임.

(6) 순차 탐색 - 연결 리스트로 구현된 경우

• 연결 리스트 경우: 삽입의 경우 단순히 연결리스트의 맨 앞 부분에 삽입을 해주면 되고, 삭제의 경우 삭제 된 전후 노드를 연결해주면 됨.

(7) 순차 탐색 - 성능과 특징

• 탐색 O(n): 탐색 성공의 경우 1번~n번 비교가 되지만, 탐색 실패의 경우 항상 n 번 비교가 되기 때문에 O(n)임.
• 삭제 O(n): 삭제할 원소의 순차 탐색 O(n) 진행 후 마지막 원소의 이동은 O(1) 이므로, O(n) 임.
• 삽입 O(1): 리스트 마지막에 추가하기 때문에 상수 시간만을 요구하기 때문에 O(1) 임.
• 정렬되지 않고 크기가 작은 데이터에 적합: 모든 리스트 형태의 입력에 적용이 가능하며, 비정렬 데이터 탐색에 적합하고, 탐색과 삭제시 O(n) 시간이 필요하기 때문에 데이터가 큰 경우에는 부적합 할 수 있음.

---

✅ 2. 이진 탐색

(1) 이진 탐색 이란?

• 이진 탐색: 정렬된 리스트의 원소들을 절반씩 나누면서 원하는 값을 찾아가는 탐색 방법임.
• 연결 리스트 형태에선 이진 탐색이 불가능하며, 오직 배열에서만 가능하고 분할정복 방법이 적용되어 있음.
• 탐색 방법: 배열의 가운데 값과 탐색 키값을 비교 후 동일하다면 탐색 성공으로 반환이 되지만, 동일하지 않고 탐색키가 가운데 값보다 작다면 왼쪽 배열에서 가운데값을 반복 비교하며, 만약 탐색키가 가운데 값보다 크다면 오른쪽 배열에서 가운데값을 반복 비교를 하며 탐색을 함.

(2) 이진 탐색 - 탐색 연산

• 탐색 연산: 재귀 호출 방식을 이용하며, 키값에 대한 원소를 찾아갈 때 배열을 절반씩 줄여가는 탐색 방법을 사용함.
• 시간복잡도 O(logn): 절반씩 쪼개가면서 반복 비교를 하기 때문에, 시간복잡도는 O(logn) 이 될 수 있음.

(3) 이진 탐색 - 초기화 연산

• 초기화 연산: 이진 탐색은 주어진 배열에 대해서 항상 정렬이 되어있어야 한다는 조건이 있기 때문에, 정렬하는 과정을 초기화 연산으로 볼 수 있음.

(4) 이진 탐색 - 삽입 연산

• 삽입 연산: 이진 탐색의 로직을 활용해 삽입할 위치를 찾아주는 작업을 먼저 진행하며, 추가적으로 삽입이 될 위치로부터 다음 인덱스의 요소들을 오른쪽으로 한 칸씩 이동하고, 삽입이 될 위치에 원소를 삽입하는 과정임.
• 이진 탐색 로직을 활용해 찾고, 오른쪽으로 한 칸씩 이동하는 이유는 정렬된 상태를 유지하기 위함임.
• 시간복잡도 O(n): 이진 탐색은 O(logn) 의 시간을 가지지만, 이후, 원소 삽입이 되는 위치 오른쪽 원소들을 오른쪽으로 한 칸 씩이동하는 연산이 들어가기 때문에 O(n) 의 시간 복잡도를 가지게 됨.

• 예시를 들면, 중간값인 index 3 = 40 을 잡고, 삽입 원소(45) 와 비교를 한 뒤 40보다 크기 때문에 오른쪽 배열의 중간값인 index 5 = 60 과 45를 또 비교 한 뒤, 60보단 작기 때문에 왼쪽 배열의 index 4 = 50 과 비교를 진행하게 되는데, 이때 왼쪽 부분배열은 이미 탐색이 완료된 상태이므로, 50보다 큰 모든 데이터들을 오른쪽으로 한 칸씩 밀고 그 자리에 삽입하는 원리임.

(5) 이진 탐색 - 삭제 연산

• 삭제 연산: 삭제할 원소를 가지고 이진 탐색을 진행해 삭제하는 방식이며, 삭제가 된 원소의 빈 인덱스에는 오른쪽의 모든 요소들을 왼쪽으로 한 칸씩 이동을 시키며, 정렬상태를 유지 하게 됨.
• 시간복잡도 O(n): 이진 탐색 과정은 O(logn) 의 시간을 갖지만, 이후 삭제 과정에서 원소를 왼쪽으로 한 칸씩 이동시키며 정렬상태를 유지하기 때문에 O(n) 의 시간복잡도를 가짐.

(6) 이진 탐색 - 연결 리스트 구현시

• 연결 리스트 구조에서 삽입과 삭제는 효율적으로 가능하겠지만, 결과적으로 이진 탐색 자체가 불가능하므로, 성립이 안됨.

(7) 이진 탐색 - 성능과 특징

• 탐색 연산: O(logn) 시간복잡도를 가짐.
• 초기화 연산: O(nlogn) 이며, 이유는 정렬 수행의 결과가 O(nlogn) 임.
• 삽입/삭제 연산: O(n) 배열의 원소를 밀어주기 때문에 O(n) 만큼의 시간이 걸림.
• 정렬된 리스트에 대해서만 적용이 가능한 특징이 있음.
• 삽입과 삭제가 빈번한 경우에는 O(n) 의 데이터 이동이 필요하기 때문에 부적합하기 때문에 데이터가 작은 경우에 적합함.
• TIP: 삽입과 삭제가 빈번한 경우에도 이진 탐색을 적용하고자 해서 나온게 이진 탐색 트리 개념임.

---

✅ 3. 이진 탐색 트리

(1) 이진 탐색 트리란?

• 이진 트리: 최대 두 개의 자식 노드를 가지는 계층적인 트리 모양의 자료구조를 의미한다.
• 이진 탐색 트리: 이진 트리의 개념에 부모 노드의 왼쪽 자식 노드는 부모보다 작은 값, 오른쪽은 부모보다 큰 값의 특징을 더한 이진 트리에서 탐색을 위해 업그레이드 된 자료구조로 볼 수 있다.
• 또한, 이진 탐색 트리의 경우 연결 리스트 형태의 포인팅 구조를 가지는 특징이 있음.

(2) 이진 탐색 트리 - 탐색 연산

• 탐색 연산: 트리 구조가 주어지고, 찾고자 하는 키값 이 주어질 때, 루트 노드부터 비교를 하면서 내려가며 탐색을 진행함.
• 예를들면, 키값(40) 과 루트 노드(50) 과 비교 후 50보다 작기 때문에 왼쪽 자식 노드로 내려가게 되고, 왼쪽 자식노드(30) 과 키값(40)을 비교 후 30보다 크기 때문에 오른쪽 노드로 내려가는 식으로 데이터를 탐색을 진행함.

(3) 이진 탐색 트리 - 삽입 연산

• 삽입 연산: 삽입할 원소를 기준으로 탐색을 실시하고, 탐색이 실패할 때 해당 위치에 새 노드를 추가하는 연산임.

• 삽입 연산 예시: 삽입할 원소 65를 루트 노드부터 비교하면서 내려오게 되고, 마지막 70과 비교 후 왼쪽 노드로 가는데, 자식 노드가 없는 경우(잎 노드)이기 때문에, 이때는 탐색에 해당 값이 없다고 판단해 해당 위치에 값을 삽입함.

(4) 이진 탐색 트리 - 삭제 연산

• 후속자 노드: 어떤 노드의 바로 다음 키값을 갖는 노드로 쉽게 말해, 해당 노드의 값보다 더 큰 값이면서 다른 노드보다는 작은 값을 의미 할 수 있음.
• 위의 예시를 보면 10의 후속자 노드는 20, 20의 후속자 노드는 30... 순으로 후속자 노드를 알 수 있음.

• 삭제 연산: 삭제 연산의 경우 삭제되는 노드의 자식 노드의 개수에 따라 구분해서 처리를 하는데, 쉽게 말해 자식 노드가 0개, 1개, 2개 이 세가지 경우에 따라서 각각 다르게 삭제 연산이 처리가 됨.

• 삭제 연산 - 자식 노드가 없는 경우: 자식 노드가 없으므로, 단순히 삭제만 하면 끝남. ( 20을 그냥 삭제 하면 됨. )

• 삭제 연산 - 자식 노드가 1개인 경우: 노드 40을 삭제하는 경우 40을 탐색 후 삭제한 뒤, 그 밑의 서브트리(50, 45)를 삭제 된 노드의 위치로 올리면 끝남.

• 삭제 연산 - 자식 노드가 2개인 경우: 30을 삭제하고, 그 위치에는 30의 후속자 노드인 40을 올리게 되며, 이후 노드가 한 개인 경우가 되기 때문에 기존 40의 위치에 있던 서브트리를 그 자리로 올리면 끝남.

(5) 이진 탐색 트리 - 성능과 특징

• 탐색, 삽입, 삭제 연산은 절반씩 줄이는 이진 탐색을 기반으로 하고 있기 때문에, 트리 구조로 보면 키값을 비교하는 횟수에 비례해서 연산의 횟수를 예상 할 수 있다.
• 즉, 시간 복잡도는 키값을 비교하는 횟수에 비례한 값으로 볼 수 있으며, 이것은 이진 트리의 높이와 동일함을 알 수 있음.
• 결론은 평균 수행시간은 O(logn) 이며, 최악의 수행시간은 편향 이진 트리(경사 이진 트리) 로, 데이터의 개수만큼 탐색을 진행 할 수 있기 때문에 O(n) 이 된다.

• 삽입 연산: 경우 트리 내부의 노드 이동이 없이 잎 노드에 삽입만 진행함.
• 삭제 연산: 경우 노드를 삭제 후, 그 공간을 채우기 위해 다른 노드를 상수 번만 이동을 시킴.
• 즉, 삽입/삭제 연산 시 기존 노드의 이동이 거의 발생하지 않는 다는 특징이 있음.
• 원소의 삽입과 삭제 연산이 반복 진행이 될 때, 편향 트리 형태가 될 수 있는 가능성이 존재함.
• 균형 탐색 트리: 이진 탐색 트리는 최악의 수행시간인 O(n) 을 가질 가능성이 존재하며, 편향 트리가 만들어지지 않도록 트리의 균형을 유지해 O(logn) 을 보장하기 위해 등장한 것이 균형 탐색 트리이며, 탐색 트리의 서브트리 부분의 밸런스를 맞춰주거나 높이를 맞춰서 균형을 유지함으로써, 편향 트리를 막고 있음. ( 2-3-4 트리, 레드블랙트리, B 트리 등이 있음. )

---

✅ 4. 2-3-4 트리

(1) 2-3-4 트리란?

• 2-3-4 트리: 이진 탐색 트리의 삽입/삭제 연산에 따라 편향 트리가 되는 것을 막기 위해 등장한 균형 탐색 트리이다.
• 쉽게 말해, 하나의 노드에 여러개의 키를 가질 수 있으며, 키값의 개수에 따라 자식 노드의 개수도 여러개 가질 수 있음.
• 2-노드, 3-노드, 4-노드로 구성이 되며, 각각 1~3개의 키와 2~4개의 자식 노드를 갖는 특징을 가지고 있음.

• 3-노드: 경우 위와 같이 2개의 키를 가지며, 3개의 자식 노드를 가질 수 있음.
• 4-노드: 3개의 키와 4개의 자식 노드를 가질 수 있는 노드를 의미함.

(2) 2-3-4 트리 - 탐색 연산

• 탐색 연산: 이진 트리와 동일한 방식으로 탐색을 진행하며, 노드의 키값은 여러개 존재 할 수 있기 때문에 각 키값이 가지는 범위에서 크고 작고를 판단해 탐색을 진행함.

(3) 2-3-4 트리 - 삽입 연산

• 삽입 연산: 이진 탐색 트리와 동일하게 탐색 과정(크고 작고 비교 후)을 거친 후, 잎 노드에 도달하면 해당 위치에 삽입함.
• 하지만, 4-노드(키값이 3개, 자식 노드 4개인 경우) 를 만나게 되면, 탐색 과정에서 항상 노드 분할 우선적으로 수행함.
• 노드 분할: 삽입을 진행하기 전 탐색과정을 진행 할 때, 4-노드를 만나게 되면, 해당 4-노드의 가운데 키값을 부모 노드의 키값으로 올리는 것을 의미함.
• 결론: 탐색과정에서 4-노드에 대한 노드 분할을 진행한 뒤, 이진 탐색 트리와 동일하게 잎 노드에 삽입을 진행함.

(4) 2-3-4 트리 - 삽입 연산 예시

• (1) 먼저 위의 키값을 순서대로 2-3-4 트리에 삽입을 진행
• (2) 50 삽입: 노드 생성 및 키값 50 삽입
• (3) 55 삽입: 50과 비교 후 55가 더 크기 때문에, 50의 오른쪽 키값으로 삽입.
• (4) 30 삽입: 30은 50, 55보다 작기 때문에 맨 왼쪽 키값으로 삽입.
• (5) 10 삽입: 4-노드(30,50,55)를 분할하게 된 후, 대소 비교 후 숫자에 맞는 위치에 삽입을 진행함.
• 4-노드에 대해서 분할 과정을 제외하면, 나머지는 이진 탐색 트리의 삽입 연산과 동일하게 진행됨.

(5) 2-3-4 트리 - 성능과 특징

• 탐색, 삽입, 삭제 연산 시간 복잡도 O(logn): 이진 탐색 트리의 경우 탐색 과정만 logn 의 시간 복잡도를 가졌고 삽입과 삭제 연산에는 편향 트리가 만들어져 O(n) 의 시간복잡도를 가질 수 있는 문제가 있음.
• 하지만, 2-3-4 트리는 이진 탐색 트리를 개선한 균형 탐색 트리로써 탐색, 삽입, 삭제 연산 모두 O(logn) 의 시간복잡도를 가짐.
• 삽입/삭제가 일어나도 편향 트리가 되지 않음: 4-노드 상태에서 삽입 연산에는 분할을 진행하고, 루트 노드가 분할될 시에만 모든 노드의 레벨이 1씩 증가하기 때문에 편향트리가 안만들어짐.
• 문제점: 2-3-4 트리를 그대로 구현하면 2, 3, 4 노드 등으로 노드 구조가 나뉘어 복잡해지기 때문에 이진 탐색 트리보다 더 느려질 가능성이 많으며, 이러한 2-3-4 트리를 이진 탐색 트리로 변경한 트리는 레드 블랙 트리임.
• 쉽게 말해, 2-3-4 트리는 한 노드에 값 최대 3개까지 존재하며, 자식 최대 4개까지 존재 할 수가 있어서 비교 연산시 노드 내부에서 여러 값을 비교하게 된다. 즉, 노드 내부 비교 비용이 증가해 BST 는 1번 비교 할 때, 2-3-4 트리는 최대 3번까지 비교함 한 단계 내려갈 때 비용이 더 큰 문제가 있음. 그래서 보통 2-3-4 트리는 직접 안쓰고 레드-블랙 트리로 변환해서 사용함.