오늘 하루는 너무 바쁘게 지나갔다. 월요일이라 약간 쳐져있을만도 한데 할 일이 많아서 순식간에 시간이 지나가버렸다.
오늘은 아침 시간에 공부했던 퀵 정렬과 무차별 대입에 대해 다시 한번 정리해보고자 한다.
오늘 학습한 내용
퀵 정렬
퀵 정렬이란 무엇인가? 이름 그대로 정말 빠르게 정렬할 수 있는 알고리즘이다.
퀵 정렬의 핵심은 분할 후 정복 방식으로 데이터를 나누고 정렬하여 전체를 정리하는 방식이다.
순서는 다음과 같다.
1. 데이터 내에 피벗이라는 기준을 두고 왼쪽과 오른쪽으로 나눌 수 있다.
2. 이때 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 정렬한다.
3. 왼쪽 윈도우는 배열의 왼쪽부터 시작해서 오른쪽으로 가며 피벗보다 큰 값을 찾는다.
4. 오른쪽 윈도우는 배열의 오른쪽부터 시작해서 왼쪽으로 가며 피벗보다 작은 값을 찾는다.
5. 각 윈도우가 해당하는 값을 찾으면 스탑한 뒤 서로 스왑을 한다.
6. 이렇게 만들어진 피벗 기준의 양쪽 그룹이 같은 방식으로 정렬을 반복한다.
이때, 6번에 사용되는 방법을 재귀라고 한다.
#재귀란?
함수가 자기 자신을 다시 호출하는 것, 어떤 일을 하려고 할때 그 일을 더 작은 부분으로 나누어 작은 일을 해결함.\
그렇다면 자기 자신을 무한정 호출하는 것인가? NO
>> 재귀는 거울을 2개 마주보게 했을때 무한정 반사되지만 그 속에서 너무 작아져 볼 수 없게 되는 순간에 멈추게 된다.
퀵 정렬 코드 예시
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;
}
console.log(quickSort([9, 4, 6, 2, 8, 1, 3]));
위와 같은 퀵 정렬은 데이터를 반씩 나누며 정렬하기 때문에, 로그 시간만큼의 단계에서 각 단계마다 데이터를 처리하게 되어 O(N log N)의 복잡도를 가진다.
이때 피벗이 항상 최솟값이나 최댓값으로 선택되어 한쪽으로 치우치는 경우 모든 데이터를 비교하게 되어 O(N^2)의 시간이 걸려서 피벗을 잘 고르는 것이 중요하다.
무차별 대입
무차별 대입이란 무엇인가? 모든 가능한 조합을 생성하고, 조건에 맞는지 하나씩 확인하는 과정이다.
장점을 꼽자면 간단하다는 것이고 직접 가능한 모든 결과를 탐색하기에 정확한 해답을 찾아낼 수 있다.
하지만 모든 경우의 수를 하나씩 시도하기때문에 경우의 수가 많아질수록 시간이 급격하게 늘어나 비효율적일 수 있다.
무차별 대입 코드 예시
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]));
오늘 학습한 내용에 대한 추가 정보
위에서 공부한 퀵 정렬과 무차별 대입을 게임 서버 개발자는 어느 부분에서 사용하게 될까?
퀵 정렬은 O(nlogn)의 시간 복잡도를 가지기 때문에, 데이터 정렬이 필요한 상황에서 효율적으로 사용할 수 있을 것이다.
리더보드 정렬: 게임 서버에서 다수의 플레이어 데이터를 정렬하여 리더보드를 생성해야 할 때, 퀵 정렬을 활용할 수 있다.
예를 들어, 매 게임 라운드마다 플레이어들의 점수를 서버에서 실시간으로 정렬해야 하는 경우, 효율성이 중요하다.
아이템 정렬: 게임 내 상점에서 아이템을 가격, 레벨 요구 사항, 혹은 희귀도에 따라 정렬하여 클라이언트에 전송하는 경우.
매칭 시스템: 매칭 대기열에 있는 플레이어를 특정 기준(예: 실력, 레벨, 핑)으로 정렬하여 빠르고 공정한 매칭을 구현하는 경우.
무차별 대입은 퀵 정렬과 달리 모든 경우의 수를 탐색하기 때문에 간단한 문제 혹은 모든 경우의 수를 탐색해야만 할 때 사용할 수 있을 것이다.
패턴 매칭: 서버에서 특정 데이터(예: 해커의 행동 로그, 금지 단어 등)가 로그 데이터에 포함되어 있는지 탐색할 때, 무차별 대입 알고리즘을 사용할 수 있습니다.
퍼즐 게임 상태 탐색: 게임 내 특정 퍼즐이나 이벤트를 처리하는 과정에서 최적의 상태를 탐색할 필요가 있을 때.
보안 검사: 암호화 해독 시 공격 시뮬레이션(예: 무작위 비밀번호 대입)을 서버에서 처리해야 하는 경우. 다만, 이런 경우에는 일반적으로 더 효율적인 알고리즘이 사용됩니다.