기초 알고리즘 복습 및 심화

순열 생성 문제

입력된 숫자 배열에 대해 모든 가능한 순열을 생성하는 문제는 STL 라이브러리를 활용하면 효율적으로 해결할 수 있다.

class PermutationGenerator {
public:
    vector<vector<int>> generateAllPermutations(vector<int>& inputArray) {
        sort(inputArray.begin(), inputArray.end());
        vector<vector<int>> resultCollection;
        
        do {
            resultCollection.push_back(inputArray);
        } while(next_permutation(inputArray.begin(), inputArray.end()));
        
        return resultCollection;
    }
};

이 방법의 핵심은 next_permutation 함수를 반복적으로 호출하여 사전순으로 다음 순열을 생성하는 것이다. 이 함수는 현재 순열이 마지막 순열(내림차순)이 아닐 경우 true를 반환하고 다음 순열로 변경하며, 마지막 순열일 경우 false를 반환한다.

배열 내 중복 요소 탐지

배열에서 중복된 값을 찾는 문제는 인덱스 기반의 자릿치환 방식으로 해결할 수 있다.

class DuplicateFinder {
public:
    int findDuplicateValue(vector<int>& numberArray) {
        int arraySize = numberArray.size();
        
        // 유효성 검사
        for (auto value : numberArray) {
            if (value < 0 || value >= arraySize) {
                return -1;
            }
        }
        
        for (int index = 0; index < arraySize; index++) {
            while (numberArray[numberArray[index]] != numberArray[index]) {
                swap(numberArray[index], numberArray[numberArray[index]]);
            }
            
            if (numberArray[index] != index) {
                return numberArray[index];
            }
        }
        
        return -1;
    }
};

이 알고리즘은 각 숫자가 자신의 값과 같은 인덱스 위치에 배치되도록 교환을 수행하며, 이미 해당 위치에 다른 숫자가 존재할 경우 중복을 감지한다.

이진 표현에서 1의 개수 계산

정수의 이진 표현에서 1의 비트 수를 세는 전형적인 비트 연산 문제이다.

방법 1 - 단순 비트 시프트:

class BitCounter {
public:
    int countOneBits(int targetNumber) {
        int count = 0;
        for(int bitPosition = 0; bitPosition < 32; bitPosition++) {
            if((targetNumber >> bitPosition) & 1) {
                count++;
            }
        }
        return count;
    }
};

방법 2 - lowbit 연산 활용:

class EfficientBitCounter {
public:
    int countSetBits(int value) {
        int counter = 0;
        while(value) {
            value -= value & (-value);  // 가장 오른쪽 1 비트 제거
            counter++;
        }
        return counter;
    }
};

정렬 알고리즘 구현

퀵 정렬 구현

분할 정복 전략을 사용하는 고속 정렬 알고리즘으로, 피벗 기준으로 배열을 분할한 후 재귀적으로 정렬한다.

#include<iostream>
using namespace std;

const int MAX_SIZE = 1e6 + 10;
int arraySize;
int dataArray[MAX_SIZE];

void quickSort(int arr[], int left, int right) {
    if (left >= right) return;
    
    int pivotLeft = left - 1, pivotRight = right + 1;
    int pivotValue = arr[(left + right) >> 1];  // 중간값 피벗
    
    while (pivotLeft < pivotRight) {
        do pivotLeft++; while (arr[pivotLeft] < pivotValue);
        do pivotRight--; while (arr[pivotRight] > pivotValue);
        
        if (pivotLeft < pivotRight) {
            swap(arr[pivotLeft], arr[pivotRight]);
        }
    }
    
    quickSort(arr, left, pivotRight);
    quickSort(arr, pivotRight + 1, right);
}

병합 정렬 구현

재귀적 분할 후 정렬된 하위 배열을 병합하는 안정적인 정렬 알고리즘이다.

int tempBuffer[MAX_SIZE];

void mergeSort(int arr[], int start, int end) {
    if (start >= end) return;
    
    int midPoint = (start + end) >> 1;
    mergeSort(arr, start, midPoint);
    mergeSort(arr, midPoint + 1, end);
    
    // 병합 과정
    int leftPtr = start, rightPtr = midPoint + 1, tempPtr = 0;
    
    while (leftPtr <= midPoint && rightPtr <= end) {
        if (arr[leftPtr] <= arr[rightPtr]) {
            tempBuffer[tempPtr++] = arr[leftPtr++];
        } else {
            tempBuffer[tempPtr++] = arr[rightPtr++];
        }
    }
    
    while (leftPtr <= midPoint) tempBuffer[tempPtr++] = arr[leftPtr++];
    while (rightPtr <= end) tempBuffer[tempPtr++] = arr[rightPtr++];
    
    for (int i = start, j = 0; i <= end; i++, j++) {
        arr[i] = tempBuffer[j];
    }
}

병합 정렬의 핵심은 두 개의 정렬된 서브배열을 하나의 정렬된 배열로 결합하는 병합 단계이며, 이 과정에서 두 포인터를 사용하여 각 배열의 최솟값을 비교하며 결과 배열을 구성한다.