본문 바로가기
카테고리 없음

분할 정복 자바스크립트

캉구리 2024. 6. 19. 06:57

분할 정복(Divide and Conquer) 알고리즘은 문제를 더 작은 하위 문제로 나누어 해결하는 전략입니다. 각 하위 문제를 해결한 후, 이들을 결합하여 전체 문제의 해결책을 얻습니다. Go 언어를 사용하여 분할 정복 알고리즘을 구현하는 방법을 살펴보겠습니다.

Go에서 분할 정복 알고리즘 구현하기

분할 정복 알고리즘의 대표적인 예로는 **병합 정렬(Merge Sort)**과 **퀵 정렬(Quick Sort)**이 있습니다. 여기에서는 병합 정렬을 예제로 설명하겠습니다. 병합 정렬은 배열을 반으로 나누어 각각 정렬한 후, 두 정렬된 배열을 병합하여 전체 배열을 정렬하는 방법입니다.

병합 정렬(Merge Sort) 구현

병합 정렬의 단계는 다음과 같습니다:

  1. 분할: 배열을 두 개의 하위 배열로 분할합니다.
  2. 정복: 각 하위 배열을 재귀적으로 정렬합니다.
  3. 결합: 두 개의 정렬된 하위 배열을 병합하여 최종 배열을 만듭니다.

Go 코드 예제

go
코드 복사
package main import ( "fmt" ) // 병합 함수 func merge(left, right []int) []int { result := []int{} i, j := 0, 0 // 두 배열을 병합 for i < len(left) && j < len(right) { if left[i] < right[j] { result = append(result, left[i]) i++ } else { result = append(result, right[j]) j++ } } // 남은 요소 추가 for i < len(left) { result = append(result, left[i]) i++ } for j < len(right) { result = append(result, right[j]) j++ } return result } // 병합 정렬 함수 func mergeSort(arr []int) []int { if len(arr) <= 1 { return arr } mid := len(arr) / 2 left := mergeSort(arr[:mid]) right := mergeSort(arr[mid:]) return merge(left, right) } func main() { arr := []int{38, 27, 43, 3, 9, 82, 10} sortedArr := mergeSort(arr) fmt.Println("Sorted array:", sortedArr) }

코드 설명

  1. 병합 함수 merge:
    • 두 개의 정렬된 배열을 병합하여 하나의 정렬된 배열을 반환합니다.
    • 두 배열의 요소를 비교하여 작은 값을 결과 배열에 추가합니다.
    • 하나의 배열이 먼저 끝나면, 다른 배열의 남은 요소를 결과 배열에 추가합니다.
  2. 병합 정렬 함수 mergeSort:
    • 배열이 하나의 요소 이하일 경우 이미 정렬된 것으로 간주하고 반환합니다.
    • 배열을 두 개의 하위 배열로 나눈 후, 재귀적으로 mergeSort를 호출하여 각 하위 배열을 정렬합니다.
    • 두 정렬된 하위 배열을 merge 함수로 병합하여 최종 정렬된 배열을 반환합니다.
  3. main 함수:
    • 정렬할 배열을 정의하고, mergeSort를 호출하여 정렬된 배열을 출력합니다.

병합 정렬의 장점과 단점

  • 장점:
    • 안정적인 정렬(원래 배열의 동일한 값의 순서가 유지됨).
    • 최악의 경우 시간 복잡도가 O(nlog⁡n)O(n \log n)로 안정적입니다.
  • 단점:
    • 추가적인 메모리가 필요합니다(배열을 병합할 때 새로운 배열을 생성해야 함).

추가 예제: 퀵 정렬(Quick Sort)

퀵 정렬은 또 다른 분할 정복 알고리즘으로, 배열을 피벗을 기준으로 두 개의 부분으로 나누고, 재귀적으로 각 부분을 정렬합니다.

Go 코드 예제

go
코드 복사
package main import ( "fmt" ) // 파티션 함수 func partition(arr []int, low, high int) int { pivot := arr[high] i := low - 1 for j := low; j < high; j++ { if arr[j] < pivot { i++ arr[i], arr[j] = arr[j], arr[i] } } arr[i+1], arr[high] = arr[high], arr[i+1] return i + 1 } // 퀵 정렬 함수 func quickSort(arr []int, low, high int) { if low < high { pi := partition(arr, low, high) quickSort(arr, low, pi-1) quickSort(arr, pi+1, high) } } func main() { arr := []int{38, 27, 43, 3, 9, 82, 10} quickSort(arr, 0, len(arr)-1) fmt.Println("Sorted array:", arr) }

코드 설명

  1. 파티션 함수 partition:
    • 피벗을 기준으로 배열을 나누고, 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 이동시킵니다.
    • 피벗의 최종 위치를 반환합니다.
  2. 퀵 정렬 함수 quickSort:
    • 파티션을 호출하여 배열을 나누고, 각 부분에 대해 재귀적으로 quickSort를 호출합니다.
  3. main 함수:
    • 정렬할 배열을 정의하고, quickSort를 호출하여 정렬된 배열을 출력합니다.

요약

분할 정복 알고리즘은 문제를 작은 하위 문제로 나누어 해결하고, 이를 결합하여 전체 문제를 해결하는 접근 방식입니다. Go 언어에서 분할 정복 알고리즘을 구현할 때는 재귀적 호출과 배열/슬라이스 조작을 활용하여 효과적인 솔루션을 구현할 수 있습니다. 병합 정렬과 퀵 정렬은 이러한 접근 방식을 잘 보여주는 예입니다.

 
 
4o mini
__분할 정복 ____자바스크립트
 
ChatGPT

자바스크립트에서 분할 정복(Divide and Conquer) 알고리즘을 구현할 때는 문제를 더 작은 하위 문제로 나누고, 이들 하위 문제를 각각 해결한 후 결과를 결합하여 전체 문제를 해결합니다. 자바스크립트로 이 접근 방식을 구현하는 대표적인 예로는 **병합 정렬(Merge Sort)**과 **퀵 정렬(Quick Sort)**이 있습니다. 여기에서는 병합 정렬을 예제로 설명하겠습니다.

병합 정렬(Merge Sort) 구현

병합 정렬은 배열을 반으로 나누어 각각 정렬한 후, 두 정렬된 배열을 병합하여 전체 배열을 정렬하는 방법입니다.

병합 정렬 구현 예제

javascript
코드 복사
// 배열을 병합하는 함수 function merge(left, right) { let result = []; let i = 0, j = 0; // 두 배열을 병합 while (i < left.length && j < right.length) { if (left[i] < right[j]) { result.push(left[i]); i++; } else { result.push(right[j]); j++; } } // 남아있는 요소 추가 while (i < left.length) { result.push(left[i]); i++; } while (j < right.length) { result.push(right[j]); j++; } return result; } // 병합 정렬 함수 function mergeSort(arr) { if (arr.length <= 1) { return arr; } const mid = Math.floor(arr.length / 2); const left = mergeSort(arr.slice(0, mid)); const right = mergeSort(arr.slice(mid)); return merge(left, right); } // 사용 예시 const array = [38, 27, 43, 3, 9, 82, 10]; const sortedArray = mergeSort(array); console.log("Sorted array:", sortedArray);

코드 설명

  1. 병합 함수 merge:
    • 두 개의 정렬된 배열 left와 right를 병합하여 하나의 정렬된 배열을 반환합니다.
    • 두 배열의 요소를 비교하여 작은 값을 result 배열에 추가합니다.
    • 하나의 배열이 먼저 끝나면, 다른 배열의 남은 요소를 result 배열에 추가합니다.
  2. 병합 정렬 함수 mergeSort:
    • 배열의 길이가 1 이하인 경우 이미 정렬된 것으로 간주하고 반환합니다.
    • 배열을 중간에서 두 개의 하위 배열로 나누고, 각각 mergeSort를 호출하여 정렬합니다.
    • 두 정렬된 하위 배열을 merge 함수로 병합하여 최종 정렬된 배열을 반환합니다.
  3. 사용 예시:
    • 정렬할 배열을 정의하고 mergeSort를 호출하여 정렬된 배열을 출력합니다.

병합 정렬의 장점과 단점

  • 장점:
    • 안정적인 정렬(원래 배열의 동일한 값의 순서가 유지됨).
    • 최악의 경우 시간 복잡도가 O(nlog⁡n)O(n \log n)로 안정적입니다.
  • 단점:
    • 추가적인 메모리가 필요합니다(배열을 병합할 때 새로운 배열을 생성해야 함).

추가 예제: 퀵 정렬(Quick Sort)

퀵 정렬은 또 다른 분할 정복 알고리즘으로, 배열을 피벗을 기준으로 두 개의 부분으로 나누고, 재귀적으로 각 부분을 정렬합니다.

퀵 정렬 구현 예제

javascript
코드 복사
// 파티션 함수 function partition(arr, low, high) { const pivot = arr[high]; let i = low - 1; for (let j = low; j < high; j++) { if (arr[j] < pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; // 스왑 } } [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // 스왑 return i + 1; } // 퀵 정렬 함수 function quickSort(arr, low, high) { if (low < high) { const pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } // 사용 예시 const array = [38, 27, 43, 3, 9, 82, 10]; quickSort(array, 0, array.length - 1); console.log("Sorted array:", array);

코드 설명

  1. 파티션 함수 partition:
    • 배열을 피벗을 기준으로 두 개의 부분으로 나누고, 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 이동시킵니다.
    • 피벗의 최종 위치를 반환합니다.
  2. 퀵 정렬 함수 quickSort:
    • 파티션을 호출하여 배열을 나누고, 각 부분에 대해 재귀적으로 quickSort를 호출합니다.
  3. 사용 예시:
    • 정렬할 배열을 정의하고 quickSort를 호출하여 정렬된 배열을 출력합니다.

요약

자바스크립트에서 분할 정복 알고리즘을 적용하는 방법으로는 병합 정렬과 퀵 정렬이 있습니다. 이러한 알고리즘은 문제를 작은 하위 문제로 나누고, 각 하위 문제를 해결한 후 결과를 결합하여 전체 문제를 해결하는 전략을 사용합니다. 병합 정렬은 안정적이고 예측 가능한 성능을 제공하며, 퀵 정렬은 일반적으로 더 빠르지만 성능이 피벗 선택에 따라 달라질 수 있습니다.

티스토리툴바