태야

DFS(Depth-First Search)와 BFS(Breadth-First Search)는 그래프나 트리 탐색에서 사용하는 대표적인 탐색 알고리즘이다. 두 알고리즘 모두 특정 노드를 방문하고, 그 노드와 연결된 다른 노드들을 탐색하는 방식으로 동작한다. DFS는 깊이를 우선으로 탐색하고, BFS는 너비를 우선으로 탐색한다.

1. DFS (Depth-First Search, 깊이 우선 탐색)

DFS는 탐색할 때 가능한 한 깊게 들어가는 방식으로 탐색한다. 즉, 한 경로를 따라 끝까지 가고, 더 이상 갈 곳이 없으면 다시 돌아와 다른 경로를 탐색한다. 이 방식은 재귀나 스택을 사용해 구현할 수 있다.

DFS 예시: 그래프 탐색

function dfs(graph, start, visited = new Set()) {
    // 현재 노드 방문 처리
    visited.add(start);
    console.log(start);

    // 현재 노드와 연결된 노드들을 재귀적으로 방문
    for (let neighbor of graph[start]) {
        if (!visited.has(neighbor)) {
            dfs(graph, neighbor, visited);
        }
    }
}
// 그래프 표현 (인접 리스트)
const graph = {
    1: [2, 3],
    2: [4],
    3: [5],
    4: [],
    5: []
}

dfs(graph, 1);  // 출력: 1 2 4 3 5

DFS의 시간 복잡도

• 시간 복잡도: O(V + E) (V는 노드 수, E는 간선 수)
• 그래프의 모든 노드를 방문하고 모든 간선을 처리해야 하기 때문에, 위와 같은 복잡도를 가진다.

2. BFS (Breadth-First Search, 너비 우선 탐색)

BFS는 탐색할 때 가까운 노드부터 차례대로 방문한다. 즉, 특정 노드에서 연결된 모든 노드를 먼저 탐색한 후, 그 다음 깊이의 노드들을 탐색한다. 이 방식은 큐(Queue) 자료 구조를 사용해 구현한다.

BFS 예시: 최단 경로 탐색

function bfs(graph, start) {
    const queue = [start]; // 탐색할 노드를 저장할 큐
    const visited = new Set(); // 방문한 노드를 저장할 집합
    visited.add(start);

    while (queue.length > 0) {
        const node = queue.shift(); // 탐색할 노드를 큐에서 꺼냄
        console.log(node);

        for (let neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
}

// 그래프 표현 (인접 리스트)
const graph = {
    1: [2, 3],
    2: [4],
    3: [5],
    4: [],
    5: []
};

bfs(graph, 1);  // 출력: 1 2 3 4 5

BFS의 시간 복잡도

• 시간 복잡도: O(V + E) (V는 노드 수, E는 간선 수)
• 모든 노드와 모든 간선을 한 번씩 방문하기 때문에 DFS와 마찬가지로 같은 복잡도를 가진다.

DFS와 BFS의 차이

• 탐색 방식: DFS는 깊이 우선으로 탐색하며, BFS는 너비 우선으로 탐색한다.
• 구현 방식: DFS는 재귀나 스택을 사용하고, BFS는 큐를 사용해 구현한다.
• 사용 사례:
  • DFS는 경로 탐색(예: 미로 찾기)나 백트래킹이 필요한 문제에 적합하다.
  • BFS는 그래프에서 최단 경로를 찾는 문제에 적합하다.

예시 문제

1. 미로 찾기

문제: N x M 크기의 미로가 주어질 때, 출발점에서 도착점까지 최단 경로를 찾으세요. 벽은 통과할 수 없으며, 상하좌우로만 이동할 수 있습니다.

// BFS
function shortestPath(maze, start, end) {
    const directions = [[0, 1], [1, 0], [0, -1], [1, 0]];
    const queue = [[start, 0]]; // [현재위치, 이동거리]
    const visited = new Set();
    visited.add(start.toString());

    while (queue.length > 0) {
        const [[x, y], distance] = queue.shift();

        if (x === end[0] && y === end[1]) return distance;

        for (let [dx, dy] of directions) {
            const newX = x + dx;
            const newY = y + dy;

            if (newX >= 0 && newY >= 0 &&
                newX < maze.length && newY < maze[0].length &&
                maze[newX][newY] === 0 && !visited.has([newX, newY].toString())
            ) {
                visited.add([newX, newY].toString());
                queue.push([[newX, newY], distance + 1]);
            }
        }
    }

    return -1; // 도착할 수 없는 경우
}

const maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
];

console.log(shortestPath(maze, [0, 0], [4, 4]));  // 출력: 8 (최단 경로 거리)

2. 섬 개수 세기

문제: 2차원 배열에서 육지를 1, 바다를 0으로 나타내는 섬의 지도에서, 섬(연결된 1의 집합)의 개수를 구하세요.

// DFS
function numIslands(grid) {
    let count = 0;

    function dfs(grid, x, y) {
        if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] === '0') {
            return;
        }

        grid[x][y] = '0'; // 방문한 곳은 0 처리
        dfs(grid, x + 1, y);
        dfs(grid, x - 1, y);
        dfs(grid, x, y + 1);
        dfs(grid, x, y - 1);
    }

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === '1') {
                count++;
                dfs(grid, i, j);
            }
        }
    }

    return count;
}

const grid = [
    ['1', '1', '0', '0', '0'],
    ['1', '1', '0', '0', '0'],
    ['0', '0', '1', '0', '0'],
    ['0', '0', '0', '1', '1']
];

console.log(numIslands(grid));  // 출력: 3 (3개의 섬)

patch-package

서드파티 라이브러리를 커스텀한 상태가 배포상태에서도 지속되도록 관리해주는 패키지.

즉, node_modules에 수정한 사항이 git으로 관리되고 어떠한 실행 환경에서도 적용되도록 한다.

patch-package를 사용할 시 매번 버전이 달라질 때마다 patch 파일의 버전을 인스톨 되어 있는 버전과 맞춰줘야 하는 단점이 있다.

1. 설치

npm install —save-dev patch-package

2. 설정

// package.json

"scripts": {
	"postinstall": "patch-package", // 해당 스크립트 추가
},

3. 변경하고자 하는 패키지 코드 수정

패키지 코드를 원하는대로 수정한다.

4. patch 적용

npx patch-package [변경한 패키지 이름]

5. “patches”라는 폴더가 생기고, 폴더 안에 변경한 패치 내용이 저장되어 있음을 확인

6. node_moduels 을 지웠다가 npm install 해보면 자동으로 패치내용들이 적용되어 있음

주의) 수정한 패키지의 patches 버전과 package.json의 패키지 버전이 다르면 에러를 유발하니 버전 체크하는 것이 중요!

<내 풀이>

function solution(heights) {
    var answer = []

    for(var i = heights.length - 1; i > 0; i--){
        for(var j = i - 1; j>=0; j--){
            if(heights[i] < heights[j]){
                answer.unshift(j+1);
                break;
            }else if(j === 0){
                answer.unshift(0);
            }
        }
        
    }
    answer.unshift(0); 
    return answer;
}

<다른 풀이>

function solution(heights) {
    return heights.map((v, i) => {
        while (i) {
            i--;
            if (heights[i] > v) {
                return i + 1;
            }
        }
        return 0;
    });
}

<공부>

map() : 인자로 주어진 함수(여기선 화살표 함수)에 모든 각각의 요소를 적용한 값으로 이루어진 배열을 반환합니다

Arrow function(화살표 함수) : 화살표 함수는 항상 익명이다. 메서드 함수가 아닌 곳에서 적합하며, 그래서 생성자로 사용을 못 한다.

var add = function (a,b) {
	return a+b;
};

// {} 블럭이 없는 경우(한 줄로 표현이 되는 경우)
var add = (a,b) => a+b;

// {} 블럭이 필요한 경우 --> 반드시 return 키워드를 사용해야함
var something = (a,b) => {
	//do something more
    return a * b;
};