[항해99 취업 리부트 코스 학습일지] 3주차 알고리즘 학습 Day 5

Q. 오늘 진행된 강의에서 학습한 내용은 무엇인가요?

깊이 우선 탐색(DFS)이란 무엇인가요?

깊이 우선 탐색(DFS, Depth-First Search)은 그래프 탐색 알고리즘 중 하나로, 한 정점에서 시작하여 가능한 깊이까지 탐색한 후, 다시 돌아와 다른 경로를 탐색하는 방식입니다. 트리나 그래프의 모든 정점을 방문하는 데 사용됩니다.

깊이 우선 탐색의 특징

스택 기반: DFS는 스택 자료구조를 사용합니다. 재귀 호출을 이용하면 자연스럽게 함수 호출 스택을 사용하게 됩니다.

경로 탐색: 경로를 찾는 데 유용합니다. 예를 들어, 미로를 찾는 문제에 효과적입니다.

모든 정점 방문: 그래프의 모든 정점을 한 번씩 방문합니다.

시간 복잡도: DFS의 시간 복잡도는 O(V + E)이며, 여기서 V는 정점의 수, E는 간선의 수입니다.

 

너비 우선 탐색(BFS)이란 무엇인가요?

너비 우선 탐색(BFS, Breadth-First Search)은 그래프 탐색 알고리즘 중 하나로, 시작 정점에서부터 인접한 모든 정점을 먼저 방문하고, 방문한 정점에 인접한 정점들을 차례로 방문하는 방식입니다. 레벨 단위로 탐색하기 때문에 계층적인 구조를 탐색할 때 유용합니다.

너비 우선 탐색의 특징

큐 기반: BFS는 큐 자료구조를 사용합니다. 방문할 정점을 큐에 저장하고, 큐에서 정점을 꺼내면서 탐색을 진행합니다.

최단 경로 탐색: 무가중치 그래프에서 두 정점 사이의 최단 경로를 찾는 데 유용합니다.

모든 정점 방문: 그래프의 모든 정점을 한 번씩 방문합니다. 연결 성분을 찾는 데 유용합니다.

시간 복잡도: BFS의 시간 복잡도는 O(V + E)이며, 여기서 V는 정점의 수, E는 간선의 수입니다.

 

Q. 이번 주 진행된 팀 스터디에서 얻은 인사이트는 무엇인가요?

실제로 구현되는 DFS, BFS 문을 반복해서 숙지하기!

 

DFS

public static void dfs(int node) {
        visited[node] = true;
        order[node] = count++;

        for (int newNode : graph[node]) {
            if (!visited[newNode]) {
                dfs(newNode);
            }
        }
    }

 

BFS

public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        order[start] = count++;

        while (!queue.isEmpty()) {
            int node = queue.poll();

            for (int nextNode : graph[node]) {
                if (!visited[nextNode]) {
                    visited[nextNode] = true;
                    queue.add(nextNode);
                    order[nextNode] = count++;
                }
            }
        }
    }

 

 

항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.

https://hanghae99.spartacodingclub.kr/reboot

IT 커리어 성장 코스 항해99, 개발자 취업부터 현직자 코스까지