[컴퓨터과학 개론] 6강 - 알고리즘(2)

✅ 1. 정렬 알고리즘: 퀵 정렬, 합병 정렬

• 퀵정렬, 합병 정렬 두 가지의 공통 특징은 분할 정복 방법이 적용되는 알고리즘이다.
• 분할 정복 방법은 그냥 단순히 데이터 집합을 쪼개서 분할 해서 정렬 할 때 쓰이는 개념으로 보면 될 듯

(1) 퀵 정렬

[ 피벗 - pivot, 분할원소 ]

• 두 개의 부분배열로 분할할 때 기준이 되는 특정한 데이터를 의미함.
• 보통 주어진 배열의 첫 번째 원소를 피벗으로 정하긴 함.

• 특정 데이터(피벗)를 기준으로 입력 배열을 두 개의 부분배열로 분할하고, 각 부분 배열에 대해서 독립적으로 퀵 정렬을 순환적으로 적용한다. 라는 개념을 가지고 있는 정렬임.
• 쉽게말해, 입력 배열에서 정렬 기준으로 삼고 싶은 요소를 피벗으로 보고 해당 피벗 데이터를 기준으로 입력 배열을 두 개의 부분 배열로 나눌 수 있다. 즉, 왼쪽 부분 배열(왼쪽 그룹), 오른쪽 부분 배열(오른쪽 그룹)로 나눈다는 의미이다. 또한, 왼쪽 그룹 정렬과 오른쪽 그룹의 정렬은 따로 독립적으로 처리가 되며, 부분 배열에 대해서도 똑같이 정렬 기준이 되는 피벗을 선택하여 해당 피벗을 기준으로 다시 분할이 되고 정렬이 되는 방식이다. 이러한 과정을 반복하는 것이 퀵 정렬이다.
• 즉, 이러한 피벗을 기준으로 찾는 과정이 "피벗이 제자리를 잡도록 하여 정렬하는 방식" 으로도 볼 수 있음.
• 평균적으로 가장 좋은 성능의 비교 기반 알고리즘이며, O(nlogn) 이다.

(2) 퀵 정렬 - 분할 과정 1

• 배열을 피벗 기준으로 부분 배열로 분할하는 과정을 분할 과정이라 볼 수 있다.

• (1) 배열의 제일 첫 번째 요소를 피벗으로 가정을 하며, 피벗의 index = 0, L index = 1 , R index = 7 로 정의를 한다.
• (2) 피벗 데이터인 54를 기준으로 L 은 인덱스를 올리면서 피벗보다 큰 값을 찾게 되고, R 은 반대로 인덱스를 내리면서 피벗보다 작은 값의 위치를 찾게 된다. 즉, 34 -> 41 -> 89 ( 피벗보다 큰 값 ) 에서 멈추게 되며 L 은 89에 위치하게 되고, R 은 피벗의 데이터인 54 보다 작은 값인 23 원래 위치하는 곳에 있게 된다.
• (3) 현재 L 의 위치 89 와 R 의 위치 23 의 위치를 서로 변경을 하게 되며, L 과 R 이 또 다시 이동하면서 피벗을 기준으로 큰 수와 작은 수를 찾게 되면 그 자리에 멈추고 또 다시 서로 교환을 반복하게 된다.
• (4) L 과 R 의 인덱스가 교차가 되는 순간 즉, L(index) > R(index) 가 되는 경우에는 R 의 값과 피벗 값을 서로 위치를 교환하게 되고 정렬이 종료가 되게 된다.
• (5) 결과적으로 피벗을 기준으로 왼쪽 부분배열은 피벗보다 작은 값 오른쪽은 피벗보다 큰 값이 되게된다.

(3) 퀵 정렬 - 분할 과정 2

• 위와 마찬가지로 L 과 R 이 이동하면서 피벗을 기준으로 큰 값과 작은 값을 찾으며 서로 위치를 교환하게 된다.
• 마찬가지로 L 이 R 보다 큰 상태 즉, L > R 상태이므로, R 의 값이 피벗과 위치를 바꾸게 되면서 분할이 되게 된다.

(4) 퀵 정렬 - 전체적인 수행 과정

• 앞선 분할 과정을 통해 피벗이 제자리를 찾아갈 수 있으며, 이러한 분할 과정을 통해 얻어낸 왼쪽과 오른쪽 부분배열에서 또 다시 분할 과정을 통해 피벗이 제자리를 찾아가게 되는데 이러한 과정을 반복하면 최종적으로 정렬 된 배열을 얻을 수 있다.

• (1) 기준이 되는 피벗 54 를 분할 과정을 통해 제자리를 찾아가게 되며, 오른쪽과 왼쪽 부분배열이 생기게 됨.
• (2) 피벗 16을 기준으로 L 은 34 에서 멈추게 된다 R 은 16 보다 작은 수가 없으므로, 원래 위치에서 고정이 되게 된다.
• (3) 피벗 34 기준으로 L 은 41 에 멈추고 R 은 23 에 멈추게 된다 서로 교환을 하게 되어 34, 23, 41, 52 형태가 될 것이다. 이후, L > R 형태가 되므로 23 과 34는 교환이 되며 23, 34, 41, 52 형태가 되게 된다.
• (4) 23은 분할 할 데이터가 없으므로 23이 제자리를 찾게 됨.
• (5) 41 또한 L 만 존재하기 때문에 41이 위치가 고정이 됨
• (6) 52 또한 L 만 존재하기 떄문에 52이 위치가 고정이 됨.
• (7) ~ (8) 67, 89 또한 마찬가지로 고정이 됨.

(5) 퀵 정렬 - 퀵 정렬의 특징

[ 분할정복 방법을 적용한 알고리즘 ]

• 분할: 정렬한 n 개의 데이터를 피벗을 중심으로 두 개의 부분배열로 분할
• 정복: 두 부분배열 각각에 대해 퀵 정렬을 순환적으로 적용하여 두 부분배열을 정렬
• 결합: 필요 없음

[ 성능 ]

• 분할 과정의 수행 시간 - O(n)
• 평균 수행 시간 - O(nlogn) : 피벗 선택의 임의성만 보장되면 평균 수행 시간을 보일 가능성이 높음
• 최선 수행 시간 - O(nlogn)
• 최악 수행 시간 - O(n^2): 해당 최악의 경우는 입력 데이터가 이미 정렬 된 경우로 피벗이 첫 번째 원소를 지정 한 경우 항상 최대값이나 최솟값이 되는 경우 이므로, 최악의 수행 시간이 될 수 있음.

(6) 합병 정렬

• 동일한 크기의 두 개의 부분배열로 분할하고, 각 부분배열을 순환적으로 정렬한 후, 정렬된 두 부분배열을 합병해서 하나의 정렬된 배열을 만드는 정렬 방식이다.
• 쉽게말해, 동일한 크기로 부분배열을 두개로 분할한 뒤 각 부분배열을 정렬하고 이후 두 부분 배열을 합병하면서 정렬
• 즉, 동일한 크기로 자르므로 가운데를 기준으로 자르는 느낌이 될 수 있음.

(6) 합병 정렬 - 전체적인 수행 과정

• (1) 반씩 쪼개면서 더 이상 쪼개지지 않을 때 까지 반복 분할을 하게 된다.
• (2) 이후 합병 과정에서 두 수를 비교하는 반복 합병을 통해 정렬을 하게 된다.
• 즉, 핵심은 분할이 되어 쪼개진 두 부분배열을 하나의 정렬된 배열로 즉, 합병하는 과정이 될 수 있음.

(7) 합병 정렬 - 합병 과정

• 합병 과정은 정렬된 두 부분배열을 하나의 정렬된 배열로 만드는 과정이다.

# 두 부분배열
34 41 54 89 | 16 23 52 67

# 합병 과정
34 , 16 비교 => 16
34 , 23 비교 => 23
34 , 52 비교 => 34
52 , 41 비교 => 41
52 , 54 비교 => 52
54 , 67 비교 => 54
67 , 89 비교 => 67
남는 값 => 89

# 결과
C[n] = 16, 23, 34, 41, 52, 54, 67, 89

• 두 부분배열은 앞에서 이미 정렬이 된 상태 이므로, 각 부분배열의 앞 인덱스부터 서로 비교를 하면서 
• 16과 34를 비교 후 작은 값은 C[n] 배열에 담고 앞 부터 남는 수 반복 비교 후 배열에 담는 이러한 과정을 통해 정렬이 가능함.

(8) 합병 정렬 - 특징

• 합병 정렬도 퀵 정렬과 동일하게 분할정복 방법을 적용한 알고리즘이다.
• 분할: 정렬한 n 개의 데이터를 n/2 개의 데이터를 갖는 두 부분배열로 분할
• 정복: 두 부분배열에 대해 합병 정렬을 각각 순환적으로 적용하여 정렬
• 합병: 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만듦

[ 성능 ]

• 최선, 최악, 평균 수행 시간 모두 O(nlogn) 의 특징을 띄고 있음.
• 기존의 선택 정렬, 버블 정렬 등은 O(n^2) 이었지만, 합병이나 퀵 정렬은 모두 O(nlogn) 으로 성능이 더 뛰어남

---

✅ 2. 순차탐색, 이진탐색

(1) 탐색 이란?

• 탐색이란 주어진 데이터 집합에서 원하는 값을 가진 데이터를 찾는 작업을 의미한다.
• 탐색에는 대표적으로 순차 탐색, 이진 탐색, 이진 탐색 트리가 존재한다.
• 각각 성능은 순차 탐색 O(n) / 이진 탐색 O(logn) / 이진 탐색 트리 평균 O(logn) 최악 O(n) 특징을 가지고 있음.

(2) 순차 탐색

• 리스트 형태로 주어진 데이터를 처음부터 하나씩 차례대로 비교하여 원하는 데이터를 찾는 방법이다.

• 예시 이미지와 같이 배열에서 30의 값을 찾는 과정에서 앞에서부터 하나씩 탐색하면서 찾아가는 방법이 순차 탐색이다.

(3) 순차 탐색 - 특징

[ 탐색 성능 ]

• 실패하는 경우의 비교 횟수는 n 번, 성공하는 경우의 비교 횟수는 1 ~ n 번이 될 수 있다.
• 즉, 입력 크기 n 의 비례하는 만큼의 성능 크기를 가지게 되며 O(n) 이 될 수 있음.
• 결론은 순차 탐색은 데이터가 많은 경우에 사용을 하게 되면 성능이 낮아질 수 있음.

[ 순차 탐색 특징 ]

• 순차 탐색은 모든 리스트(배열, 연결 리스트) 에 적용이 가능하다.
• 리스트와 같이 데이터가 키값과 관련해서 아무런 순서 없이 단순하게 연속적으로 저장 되는 경우
• 즉, 데이터가 정렬되지 않은 경우에는 순차 탐색이 적합 할 수 있다.
• 반대로 데이터가 정렬이 된 상태로 들어온다면 이진 탐색이 효율적임.

(4) 이진 탐색

• 정렬된 입력 배열에 대해서 주어진 데이터를 절반씩 줄여가면서 원하는 데이터를 찾는 방법이다.
• 즉, 이진 탐색의 조건은 반드시 정렬된 배열이어야만 탐색이 가능하다는 조건이 있다는 의미임.
• 분할정복 방법을 적용한 알고리즘이다.

[ 탐색 방법 ]

• 배열의 가운데 값과 탐색키를 비교하여 원하는 값을 찾아가는 방법이다.
• 즉, 입력 배열의 가운데 값인 A[Mid] 와 탐색키를 비교를 하게 된다. ( 탐색키 = 내가 찾고자하는 데이터 )

• left index = 배열 맨 앞 , right index 배열 맨 끝 을 의미.
• left index 와 right index 를 더한 값은 배열의 크기가 될 수 있고, 해당 배열의 크기에 2를 나누어 가운데를 구함.
• 가운데 데이터를 구하게 되면, 해당 데이터와 탐색키(내가 찾고자하는 데이터) 를 비교하여, 탐색키가 A[Mid] 보다 작을 경우 left , 탐색키가 A[Mid] 보다 클 경우 right 에 있다는 것을 알게 된다.
• 즉, 탐색을 반복할 때마다 대상 원소(데이터)의 개수가 절반씩 감소가 되는 특징이 있음.
• 또한, key 값이 A[Mid] 가운데 값과 같으면 탐색이 바로 성공 할 수 있는 겨

(4) 이진 탐색 - 탐색 과정

• 탐색키 값이 35 라 가정하고 이진 탐색 진행
• 먼저 left index 0 과 right indext 8 를 더해서 2로 나누게 되면 가운데 index 4 를 얻을 수 있게 된다.
• 해당 index 4 는 데이터가 30이 들어가있고, 탐색키 35 와 비교를 하게 되면 35가 더 크기 때문에 right 를 보게된다.
• right 에서 또 이진 탐색을 통해 절반을 줄이고 탐색키와 가운데 index(5+8/2=6) 를 비교하여 찾아가는 과정이 될 수 있다.
• 참고로 원하는 데이터를 찾았을 경우 인덱스를 반환함.

(4) 이진 탐색 - 특징

[ 성능 ]

• 한 번 탐색할 때마다 탐색 대상이 되는 데이터의 개수가 절반씩 감소하기 때문에 O(logn) 성능을 가짐.

[ 특징 ]

• 데이터가 이미 정렬된 경우에만 적용이 가능하다
• 삽입/삭제 연산 시 정렬 상태의 유지를 위해 데이터 이동이 발생 할 수 있다는 단점? 이 있음.
• 즉, 삽입/삭제와 같은 동적 연산이 많은 응용에는 부적합 할 수 있음.
• 매번 삽입 삭제와 같이 배열이 변경이 되면 정렬을 매번 해줘야 하는 단점이 있음.
• 이러한 경우 배열이 아닌 트리를 이용한 이진 탐색 트리를 활용해서 해결 할 수 있음.

---

✅ 3. 이진 탐색 트리

• 각 노드의 왼쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 작다.
• 각 노드의 오른쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 크다.
• 이 두가지 조건을 만족하는 트리를 이진 트리로 볼 수 있다.

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

• 루트 노드에서부터 키값의 비교를 통해 왼쪽 또는 오른쪽 서브트리를 따라 이동하면서 데이터를 찾게 됨.
• 즉, 44 와 같은 데이터를 찾겠다고 가정하면 각 노드보다 크면 오른쪽 작으면 왼쪽으로 내려가면서 찾게 되는 원리임.

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

• 기존의 배열 이진 탐색 방식은 삽입 삭제와 같은 연산이 필요한 경우에는 삽입과 삭제에 대해 매번 정렬을 해줘야 하기 때문에 적합하지 못했지만, 이진 탐색 트리 방식은 이걸 해결 할 수 있음.
• 이진 탐색 트리 삽입 연산은 삽입할 데이터를 탐색한 후, 탐색이 실패한 위치에 새로운 노드를 자식 노드로 추가하는 방식임.

• 즉, 25 데이터를 찾는 과정에서 35 -> 30 -> 15 -> 22 인 기존 노드들을 타게 되는데 이때 더 이상 노드가 없는데 25를 찾는 경우에는 탐색이 실패했기 때문에 밑에 25 노드를 새로 만들어주게 된다.
• 즉, 삽입 시 25 숫자가 있는지 검증을 한 뒤 없다고 판단한 뒤 삽입을 해주는 방식이라고 볼 수 있음.
• 결론은 탐색이 성공한 경우에는 데이터가 이미 존재한다고 판단이 되므로 삽입 없이 종료가 된다고 볼 수 있음.

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

• 후속자 노드 successor, 계승자 노드: 어떤 노드의 키값 바로 다음 키값을 갖는 노드를 의미한다.

후속자 노드

• 또한, 트리에서 이진 탐색은 삭제되는 노드의 자식 노드의 개수에 따라 구분해서 처리
• 즉, 자식 노드의 개수가 다른 경우에 따라 삭제되는 방식이 여러개가 쓰임.

[ 자식 노드가 없는 경우(리프 노드의 경우) ]

• 남는 노드가 없으므로 위치 조절이 불필요해, 단순 삭제를 하면 해결이 된다.
• 위와 같이 22 를 삭제하는 경우 단순히 22 를 가지는 노드를 제거하면 된다.

[ 자식 노드가 1개인 경우 ]

• 자식 노드가 1개인 경우에는 삭제되는 노드의 위치로 올리면서 서브트리 전체도 따라 올리게 됨,
• 위와 같이 30 노드를 삭제한다고 가정하면, 30 노드를 제거 한 뒤 15 와 그 서브트리를 기존 30 의 자리로 올리게 됨

[ 자식 노드가 2개인 경우 ]

• 자식 노드가 2개인 경우에는 삭제되는 노드의 후속자 노드를 삭제되는 노드의 위치로 올리게 된다.
• 그리고 후속자 노드를 삭제되는 노드로 취급하여 자식 노드의 개수에 따라 다시 처리하게 됨.

(4) 이진 탐색 트리 - 성능

• root 노드로 부터 탐색 즉, 내려오기 때문에 키값 비교 횟수에 비례하게 됨.
• 즉, 트리의 높이 h -> O(h) 성능을 가지게 됨. ( 최대 높이 O(logn) , 최소 높이 O(n) )
• 결국 트리의 높이에 따라 이진 탐색의 대한 성능이 달라질 수 있음.
• 그리고 이진 탐색 트리에서 삽입과 삭제를 빈번히 하게 된다면, 경사 이진 트리가 될 가능성이 높아지기 때문에 평균 수행 시간이 아닌 최악 수행 시간이 될 수 있게 된다. 이러한 것을 해결 즉, 평균 수행 시간을 보장하기 위해서 균형 탐색 트리도 존재함.