#000#IT_Knowledge#010#Develop_Knowledge#010.10#Data_Structure_and_Algorithm#010.10 a#Why_learn_data_structures_and_algorithms?

데이터 구조와 알고리즘 배워야 하는 이유

프로그래밍적으로 문제를 풀 때 데이터 구조와 알고리즘을 알고 있으면 풀 수 있는 것도 더 효율적으로 구현하거나, 풀 수 없는 것도 해당 이론을 바탕으로 해결 가능한 실마리를 제공하기 때문. 또한 이런 개념들이 실제 하드웨어나 메모리,네트워크 등의 레벨에서도 구현이 돼 있기 때문에 이를 알아야 문제가 생기거나 최적화 할 때 "이해"가 가능하다. 이런 이유로 위의 개념들을 알아야 한다고 생각한다..

특히 시간복잡도 등을 구체적으로 수치화하고 평가할 때 쓰이기도 한다. 하지만 지인 말을 빌리자면 10년 넘게 업계에서 개발자들 중 시간 복잡도를 신경쓰면서 구현할 것을 본적이 없다고 한다. 요즘 흐름은 하드웨어나 RAM등을 업그레이드 해버리면 문제가 해결되니깐 그러는것 같다고... 어느정도 맞는 말이긴 하지만 개인적으로 정말 큰 규모나 복잡한 시스템에서는 단순하게 RAM을 늘리는 것만으로는 해결이 불가능한, 구조적으로 수정과 재설계가 필요한 문제가 발생할 수 있다. 그런 때에 이 지식들을 알고 있어야 문제를 해결할 수 있지 않을까 라고 개인적으로 생각한다.
즉 알고 있어야 하지만, 현실에서 잘 안 쓰일 수 있지만, 그래도 큰 문제나 근본적인 문제와 같은 어려운 문제를 해결할 때는 필수적인 지식.

구체적인 내용은 구글에 쳐보면 그림, 영상 등과 함께 자세히 설명돼 있기에 그걸 내가 굳이 한 번 더 쓸 필요는 없을 것이다. 그래서 생각한 것이 특정 구조나 알고리즘에 대한 나만의 키워드로 정리해 놓으려 합니다.

Algorithm

검색 알고리즘

선형 검색

단순, 처음부터 나올 때까지

이진 검색

이미 오름차순 정렬된 상태, 중간 기준으로 크다 작다 비교

정렬

버블 정렬

O(n^2), 1 회전마다 가장 큰 값이 끝에 위치, 두 개를 교환

function bubble_sort(arr){
    let copy = [...arr];


    for (let i = 0; i < arr.length-1 ; i++){

        console.log(`${i}회차 정렬 시작`);
        for (let j =0; j < arr.length-1-i;j++){

            if (copy[j] > copy[j+1]){
                [copy[j+1] ,copy[j]] = [copy[j], copy[j+1]];
                console.log(copy);
            }
        }
        console.log("-----------");

    }

    return copy;
}
let array1 = [5, 3, 8, 4, 2];
console.log("Original:", array1);
console.log("Sorted:", bubble_sort(array1));
// Expected output: [2, 3, 4, 5, 8]

선택 정렬

최악 시간복잡도 O(n^2), 1회전마다 가장 작은수가 맨 앞과 교환,

function selection_sort(arr) {

    let copy = [...arr]

    for (let i = 0; i < copy.length - 1; i++) {
        let minIndex = i;

        console.log(`${i}회차 회전`)
        for (let j = i + 1; j < copy.length; j++) {

            if (copy[j] < copy[minIndex]) {
                minIndex = j

            }
        }

        // 최소값을 현재 위치의 값과 교환
        if (minIndex !== i) {
            [
                copy[i], copy[minIndex]
            ] = [
                copy[minIndex], copy[i]
            ];
        }
        console.log(copy)

    }

    return copy;
}

// 테스트 예제
let array1 = [64, 25, 12, 22, 11];
console.log("Original:", array1);
console.log("Sorted:", selection_sort(array1));
// Expected output: [11, 12, 22, 25, 64]

병합 정렬

원소가1개가 될때까지 분할, 이후부터 정복하는데 빈 리스트를 통해 해당 정렬 수행, O(n logn)

function merge(left, right) {
    let result = [];
    let leftIndex = 0;
    let rightIndex = 0;

    console.log(`left: ${left} right: ${right}`)
    while (leftIndex < left.length && rightIndex < right.length) {

        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex])
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }

    }

    return result
        .concat(left.slice(leftIndex))
        .concat(right.slice(rightIndex));

}

function mergeSort(arr) {

    if (arr.length <= 1) {
        return arr;
    }

    const middle = Math.floor(arr.length / 2);
    const left = arr.slice(0, middle);
    const right = arr.slice(middle);

    return merge(mergeSort(left), mergeSort(right));

}

// 테스트 케이스 1: 일반적인 배열
let array1 = [
    38,
    27,
    43,
    3,
    9,
    82,
    10
];
console.log("Original:", array1);
console.log("Sorted:", mergeSort(array1));
// Expected output: [3, 9, 10, 27, 38, 43, 82]

Data Structure

힙

스택

큐

딕셔너리