coin FE

프론트엔드 개발자이기전에 우리 직종도 개발자이기에 너무 딥하게 알 필요도 없긴 하지만 그래도 어느 정도 기초적인 부분은 알고 사용할 수 있어야한다고 생각을 한다.

코테를 위한 알고리즘 공부가 아닌 실무에서 어떤 식으로 사용이 가능할지 생각하고 분석하고 문제점을 파악하는 부분이 꼭 필요하다고 느낀다. 하지만 프론트개발에서 알고리즘은 그닥 그렇게 중요하지가 않다. 이미 추상화가 되어있는 노드JS API 이고 브라우저 단에서는 대용량 데이터를 처리하지 않고 간단한 필터링 조건으로만 사용될 뿐이지 그다지 중요성을 못느끼긴 했다. getElementById 함수가 dom 트리구조를 DFS 로 탐색하는것을 굳이 알지 않아도 된다 ID 속성을 받고, 출력으로 DOM 엘리먼트가 반환된다는 사실 자체만 이해하고 쓰는게 더 경제적이다.

추상화된 형태로 제공되는 알고리즘의 입출려만 잘 알면 실무에서는 크게 신경쓸게 없다. 하지만 여러가지 상황에서는 알고리즘이 필요한 부분이 있다.큰 배열이 아닌 정렬이 되어 있다면 이분 탐색으로 값을 찾는 것이 훨씬 더 빠르다. 그리고 서버에서 받은 데이터를 메모이제이션 동적프로그래밍으로 똑같은 계산을 다시 할 때에는 기억해둔 결과를 가져다 쓰는 것으로 성능을 끌어올릴 수 있다. 리액트에서는 useMemo, useCallback 으로 내장 API 로 제공한다. 동적 프로그래밍을 활용하여 중복된 계산을 줄이고 큰 문제를 작은 문제로 분할하여 해결함으로써 복잡한 계산의 효율성을 높일 수 있다.

프론트개발에 있어서 알고리즘 공부가 딱히 필요성을 못느꼈던건 연차가 적어서 작은일을 맡아서 작업을 해서 그랬던 것 같다. 요구사항에만 중점을 두고 거기에 맞춰서 작업을 하는라 제대로 된 알고리즘의 개념을 도입하지 못하고 효율성, 성능을 무시하고 만들었던 것 같았다. 특히 많이 필요성을 느낀 부분에 알고리즘 부터 정리를 해보겠다.

1. 정렬 알고리즘

정렬 알고리즘은 컴퓨터가 데이터를 특정한 순서대로 나열하는 방법을 뜻하고 가나다순으로 정리 또는 사람 키를 작은 순서대로 세우는 것과 같음 

 사용 되는 이유 

• 프론트는 유독 배열을 가지고 작업을 많이 한다.  1년차일 때 정말 힘들었다.. 여기서 정렬 알고리즘을 알고 코드를 만들었다면 성능, 최적화 등등 개발 시간 단축을 하였을것이다. 특정 데이터를 찾는 시간을 단축 시켜주고 단어를 찾듯이 정렬된 데이터에서 원하는 값을 빠르게 찾을 수 있다. 그리고 통계분석, 데이터 시각화 등 다양한 분석 작업을 수월하게 만들어 준다. 많은 알고리즘들이 정렬된 데이터를 기반으로 작동하기에 정렬 알고리즘은 프론트개발 하는 사람들도 필수적으로 꼭 알아야하는 기본인 부분인 것 같다. 예시로 내가 전에 다니던 회사에서 가격, 인기순, 이름순 등등 여러가지 필터링 조건으로 화면에 뿌려주는 작업이 있었는데 여기서 정렬 알고리즘을 개념을 좀 더 빠삭하게 알고 있었더라면 수월하게 빠른 시간내에 끝내지 않았을까 하는 생각이 든다.

종류

• 버블 정렬: 인접한 두 원소를 비교 자리를 변경하여 반복하는 알고리즘 효율성 안 좋음

const bubbleSort = (arr) => {
    const n = arr.length; // 배열의 길이를 저장
    for (let i = 0; i < n - 1; i++) { // 배열을 n-1번 반복
        for (let j = 0; j < n - i - 1; j++) { // 매 반복마다 큰 수를 뒤로 보냄
            if (arr[j] > arr[j + 1]) { // 인접한 두 요소 비교
                // 스왑: 두 요소의 위치를 교환
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr; // 정렬된 배열 반환
};

// 사용 예
console.log(bubbleSort([64, 34, 25, 12, 22, 11, 90]));

• 선택 정렬: 가장 작은 값을 찾아 앞으로 보내는 방식 반복하는 알고리즘 버블 보다 성능이 좋으나 느림

const selectionSort = (arr) => {
    const n = arr.length; // 배열의 길이를 저장
    for (let i = 0; i < n - 1; i++) { // 배열을 n-1번 반복
        let minIndex = i; // 현재 인덱스를 최소값 인덱스로 설정
        for (let j = i + 1; j < n; j++) { // 현재 인덱스 이후의 요소들 비교
            if (arr[j] < arr[minIndex]) { // 더 작은 요소 발견
                minIndex = j; // 최소값 인덱스 업데이트
            }
        }
        // 스왑: 최소값을 현재 인덱스와 교환
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
    return arr; // 정렬된 배열 반환
};

// 사용 예
console.log(selectionSort([64, 34, 25, 12, 22, 11, 90]));

• 삽입 정렬: 정렬된 부분과 정렬되지 않은 부분을 나눠 정렬되지 않은 부분의 원소를 적절한 위치에 삽입하는 알고리즘

const insertionSort = (arr) => {
    const n = arr.length; // 배열의 길이를 저장
    for (let i = 1; i < n; i++) { // 1부터 시작 (첫 번째 요소는 이미 정렬됨)
        const key = arr[i]; // 현재 요소를 key로 저장
        let j = i - 1; // 정렬된 부분의 마지막 인덱스

        // key보다 큰 요소를 오른쪽으로 이동
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; // 요소 이동
            j--; // 인덱스 감소
        }
        arr[j + 1] = key; // key를 올바른 위치에 삽입
    }
    return arr; // 정렬된 배열 반환
};

// 사용 예
console.log(insertionSort([64, 34, 25, 12, 22, 11, 90]));

• 퀵 정렬: 기준 값을 설정하고 기준 값보다 작은 값과 큰 값으로 나누는 방식을 재귀적으로 반복하는 알고리즘

const quickSort = (arr) => {
    if (arr.length <= 1) return arr; // 배열의 길이가 1 이하이면 그대로 반환
    const pivot = arr[arr.length - 1]; // 마지막 요소를 피벗으로 선택
    const left = []; // 피벗보다 작은 요소를 저장할 배열
    const right = []; // 피벗보다 큰 요소를 저장할 배열

    for (let i = 0; i < arr.length - 1; i++) { // 피벗 제외하고 모든 요소 비교
        if (arr[i] < pivot) {
            left.push(arr[i]); // 피벗보다 작은 요소 추가
        } else {
            right.push(arr[i]); // 피벗보다 큰 요소 추가
        }
    }
    // 재귀적으로 왼쪽과 오른쪽 배열을 정렬 후 병합
    return [...quickSort(left), pivot, ...quickSort(right)];
};

// 사용 예
console.log(quickSort([64, 34, 25, 12, 22, 11, 90]));

• 합병 정렬: 리스트를 계속해서 반으로 나누어 정렬한 후 다시 합치는 방식을 반복하는 알고리즘 가장 안정적인 알고리즘임

const 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); // 두 정렬된 배열 병합
};

const merge = (left, right) => {
    const result = []; // 결과를 저장할 배열
    let i = 0, j = 0; // 왼쪽과 오른쪽 배열의 인덱스

    // 두 배열을 비교하여 정렬된 형태로 병합
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i]); // 왼쪽 요소 추가
            i++; // 왼쪽 인덱스 증가
        } else {
            result.push(right[j]); // 오른쪽 요소 추가
            j++; // 오른쪽 인덱스 증가
        }
    }
    // 남아 있는 요소 추가
    return result.concat(left.slice(i)).concat(right.slice(j));
};

// 사용 예
console.log(mergeSort([64, 34, 25, 12, 22, 11, 90]));

정렬 알고리즘은 특성에 맞게 적용을 시키면 간결하고 성능, 최적화, 개발 속도가 더 빨라질 것 이다.

데이터의 크기가 작다면 삽입 정렬과 같은 간단한 알고리즘을 사용하고 데이터가 거의 정렬되어 있다면 삽입 정렬이 

효율적이고 성능 적으로 빠른 처리 속도가 필요하다면 퀵 정렬이나 합병 절렬을 사용하는 것이 좋다.

2. 탐색 알고리즘

• 선형 탐색

- 배열의 처음부터 끝까지 모든 요소를 차례대로 확인하여 원하는 값을 찾는 방법

- 시간 복잡도 : O(n) (n은 배열의 크기) 

- 단순하고 구현 쉬움, 정렬 여부와 관계없이 사용 가능, 데이터가 많은 경우 비효율적임

const linearSearch = (arr, target) => {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i; // 목표값을 찾으면 인덱스 반환
        }
    }
    return -1; // 목표값을 찾지 못함
};

// 사용 예
const numbers = [5, 3, 8, 1, 2];
console.log(linearSearch(numbers, 8)); // 2

• 이분 탐색

- 정렬된 배열에서 중간값과 비교하여 탐색 범위를 반으로 줄여가면 값을 찾는 방법

- 시간 복잡도 O(log n)

- 효율적이고 대규모 데이터에 적합함

- 데이터가 정렬되어 있어야 사용 가능

const binarySearch = (arr, target) => {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid; // 목표값을 찾으면 인덱스 반환
        }
        if (arr[mid] < target) {
            left = mid + 1; // 오른쪽 절반 탐색
        } else {
            right = mid - 1; // 왼쪽 절반 탐색
        }
    }
    return -1; // 목표값을 찾지 못함
};

// 사용 예
const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(binarySearch(numbers, 7)); // 6

• 깊이 우선 탐색 ( DFS )

- 그래프나 트리에서 가능한 한 깊게 탐색하다가 더 이상 갈 수 없게 되면 이전단계로 돌아가는 방법

- 시간 복잡도 O(V+E) (V는 정점(꼮지점) 수, E는 간선(모서리 엣지) 수)

- 스택을 사용하여 구현 가능

- 경로 탐색 문제에 유용함

const dfs = (graph, start, visited = new Set()) => {
    if (!visited.has(start)) {
        console.log(start); // 방문한 정점 출력
        visited.add(start);
        const neighbors = graph[start] || [];
        neighbors.forEach(neighbor => dfs(graph, neighbor, visited)); // 재귀 호출
    }
};

// 사용 예
const graph = {
    A: ['B', 'C'],
    B: ['D'],
    C: ['E'],
    D: [],
    E: []
};

dfs(graph, 'A'); // A B D C E

• 너비 우선 탐색 ( BFS )

- 그래프나 트리에서 현재 정점(꼭지점) 의 이웃을 모두 탐색한 후, 다음 정점(꼭지점)으로 넘어가는 방법

- 시간 복잡도ㅓ: O(V+E)

- 큐를 사용 하여 구현가능

- 최단 경로 탐색 문제에 유용

const bfs = (graph, start) => {
    const visited = new Set();
    const queue = [start];

    while (queue.length > 0) {
        const vertex = queue.shift(); // 큐에서 정점 꺼내기
        if (!visited.has(vertex)) {
            console.log(vertex); // 방문한 정점 출력
            visited.add(vertex);
            const neighbors = graph[vertex] || [];
            queue.push(...neighbors); // 이웃 추가
        }
    }
};

// 사용 예
const graph2 = {
    A: ['B', 'C'],
    B: ['D'],
    C: ['E'],
    D: [],
    E: []
};

bfs(graph2, 'A'); // A B C D E

탐색 알고리즘은 데이터 구노 내에서 원하는 값을 찾는 데 필수적임 각 알고리즘은 특정 상황에서 더 효율적으로 유용하게 

사용 될 수 있음 데이터의 구조와 요구 사항에 따라 적절한 탐색 알고리즘을 선택하는것이 중요하다.

추후에 더 많은 내용을 추가하고 실무에서 적용한 내용과 사례들을 가지고 와보겠다.!