"누구나 자료구조와 알고리즘"을 (일부)읽고..

1~5장에 대한 부분을 읽고 정리

2025년 01월 01일 · 0 분 소요

들어가며

프로젝트 진행 시 개발하는 과정에서 데이터를 효율적으로 관리하거나, 복잡한 구조를 효과적으로 풀어나가고 해결해야 할 때 기본기를 다질 필요성을 느낀 적이 많지만, 작업하는데 급급하여 놓치고 지내다가 동료분에게 "누구나 자료 구조와 알고리즘"이라는 책을 추천받고 틈틈이 보게 되었습니다. 아직 다 읽지는 못하였지만 제가 본 부분에 대해 추가적으로 알아본 것들과 함께 공유하고자 작성하게 되었습니다.

자료 구조의 중요성

자료 구조와 알고리즘은 데이터를 효율적으로 다루고 문제를 논리적으로 해결하기 위한 핵심 요소입니다. 자료 구조는 데이터를 체계적으로 정리하고 구성하는 방법을 이해하는 데 중점을 두며, 알고리즘은 이를 바탕으로 데이터를 활용하고 처리하는 과정을 설계하는 데 초점이 맞춰져 있습니다.

자료 구조의 기본적인 예로 배열을 들 수 있습니다. 배열은 데이터를 순서대로 정리해 저장할 수 있는 구조로, 크기가 고정된 연속적인 메모리 공간을 활용합니다. 배열의 크기란 배열에 저장할 수 있는 데이터의 총개수를 의미하며, 이 크기는 배열이 생성될 때 결정됩니다. 또한, 배열의 데이터는 각 요소가 메모리 상에서 차지하는 위치를 기준으로 고유한 번호(인덱스)로 접근할 수 있습니다. 예를 들어, API에서 반환된 JSON 데이터를 배열로 저장한 뒤, 이러한 인덱스를 이용해 특정 데이터를 빠르게 찾거나 처리할 수 있습니다. 책에는 다른 예제로 설명되어 있지만, 저는 스크립트를 사용하기에 그에 맞게 수정하여 예시를 작성하였습니다.

const users = ["doworld", "nagaeso", "zurang23"];
console.log(users[1]); // "nagaeso"

자료 구조 연산

배열과 같은 자료 구조에서 수행 가능한 주요 연산으로는 읽기, 검색, 삽입, 삭제가 있습니다.

그전에 알아야 할 내용은 속도 측정 부분인데요. 연산의 속도를 측정할 때 얼마나 빠른가와 같이 시간의 관점이 아닌 얼마나 많은 계산 단계가 필요한지를 따져봐여 하며, 연산의 속도 측정은 연산의 시간 복잡도 측정으로도 알려져 있다고 합니다. 이제 배열에 쓰이는 네 가지 연산이 얼마나 많은 단계가 필요한지 함께 적어두려고 합니다.

읽기 : 배열의 특정 인덱스에 어떤 값이 들어있는지 찾는 연산. 특정 인덱스를 집어 찾는 것이기 때문에 한 단계로 연산이 가능합니다. 예시는 위의 코드와 동일합니다.
검색 : 배열에서 특정 값이 있는지 알아보고 어떤 인덱스에 있는지 찾는 연산. 읽기와 반대로 특정 값을 집어 찾는 것이지만 효율성은 어마어마하게 다르다고 합니다. 인덱스는 바로 가서 값을 찾지만 검색은 배열의 길이에 따라 그리고 특정 값의 위치에 따라 해당 값을 찾는 데까지 많은 단계가 걸릴 수 있습니다.
```
function findUsers(users, target) {
    return users.includes(target);
}
console.log(findUsers(["doworld", "nagaeso", "zurang23"];, "nagaeso")); // true
```
삽입 : 배열 앞 또는 끝에 값을 추가하거나 중간에 값을 삽입하는 연산. 동적으로 데이터를 관리할 때 유용. 책에서는 끝에 추가하는 것이 가장 효율성이 높으며, 맨 처음이나 중간에 데이터를 삽입하면 삽입할 공간을 만들기 위해 많은 데이터 조각들이 이동해야 하므로 가장 많은 단계가 걸릴 수 있다.
```
const arr = [1, 2, 3];
arr.push(4); // 배열 끝에 추가
arr.splice(1, 0, 5); // 배열 중간에 추가
```
삭제 : 배열의 끝에서 값을 제거하거나 중간 값을 제거하는 연산. 데이터를 갱신할 때 필요. 기술적으로 해당 데이터만 삭제하는 한 단계만 걸리지만, 배열 내 빈 공간이 발생하여 뒤에 있는 데이터들이 빈 공간을 메꾸는 데이터 이동이 일어나기 때문에 배열의 길이에 따라 계산 단계가 영향을 받습니다.
```
const arr = [1, 2, 3, 4];
arr.pop(); // 배열 끝에서 삭제
arr.splice(1, 1); // 배열 중간에서 삭제
```

또 다른 자료 구조인 집합이 있는데요.

집합은 중복 값을 허용하지않는, 즉 중복 없는 데이터를 저장하는 데 사용되며, 태그 관리 시스템에서 중복된 태그를 방지하는 데 자주 활용됩니다.

예시는 배열 기반 집합인데요. 중복 금지라는 제약이 하나 더 추가된 배열입니다.

const tags = new Set(["html", "css", "javascript"]);
tags.add("html"); // html가 배열 내 있으나 추가. 중복 방지
console.log(tags); // Set { "html", "css", "javascript" }

검색 알고리즘

위의 자료 구조로 설명했던 배열과 집합 외에 정렬된 배열도 있는데요. 정렬된 배열은 값이 항상 순서대로 있는 구조입니다. 해당 자료 구조도 동일하게 네 가지 주요 연산이 있는데, 가장 강력한 부분은 검색 연산에 있습니다. 바로 이진 검색인데요. 아래 예시 코드와 함께 설명드리겠습니다.

이진 검색 : 배열이 정렬된 상태에서 원하는 값을 찾기 위해 배열을 반으로 나누는 과정을 반복하여 찾아 검색 속도가 크게 향상됩니다. 배열의 크기가 클수록 더 빠르게 값을 찾을 수 있다고 합니다. 단, 이진 검색은 반드시 정렬된 배열에서만 사용 가능합니다.
```
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const middle = Math.floor((left + right) / 2);
        if (arr[middle] === target) return middle;
        if (arr[middle] < target) left = middle + 1;
        else right = middle - 1;
    }

    return -1; // 찾을 수 없음
}

const sortedArray = [1, 3, 5, 7, 9];
console.log(binarySearch(sortedArray, 5)); // 2
```
- 배열의 중간 값 확인.
- 중간 값이 찾고자 하는 값보다 크다면, 오른쪽 절반을 버림.
- 중간 값이 찾고자 하는 값보다 작다면, 왼쪽 절반을 버림.
- 찾고자 하는 값을 발견하거나 더 이상 나눌 부분이 없을 때까지 이 과정 반복.

선형 검색 : 배열의 첫 번째 데이터부터 차례대로 원하는 값을 찾는 방법입니다. 정렬되지 않은 배열에서도 사용할 수 있지만, 배열의 크기가 클수록 오래 걸린다고 합니다.

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1; // 찾을 수 없음
}

const unsortedArray = [7, 1, 9, 3, 5];
console.log(linearSearch(unsortedArray, 5)); // 4

빅 오 표기법

빅 오 표기법은 알고리즘이 얼마나 효율적인지를 측정하는 도구입니다. 이는 입력 데이터 크기(N)가 커질수록 알고리즘이 얼마나 많은 단계를 수행해야 하는지를 나타내줍니다. 최악의 경우(가장 많은 단계를 요구하는 상황)를 기준으로 알고리즘의 성능을 평가하는데, 이것은 입력 크기에 따라 성능 변화가 어떻게 일어나는지를 이해하는 데 도움을 준다고 합니다.

O(1): 상수 시간 : 작업의 단계 수가 입력 크기에 영향을 받지 않을 때 사용.

// O(1): 상수 시간
// 예를 들어, 배열의 첫 번째 요소를 가져오는 작업은 배열 크기와 상관없이 항상 한 단계로 완료되므로 O(1)로 표현됩니다.
function getElementAtIndex(arr, index) {
    return arr[index]; // 배열 크기와 무관하게 한 단계로 실행
}

O(n): 선형 시간 : 입력 크기에 비례하여 단계 수가 증가할 때 사용.

// O(n): 선형 시간
// 예를 들어, 배열의 모든 요소를 출력하는 작업은 데이터 크기(N)에 비례하여 단계 수가 증가하므로 O(n)으로 표현됩니다.
function printElements(arr) {
    arr.forEach(element => console.log(element)); // 배열 크기만큼 실행
}

O(n^2): 이차 시간 : 입력 크기가 커질수록 단계 수가 입력 크기의 제곱에 비례하여 증가. 이 유형의 알고리즘은 중첩 반복문이 있을 때 자주 나타납니다.
```
function printPairs(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            console.log(arr[i], arr[j]);
        }
    }
}
```
O(logN): 로그 시간 : 입력 크기를 반복적으로 절반으로 나누는 작업이 있을 때 사용됩니다. 원소가 하나가 될 때까지 데이터 원소를 계속해서 반으로 줄이는 만큼의 단계 수가 걸린다는 뜻인데, 대표적인 예로 위에서 설명드린 이진 검색이 있습니다.
- 로그는 로가리즘의 줄임말인데요. (저도 이걸 보면서 처음 알았네요;) 로가리즘이라고 부르는 이 표기법은 데이터 크기가 기하급수적으로 증가해도, 단계 수는 매우 느리게 증가하는 특징이 있습니다. 큰 데이터 집합에서도 효율적으로 동작할 수 있는 강력한 알고리즘이라고 합니다.
```
function findIndexWithLog(arr, target) {
    return binarySearch(arr, target);
}
const data = Array.from({ length: 1000000 }, (_, i) => i);
console.log(findIndexWithLog(data, 999999)); // 999999
```
O(n log n): 로그 선형 시간 : 알고리즘의 실행 시간이 선형 시간과 로그 시간이 결합된 형태로, 일반적으로 병합 정렬이나 퀵 정렬과 같은 정렬 알고리즘에서 나타나며, 입력 크기가 두 배로 늘어나면 실행 시간은 약 두 배의 로그만큼 증가한다고 합니다.
O(2^n): 지수 시간 : 입력 크기에 대해 실행 시간이 지수적으로 증가하는 것을 말하는데요. 입력 크기가 증가할수록 실행 시간이 매우 빠르게 증가한다고 합니다.
자세한 내용은 BK - Big-O 표기법 글을 확인해주세요~! :)

정렬 알고리즘

정렬 알고리즘에 여러 가지가 있지만 버블 정렬과 선택 정렬, 병합 정렬에 대해 공유드리려고 합니다.

버블 정렬 : 배열에서 인접한 두 데이터를 비교해서 큰 값을 뒤로 보내고 작은 값을 앞으로 보내는 과정을 반복하는 단순한 정렬 알고리즘 중 하나입니다. 가장 큰 값이 맨 뒤로 "버블"처럼 올라가면서 정렬되어 버블 정렬이라고 합니다.
```
function bubbleSort(arr) {
    let n = arr.length;
    let swapped;
    do {
        swapped = false; // 교환이 이루어졌는지 확인하는 변수
        for (let i = 0; i < n - 1; i++) {
            // 인접한 두 원소를 비교
            if (arr[i] > arr[i + 1]) {
                // 크기가 크면 두 원소를 교환
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
                swapped = true; // 교환이 이루어졌음을 표시
            }
        }
        n--;  // 최댓값이 맨 뒤로 가므로 그 자리는 다시 검사할 필요가 없으므로 n을 줄입니다.
    } while (swapped);  // 교환이 이루어졌다면 계속 반복
    return arr;
}

const numbers1 = [5, 3, 8, 4, 2];
console.log(bubbleSort(numbers1)); // [2, 3, 4, 5, 8]
```
- 작은 데이터 배열에서는 잘 동작하지만, 배열이 커질수록 성능이 급격히 떨어져 효율적인 알고리즘은 아닌 것으로 보입니다. 이차 시간(O(n^2))이 걸리는 이유는 비교를 여러 번 반복하기 때문입니다.
- 여기서 이차 시간이라는 개념이 생소하실 텐데요. 지속적으로 두 원소를 비교하여 정렬을 하는 것을 반복하기에 버블 정렬의 시간 복잡도는 O(n^2)이고, 비교 횟수와 교환 횟수가 모두 n^2에 비례하기 때문에 "이차 시간"이라고 부릅니다.

선택 정렬 : 배열에서 가장 작은 원소를 찾아 맨 앞으로 이동시키는 과정을 반복해서 배열을 정렬하는데, 한 번의 반복에서 최솟값을 찾아서 맨 앞의 원소와 교환하기 때문에 비교 횟수가 제곱 비례합니다. 이 또한 시간 복잡도는 O(n^2)라고 볼 수 있겠네요.

function selectionSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let minIndex = i; // 최소값의 인덱스를 기록
        for (let j = i + 1; j < arr.length; j++) {
            // 현재 인덱스 이후의 원소들을 비교하여 최소값을 찾음
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // 최소값의 인덱스를 업데이트
            }
        }
        // 최소값을 현재 인덱스 위치와 교환
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
    return arr;
}

const numbers2 = [5, 3, 8, 4, 2];
console.log(selectionSort(numbers2)); // [2, 3, 4, 5, 8]

병합 정렬 : 배열을 반식 나누고 정렬한 후 병합하는 방식입니다. 배열의 크기가 두 배가 되면 log n 만큼 분할되고, 병합 과정에서 n 만큼 시간이 걸리기 때문에 병합 정렬의 시간 복잡도는 O(n log n)이라고 볼 수 있습니다.

function mergeSort(arr) {
    if (arr.length <= 1) return arr;  // 배열의 길이가 1 이하일 경우 그대로 반환

    const mid = Math.floor(arr.length / 2);  // 배열의 중간 인덱스 계산
    const left = mergeSort(arr.slice(0, mid));  // 배열을 반으로 나누어 왼쪽 부분 정렬
    const right = mergeSort(arr.slice(mid));  // 배열을 반으로 나누어 오른쪽 부분 정렬

    return merge(left, right);  // 두 부분을 병합하여 반환
}

function merge(left, right) {
    const result = [];
    while (left.length && right.length) {
        // 왼쪽과 오른쪽에서 더 작은 값을 result에 추가
        if (left[0] < right[0]) {
            result.push(left.shift());  // 왼쪽에서 작은 값 추출
        } else {
            result.push(right.shift());  // 오른쪽에서 작은 값 추출
        }
    }
    // 남은 값들을 result에 추가
    return [...result, ...left, ...right];
}

const numbers4 = [5, 3, 8, 4, 2];
console.log(mergeSort(numbers4)); // [2, 3, 4, 5, 8]

참고 문서

누구나 자료 구조와 알고리즘 - 제이 웬그로우 저/심지현 역

마치며

작업을 진행하면서 자주 접하는 너무 기본적인 데이터 구조들이 많이 보이실 텐데요. 스크립트를 작성하는 것과 별개로 개념에 대한 이해를 돕는데 조금이나마 도움이 되었으면 좋겠습니다. 아직 끝까지 다 읽지는 못하였지만 자료 구조와 알고리즘은 단순한 지식이 아니라, 실전에서 코드에 대한 이해와 효율성을 높일 수 있는 부분이라고 생각합니다. 단기간에 학습할 수 있는 영역은 아니기 때문에 계속 관련해서 보아야 할 텐데요. 혹 학습할 생각이 있으신 분이 계시다면 되도록 기초적인 배열, 리스트, 스택, 큐, 해시 테이블과 같은 주요 자료 구조의 원리나 사용법 등을 학습해 보시고 알고리즘을 연습할 수 있는 코딩 문제들이 많더라고요. 그런 것들을 활용하여 경험하면서 진행해 보시는 것도 좋을 것 같습니다. 저도 이후 알게 되는 것들에 대해 추가적으로 다시 정리하여 작성할 수도 있을 것 같네요. 해당 글은 여기까지이며, 이후 내용이 추가나 수정이 필요한 부분이 있다면 언제든 알려주세요.
부족한 글 읽어주셔서 감사합니다. 🙇🏻‍♀️
그럼 안녕히…👋 -The End-