# Understanding Special Alignment in Computer Algorithms (2/3)

**Contents**

**1️⃣** 기수 정렬 (radix sort)  
**2️⃣** 계수 정렬 (counting sort)  
**3️⃣** 버킷 정렬 (bucket sort)

---

## **1️⃣** 기수 정렬 (radix sort)

### **기수 정렬(radix sort)의 개념**

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727848365775/37250d10-6033-4361-98a9-b12fff10676d.png align="center")

* \*\*기수 정렬(Radix Sort)\*\*은 정수나 문자열을 자리수별로 비교하여 정렬하는 알고리즘이다.
    
* 주어진 원소들을 가장 낮은 자릿수부터 차례대로 큐를 이용하여 재배열하고, 자릿수별로 정렬을 반복함으로써 전체 원소를 정렬한다.
    

### 기수 정렬의 적용 조건:

* **원소들이 모두 상수** `k`개 이하의 자릿수를 가진 자연수 또는 알파벳 등 문자일 경우:
    
    * 기수 정렬은 주어진 원소들이 특정한 자릿수를 가지는 경우에 유효하다.
        
    * 예를 들어, 자릿수가 3자리 이하인 정수들이나 일정한 길이의 문자열 정렬에 적합하다.
        

### **예제 설명:**

* **첫 번째 자리(First digit)**: 4
    
* **두 번째 자리**: 5
    
* **세 번째 자리**: 3
    
* **네 번째 자리**: 1
    

이렇게 자릿수를 기준으로 각 자리의 값을 비교하면서 정렬을 수행하는 것이 기수 정렬의 방식이다.

### **기수 정렬의 작동 예시**

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727848536335/dd0b14f2-97bc-4980-bf31-0cd7db40d861.png align="center")

기수 정렬은 각 자릿수를 차례로 비교하여 재배열하는 방식으로, 낮은 자릿수부터 높은 자릿수까지 정렬을 수행하여 최종적으로 전체 원소가 정렬된다. 이미지를 자세히 살펴보자.

### 이미지 설명:

1. **첫 번째 자릿수로 재배열**:
    
    * 가장 낮은 자릿수(1의 자리) 기준으로 정렬을 수행한다.
        
    * 결과적으로 1의 자릿수가 작은 순서대로 재배열되었다.
        
2. **두 번째 자릿수로 재배열**:
    
    * 두 번째 자릿수(10의 자리)를 기준으로 재배열한다.
        
    * 첫 번째 자릿수의 순서를 유지하며, 두 번째 자릿수가 작은 순서대로 재정렬되었다.
        
3. **세 번째 자릿수로 재배열**:
    
    * 세 번째 자릿수(100의 자리)를 기준으로 정렬한다.
        
    * 앞서 정렬된 순서를 유지하면서 100의 자릿수가 작은 순서대로 재배열되었다.
        
4. **네 번째 자릿수로 재배열**:
    
    * 네 번째 자릿수(1000의 자리)를 기준으로 정렬한다.
        
    * 모든 자릿수를 기준으로 정렬이 완료되었기 때문에 최종적으로 정렬된 상태가 된다.
        

### **기수 정렬의 의사코드(pseudocode)**

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727848741742/88ec01f3-4de0-4968-b452-93c25a89e151.png align="center")

### 의사코드 설명:

1. `radixSort(A[], n, k)`:
    
    * `A[]`: 정렬할 배열을 뜻한다.
        
    * `n`: 배열의 크기, 즉 원소의 개수이다.
        
    * `k`: 각 원소가 가질 수 있는 최대 자릿수를 뜻한다.
        
2. **알고리즘 설명**:
    
    * **첫 번째 조건**:
        
        * 원소들이 최대 `k` 자릿수 이하인 배열 `A[0...n-1]`을 정렬한다.
            
    * **두 번째 조건**:
        
        * 가장 낮은 자릿수를 1번째 자릿수로 간주하고, 이 자릿수부터 시작하여 정렬을 진행한다.
            
3. `for` 루프:
    
    * `for i = 1 to k`
        
        * `i`번째 자릿수에 대해 배열 `A[0...n-1]`을 정렬한다.
            
        * 이때 **안정성을 유지하면서 정렬**해야 한다.
            
        * 안정성(Stability)이란 동일한 자릿수를 가진 원소들이 정렬 후에도 기존 순서를 유지하는 것을 의미한다. 이를 통해 각 자릿수의 정렬이 이전 자릿수의 정렬에 영향을 미치지 않는다.
            

### **기수 정렬에서 각 자리수의 정렬**

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727854472902/8c22b6bd-022f-43b0-bdaf-5803d711026f.png align="center")

기수 정렬은 일반 정렬 알고리즘보다 효율적으로 동작할 수 있으며, 각 자릿수를 기준으로 데이터를 재배열하여 전체 배열을 정렬한다. 각 자릿수 정렬 시 큐를 사용함으로써 안정성을 유지하고 복잡도를 줄이는 것이 핵심이다.

### 내용 요약:

1. **복잡도 분석**:
    
    * 알고리즘 1-1에서 첫 번째 자릿수를 정렬할 때, 일반적인 정렬 알고리즘을 사용하면 시간 복잡도는 `O(n log n)` 이상이 필요하다.
        
    * 그러나 기수 정렬은 각 자릿수를 기준으로 큐(Queue) 같은 데이터 구조를 사용하여 재배열함으로써, 복잡도를 줄일 수 있게된다.
        
2. **각 자릿수의 정렬 과정**:
    
    * 이미지의 예시는 각 자릿수의 값을 기준으로 데이터가 어떻게 재배열되는지 보여주고 있다.
        
    * 예를 들어, 1의 자릿수를 기준으로 데이터를 분류하고, 정렬이 완료되면 10의 자릿수, 100의 자릿수, 그리고 그 이상의 자릿수를 순서대로 정렬한다.
        
    * **데이터 삽입**과 **데이터 출력**의 과정을 반복하면서 각 자릿수의 값에 따라 데이터가 큐 구조에 저장되고 다시 출력된다.
        
3. **큐(Queue)를 이용한 정렬**:
    
    * 각 자릿수의 값을 기준으로 데이터가 재배열될 때, 큐를 이용하여 정렬을 수행한다.
        
    * 큐의 `FIFO(First-In, First-Out)` 속성 덕분에 각 자릿수 정렬이 안정성을 유지할 수 있다.
        
4. **결과**:
    
    * 모든 자릿수에 대해 정렬이 끝난 후, 최종적으로 정렬된 데이터는 \[03, 16, 18, 23, 24, 77, 80, 88\]과 같은 순서로 완성되었다.
        
    * 이미지에서는 데이터의 최종 정렬 결과를 아래쪽에 표시하여, 각 자릿수별 정렬이 전체 정렬로 어떻게 이어지는지 보여주고 있다.
        

### **기수 정렬의 시간 복잡도**

1. **각 자릿수의 정렬**:
    
    * 알고리즘 4-20에서 각 자릿수를 큐를 이용하여 재배열한다.
        
    * 각 자릿수마다 원소들을 정렬하는 데 걸리는 시간 복잡도는 `O(n)`이다.
        
        * `n`은 정렬할 배열의 원소 개수이다.
            
2. **전체 시간 복잡도**:
    
    * 배열의 모든 자릿수(`k`개)에 대해 정렬을 수행해야 한다.
        
    * 따라서 전체 시간 복잡도는 자릿수(`k`)와 배열의 원소 개수(`n`)를 곱한 `O(kn)`이 된다.
        

### 요약:

* **각 자릿수의 시간 복잡도**: `O(n)`
    
* **전체 정렬의 시간 복잡도**: `O(kn)`, 여기서 `k`는 자릿수의 개수, `n`은 배열의 원소 개수이다.
    

---

## **2️⃣** 계수 정렬 (counting sort)

### 계수 정렬(counting sort)의 개념

* \*\*계수 정렬(Counting Sort)\*\*은 원소들의 **값의 빈도수**를 세어 이를 기반으로 정렬하는 알고리즘이다.
    
* 배열의 원소들을 훑어보면서 0부터 k까지 각 값이 몇 번 나타나는지 세고, 이 빈도수를 이용하여 정렬된 배열을 생성하게 된다.
    
* k 값의 예시로는 2n 이하의 자연수, 상수 1000을 넘지 않는 음이 아닌 정수 등
    
* 계수 정렬은 **값의 범위가 제한된 경우**에 효과적인 정렬 알고리즘이다.
    
* 각 값의 **빈도수**를 세어 정렬을 수행하므로, 원소의 값이 특정 범위에 속하는 경우 `O(n + k)`의 시간 복잡도를 가지게 된다.
    

### 계수 정렬의 작동 예시

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727924121871/24da7859-1641-4bc0-8a72-5f657747cabb.png align="center")

위 예시는 계수 정렬이 **값의 빈도수를 세고**, **누적합을 통해 정렬 위치를 계산**한 후, 최종적으로 **정렬된 배열을 생성**하는 과정을 시각적으로 보여주고 있다.

1. **입력 배열**:
    
    * 입력 배열은 `A[0...14]`로, 15개의 원소로 구성되어 있다.
        
    * 각 원소는 `0`부터 `12` 사이의 값을 가질 수 있다.
        
2. **카운팅 배열 생성 (b 단계)**:
    
    * \*\*카운팅 배열 `C[0...12]`\*\*를 생성하여, 각 값이 몇 번 나타났는지를 세어 저장한다.
        
    * 예시에서는 `C[i]`에 `i`값이 나타난 빈도수가 저장된다.
        
        * 예: `C[0] = 1`, `C[2] = 4` (즉, 0은 1번, 2는 4번 나타났음을 의미한다).
            
3. **누적합 계산 (c 단계)**:
    
    * 카운팅 배열 `C[]`의 값을 **누적합**으로 바꾼다.
        
    * 누적합을 통해 특정 값이 정렬된 배열에서 어느 위치에 배치될지 알 수 있다.
        
        * 예: `C[2] = 4`는 값 `2`가 정렬된 배열에서 4번째 위치까지 나타난다는 것을 의미한다.
            
4. **정렬된 배열 생성 (d 단계)**:
    
    * `B[]` 배열을 생성하여 정렬된 값을 저장한다.
        
    * `A` 배열의 값을 뒤에서부터 확인하며, `C[]` 배열의 값을 참고하여 `B[]`에 값을 배치한다.
        
        * 예: `A` 배열의 마지막 원소 `0`은 `B` 배열의 `0번째` 위치에 배치되고, `C[0]`의 값은 `1`에서 `0`으로 감소하게 된다.
            
    * 이 과정을 반복하여 `B` 배열에 정렬된 값들이 저장된다.
        

### 정렬 과정 요약:

* (b) 단계에서 **빈도수**를 세어 `C` 배열에 저장하고,
    
* (c) 단계에서 **누적합**을 계산하여 `C` 배열의 값을 업데이트한 후,
    
* (d) 단계에서 `B` 배열에 **정렬된 값**을 저장함으로써 전체 정렬이 완료된다.
    

### 결과:

최종적으로, `B` 배열에는 \[0, 1, 2, 2, 5, 6, 7, 8, 8, 8, 10, 10, 11, 11, 12\]와 같이 정렬된 값들이 저장된다.

---

### 계수 정렬의 의사코드

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727924839027/0cab8ff1-d3e4-42f0-abef-90c4567a3b52.png align="center")

1. **초기화**: for i ← 0 to k: // C\[i\] ← 0
    
    * `C[]` 배열을 0으로 초기화하였다.
        
    * `C[i]`는 값 `i`가 몇 번 나타나는지 기록하는 배열이다.
        
2. **값의 빈도수 계산**: for j ← 0 to n-1; // C\[A\[j\]\]++
    
    * 입력 배열 `A[0...n-1]`의 각 원소값을 확인하며, 해당 값의 빈도수를 `C[]` 배열에 저장한다.
        
    * 예를 들어, `A` 배열에 값 `2`가 3번 나타난다면 `C[2]`의 값은 `3`이 된다.
        
3. **누적합 계산**: for i ← 1 to k: // C\[i\] ← C\[i\] + C\[i-1\]
    
    * `C[]` 배열의 값을 누적합으로 변환한다.
        
    * `C[i]`는 `i` 값이 정렬된 배열에서 몇 번째 위치까지 나타나는지를 나타낸다.
        
    * 누적합을 통해 `i` 값이 `B` 배열의 어느 위치에 배치될지를 알 수 있다.
        
4. **정렬된 배열 생성**
    
    * 입력 배열 `A`를 뒤에서부터 순회하며, `C[]` 배열의 값을 참고하여 정렬된 배열 `B`에 값을 배치한다.
        
    * 예: `A[j]`가 `2`라면, `C[2]`의 값이 `4`일 때 `B[3]` 위치에 `2`를 배치하고, `C[2]`의 값을 1 감소시킨다.
        
5. **배열** `B`에 값 저장 및 인덱스 감소:
    
    * `A[j]`의 값을 `B[C[A[j]]-1]`에 저장하고, `C[A[j]]`의 값을 감소시킨다.
        
    * 이는 `A` 배열의 값을 `B` 배열에 올바른 순서로 배치하기 위한 과정이다.
        
6. **정렬된 배열** `B` 반환:
    
    * 최종적으로 정렬된 배열 `B`를 반환한다.
        

---

### 계수 정렬의 각 배열의 관계

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727926985560/be532bf5-a7dd-4a38-92c1-e0ecac02e9c2.png align="center")

이미지는 \*\*계수 정렬(Counting Sort)\*\*의 카운팅 배열(`C[]`)과 결과 배열(`B[]`)의 관계를 시각적으로 설명하고 있다.

### 이미지 설명:

1. **입력 배열** `A[0...n-1]`:
    
    * `A` 배열은 정렬할 원소들을 담고 있는 입력 배열이다.
        
    * 배열의 각 요소는 `y`와 같은 특정 값으로 표현된다.
        
2. **카운팅 배열** `C[0...k]`:
    
    * `C` 배열은 `A` 배열의 각 값이 몇 번 나타나는지 **빈도수**를 저장한 배열이다.
        
    * 예시에서 `y`의 빈도수는 `q`로 표시되어 있다.
        
    * 이 배열의 값을 누적합으로 변환하면 `A` 배열의 원소들이 `B` 배열에 배치될 위치를 계산할 수 있다.
        
3. **결과 배열** `B[0...n-1]`:
    
    * `B` 배열은 정렬된 결과를 담는 배열이다.
        
    * 예시에서는 `x`, `y`, `z`와 같은 값들이 정렬된 순서로 나타나 있다.
        
    * 예를 들어, `y`가 3번 나타났다면 `B` 배열의 연속된 세 칸에 `y`가 차례로 저장되게 된다.
        

---

### 계수 정렬의 시간 복잡도

<mark>요약:</mark>

* **각 단계의 시간 복잡도**:
    
    * 1단계와 3단계: `Θ(k)`
        
    * 2단계와 4단계: `Θ(n)`
        
* **전체 시간 복잡도**: `Θ(n + k)`
    
* 만약 `k`가 `O(n)`일 때, 전체 시간 복잡도는 `Θ(n)`
    
* **알고리즘 2-1의 1단계와 3단계**:
    
    * **1단계**와 **3단계**에서 사용하는 `for` 루프의 시간 복잡도는 각각 `Θ(k)`.
        
    * 여기서 `k`는 **카운팅 배열** `C[]`의 크기, 즉 입력 배열 `A[]`의 원소들이 가질 수 있는 최대 값.
        
    * 1단계: `C[]` 배열을 0으로 초기화하는 작업이므로 `Θ(k)` 시간.
        
    * 3단계: `C[]` 배열의 값을 누적합으로 변환하는 작업이므로 `Θ(k)` 시간.
        
* **알고리즘 2-1의 2단계와 4단계**:
    
    * **2단계**와 **4단계**에서 사용하는 `for` 루프의 시간 복잡도는 각각 `Θ(n)`입니다.
        
    * 여기서 `n`은 **입력 배열** `A[]`의 크기, 즉 배열에 있는 원소의 개수입니다.
        
    * 2단계: `A[]` 배열의 각 원소를 순회하며 `C[]` 배열에 빈도수를 기록하는 작업이므로 `Θ(n)` 시간.
        
    * 4단계: `A[]` 배열을 뒤에서부터 순회하며 정렬된 배열 `B[]`에 값을 배치하는 작업이므로 `Θ(n)` 시간.
        
* **전체 시간 복잡도**:
    
    * 전체 시간 복잡도는 각 단계의 시간 복잡도의 합으로 계산된다.
        
    * 1단계 (`Θ(k)`) + 2단계 (`Θ(n)`) + 3단계 (`Θ(k)`) + 4단계 (`Θ(n)`) = `Θ(n + k)`
        
    * 만약 `k`가 `O(n)`이라고 가정할 수 있다면, 전체 시간 복잡도는 `Θ(n)`이 된다.
        

---

### **3️⃣** 버킷 정렬 (bucket sort)

버킷 정렬은 원소들이 균등하게 분포되어 있을 때 최적의 성능을 발휘하는 정렬 알고리즘이다. 그래프에서 보여지는 것처럼 값들이 고르게 분포되어 있는 경우, 각 버킷에 원소들이 균일하게 나뉘어지며, 이를 통해 빠른 정렬을 수행할 수 있게된다.

### 버킷 정렬의 조건

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727930079549/d3ead243-3450-4e3a-8e53-c8b5b781d2a4.png align="center")

**정렬하고자 하는 원소들이 균등 분포를 이룰 때**:

* 버킷 정렬은 원소들이 특정 범위 내에서 **균등하게 분포**되어 있을 때 가장 효율적으로 동작한다.
    
* 균등 분포(Uniform Distribution)란 원소들이 일정한 범위 내에서 고르게 퍼져 있는 상태를 의미한다.
    

---

### 버킷 정렬의 작동 과정

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727930293160/b5b85e76-e6d7-485f-becc-43851c9f23c3.png align="center")

1. **입력 배열 준비**:
    
    * 입력 배열 `A[0...14]`는 값의 범위가 `0`에서 `1` 사이로 **균등 분포(**Uniform Distribution)를 이루고 있다.
        
    * 예시에서 `A` 배열의 원소들은 \[0.38, 0.94, 0.48, 0.73, ... , 0.02\]와 같이 소수 값을 가진다.
        
2. **버킷 번호 계산**:
    
    * 각 원소를 버킷에 배치하기 위해, 각 원소의 값에 **15를 곱하여 정수부만 취한다.**
        
    * 예: `A[0] = 0.38`일 때, `15 * 0.38 = 5.7`이므로, 정수부는 `5`이다. 따라서, `A[0]`은 5번 버킷에 배치된다.
        
    * 이 과정을 통해 `A` 배열의 각 원소가 어느 버킷에 들어갈지 결정된다.
        
    * \*\*(b 단계)\*\*에서는 각 원소가 대응되는 버킷의 번호를 나타내고 있다.
        
3. **버킷 리스트에 원소 삽입**:
    
    * 각 원소를 계산된 버킷 번호에 따라 \*\*버킷 리스트 `B`\*\*에 삽입한다.
        
    * 예: `0.02`는 0번 버킷에, `0.38`은 5번 버킷에, `0.48`은 7번 버킷에 삽입된다.
        
4. **각 버킷 정렬**:
    
    * 버킷 리스트의 각 버킷 내의 원소들을 **삽입 정렬**과 같은 간단한 정렬 알고리즘을 이용하여 정렬한다.
        
    * 예: 5번 버킷에 있는 값 `0.38`과 `0.43`은 삽입 정렬을 통해 정렬된 상태로 유지된다.
        
    * 이 단계에서 \*\*(d)\*\*의 `B` 배열과 같이 각 버킷에 속한 값들이 정렬된다.
        
5. **정렬된 원소를 차례로** `A` 배열에 복사:
    
    * 각 버킷의 정렬된 원소들을 차례로 꺼내어 최종적으로 `A` 배열에 배치한다.
        
    * 예: 0번 버킷의 값 `0.02`, 1번 버킷의 값 `0.10` 등이 차례로 `A` 배열에 복사된다.
        
    * 최종적으로 (e 단계)의 `A` 배열에 정렬된 값들이 저장된다.
        

---

### 버킷 정렬의 의사코드

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727931100712/7fea78a7-f5ac-40d1-a3ce-e980c0dc5f02.png align="center")

**주요 포인트:**

* `B` 배열은 **리스트로 구성된 배열**로, 각 리스트가 하나의 버킷을 의미한다.
    
* 입력 배열 `A`의 값은 `[0, 1]` 범위의 **균등 분포된 실수**이기 때문에, 이 값들을 적절한 버킷에 나누어 삽입한 후 정렬하게 된다.
    
* 각 버킷의 내부를 정렬한 후, 정렬된 원소들을 `A` 배열에 차례대로 복사함으로써 최종 정렬된 배열을 완성할 수 있다.
    

**각 단계 설명:**

1. **버킷에 원소 삽입**:
    
    * 입력 배열 `A`의 각 원소 `A[i]`를 해당하는 버킷 `B[nA[i]]`에 삽입한다.
        
    * 예를 들어, 원소 `A[i]`의 값이 `0.38`이라면 `n`을 15로 가정할 때, `B[15 * 0.38] = B[5]`에 삽입된다.
        
    * 여기서 `B`는 `n`개의 버킷을 갖는 리스트 배열이다.
        
2. **각 버킷 내부 정렬**:
    
    * 각 버킷 `B[i]`의 원소들을 정렬한다.
        
    * 버킷 내 원소의 개수가 적기 때문에, 삽입 정렬(Insertion Sort)과 같은 간단한 정렬 알고리즘을 사용해도 충분히 효율적이다.
        
3. **정렬된 원소들을 배열** `A`로 복사:
    
    * 정렬된 각 버킷 `B[i]`의 원소들을 차례대로 배열 `A`에 복사하여 최종 정렬된 배열을 만든다.
        
    * 복사할 때는 버킷의 순서를 유지하면서, 모든 버킷의 원소들을 차례대로 배열 `A`에 추가한다.
        

---

### 버킷 정렬의 시간 복잡도 1

**<mark>요약:</mark>**

* **각 원소의 버킷 삽입**: `Θ(1)`
    
* **전체 원소의 버킷 삽입**: `Θ(n)`
    

* **버킷에 원소 삽입**:
    
    * 알고리즘의 **2단계**에서, 각 원소를 특정 버킷 `B[i]`에 삽입하는 작업의 시간 복잡도는 `Θ(1)`이다.
        
    * 각 원소를 버킷에 배치하는 것은 **단순한 계산**(`n * A[i]`)을 통해 수행되므로, 각 삽입 작업은 `O(1)`의 시간이 소요된다.
        
    * 예를 들어, `A[i]`가 `0.38`이라면, `B[5]` 버킷에 삽입하는 것은 한 번의 계산으로 이루어지기 때문에 `Θ(1)` 시간 복잡도를 가진다.
        
* **전체 원소의 버킷 삽입**:
    
    * 총 `n`개의 원소를 각기 다른 버킷에 삽입하는 작업의 전체 시간 복잡도는 `Θ(n)`이다.
        
    * `n`개의 원소 각각에 대해 `Θ(1)`의 작업을 수행하므로, 전체 복잡도는 `n * Θ(1) = Θ(n)`이 된다.
        

### 버킷 정렬의 시간 복잡도 2

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727931585997/7d27ee70-ce3a-458e-a490-d10f81c4a0e3.png align="center")

이 설명은 **버킷 정렬이** `n`개의 균등 분포된 원소들을 가진 배열에 대해, 각 버킷에서의 정렬 시간 복잡도가 `Θ(1)`임을 보이고, 이를 기반으로 전체 정렬의 시간 복잡도가 `Θ(n)`이 된다는 것을 수학적으로 증명하고 있다. 요약은 아래를 살펴보자

<mark>요약:</mark>

* 각 버킷에 원소가 들어갈 확률: `p = 1/n`
    

* 각 버킷의 삽입 정렬 시간 복잡도: `Θ(1)`
    
* 전체 버킷의 시간 복잡도: `Θ(n)`
    

---

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727928303698/7443423b-6ebe-4e83-9bf0-b1694510feae.png align="center")

기수, 계수, 버킷 정렬은 O(n)의 복잡도를 가진 알고리즘이다.

---

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727928576013/a465987b-0452-4234-90e1-999aac1f7efd.png align="center")