중급 알고 리즘 세션 1일차

특강 – 250106,8,10(월수금)

중급 알고 리즘 세션

 

1일차 – https://teamsparta.notion.site/Node-7-1-c477f4156cdc4b1ea82960503828c2fe

 

 

 

 

퀵정렬

기본 개념

• 분할 후 정복 (Divide and Conquer):
  배열을 피벗(pivot)을 기준으로 두 그룹(작은 값은 왼쪽, 큰 값은 오른쪽)으로 나눈 후, 각 그룹에 대해 같은 방식(재귀)을 반복하여 전체를 정렬합니다.
• 피벗과 윈도우 이동:
  • 피벗: 보통 검은색 등으로 표시된 기준 숫자
  • 왼쪽 윈도우: 배열의 왼쪽에서 시작하여 피벗보다 큰 값을 탐색
  • 오른쪽 윈도우: 배열의 오른쪽에서 시작하여 피벗보다 작은 값을 탐색
  • 두 윈도우가 값을 찾으면 잠시 정지한 후 스왑(swap)하여 올바른 위치에 배치
  • 피벗 기준으로 그룹을 만들고 나면 이 두 개의 부분 배열에 대해서 계속 같은 방식으로 정렬을 반복합니다.
  • 재귀방식을 사용 

 

재귀 (Recursive)를 활용한 정렬

• 재귀 개념:
  함수가 자기 자신을 호출해 문제를 더 작은 단위로 나누어 해결하는 방식
  • 종료 조건: 반드시 필요 (예, 배열이 더 이상 분할할 수 없을 때)
• 예시 – 팩토리얼 계산:

• function factorial(n) {
    if (n === 1) { // 종료 조건: 1!은 1
      return 1;
    }
    return n * factorial(n - 1); // 재귀 호출: n * (n-1)!
  }
  
  console.log(factorial(5)); // 120

• 퀵 정렬과 재귀:
  한 개의 원본 배열이 두 개로 분할되고, 각 부분 배열이 또 재귀적으로 정렬되기 때문에 재귀 방식을 사용하는 것이 이상적입니다.

퀵 정렬 코드 구현

퀵 정렬 코드 

// quickSort.js

/**
 * 퀵 정렬 함수 (Quick Sort)
@param {number[]} array
정렬을 수행할 숫자 배열을 의미합니다.

@param {number} left
정렬을 시작할 인덱스입니다. 기본값은 0으로, 배열의 첫 번째 요소부터 정렬을 시작함을 나타냅니다.

@param {number} right
정렬을 종료할 인덱스로, 기본값은 array.length - 1입니다. 즉, 배열의 마지막 요소까지 정렬하겠다는 뜻입니다.

@returns {number[]}
정렬이 완료된 배열을 반환합니다.
*/

function quickSort(array, left = 0, right = array.length - 1) {
  // 1. 배열이 더 이상 분할할 수 없을 정도로 작아지면 종료! 
  if (left >= right) return;

  // 2. 배열의 중간 인덱스를 계산하여 피벗으로 설정
  const mid = Math.floor((left + right) / 2);
  const pivot = array[mid]; // 중간 값을 피벗으로 설정

  // 3. 왼쪽(i)과 오른쪽(j)에서 시작하는 인덱스 설정 (윈도우 세팅)
  let i = left;
  let j = right;

  // 4. i가 j와 교차하기 전까지 계속 실행
  while (i <= j) {
    // 5. i가 가리키는 값이 피벗보다 작은 경우 계속해서 오른쪽으로 이동
    while (array[i] < pivot) i++;

    // 6. j가 가리키는 값이 피벗보다 큰 경우 계속해서 왼쪽으로 이동
    while (array[j] > pivot) j--;

    // 7. i와 j가 교차하지 않았다면 두 값을 교환하고 i, j를 각각 이동
    if (i <= j) {
      [array[i], array[j]] = [array[j], array[i]]; // i와 j의 값을 스왑
      i++; // i를 오른쪽으로 한 칸 이동 (왼쪽 윈도우 이동)
      j--; // j를 왼쪽으로 한 칸 이동 (오른쪽 윈도우 이동)
    }
  }

  // 8. 왼쪽 부분 배열이 남아있다면 그 부분에 대해 다시 정렬 (재귀 호출)
  if (left < j) {
      quickSort(array, left, j);
  }

  // 9. 오른쪽 부분 배열이 남아있다면 그 부분에 대해 다시 정렬 (재귀 호출)
  if (i < right) {
      quickSort(array, i, right);
  }
  
  // 10. 배열 반환!
	return array;
}

// Node.js에서 실행할 예제
const unsortedArray = [9, 4, 6, 2, 8, 1, 3];
const sortedArray = quickSort(unsortedArray);

console.log("정렬 전:", unsortedArray);
console.log("정렬 후:", sortedArray);

무차별 대입 (Brute Force)

기본 개념

• 무차별 대입:
  가능한 모든 조합을 생성한 후 조건에 맞는 해답을 찾는 가장 단순한 알고리즘 접근 방식
  • 장점: 구현이 간단하고, 모든 경우를 확인하므로 해답을 보장
  • 단점: 경우의 수가 많아지면 시간 복잡도가 급격히 증가(비효율적)

 

function generateCombinations(arr) {
  let results = [[]]; // 시작은 빈 조합 하나로 시작

  for (let num of arr) {
    let newResults = []; // 새롭게 생성되는 조합을 임시로 저장
    for (let combination of results) {
      newResults.push([...combination, num]); // 기존 조합에 현재 숫자를 추가
    }
    results = results.concat(newResults); // 기존 결과와 새로운 조합을 합침
  }

  return results;
}

console.log(generateCombinations([1, 2, 3]));
// 출력: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

 

주요 차이점

특징	첫 번째 코드	두 번째 코드
구현 방식	새로운 배열을 만들어 반환 (비파괴적)	같은 배열에서 정렬을 수행 (파괴적, in-place)
피벗 선택	배열의 첫 번째 요소 또는 상황에 따라 다름	배열의 중간 요소를 피벗으로 사용
메모리 사용	추가 배열(left, right) 생성으로 메모리 사용 증가	동일 배열에서 작업하므로 추가 메모리 사용 없음
성능	메모리 사용량 증가로 큰 배열에서 비효율적일 수 있음	메모리 효율적, 대규모 배열에서 더 적합
가독성	간단하고 이해하기 쉬움	복잡도는 증가하지만 메모리 효율적
정렬 완료 방식	정렬된 새로운 배열을 반환	기존 배열을 정렬

 

선택 기준

• 학습 및 이해:
  간단하고 직관적인 첫 번째 코드가 적합합니다.
• 실제 대규모 데이터 처리:
  메모리 효율적이고 성능이 좋은 두 번째 (in-place) 코드가 유리합니다.

개선 가능성

• 피벗 선택 최적화:
  무작위 선택이나 중간 값을 활용하여 최악의 경우(O(N²))를 줄일 수 있음
• 재귀 호출 개선:
  스택 기반의 재귀 또는 반복문으로 전환하여 스택 오버플로우 문제를 완화 가능

---

시간 복잡도

• 평균 시간 복잡도: O(N log N)
  • 데이터가 매 단계마다 반씩 분할되고, 각 단계에서 N개의 요소를 비교하여 처리
• 최악의 시간 복잡도: O(N²)
  • 피벗이 항상 최솟값 또는 최댓값인 경우, 한쪽으로 치우치며 모든 요소를 비교

 

2일차 – https://teamsparta.notion.site/Node-7-2-891a8d94291a4e1c8d147cafe9805a6d

3일차 – https://teamsparta.notion.site/Node-7-3-df100170302546f0943baa83c0ed6784