[항해99 취업 리부트 코스 학습일지] 18일차

이번 주 목표 및 회고

📢 이번주 목표는 백준 실버1까지 승급하는 것이다. 현재 골드5이다.
     이번주 목표를 초과 달성했다. 더욱 더 열심히 해서 알고리즘 주차가 끝날 때에는 골드1까지 가보자
     갈수록 알고리즘도 더 어려워진다. 데일리 과제 매일 풀 수 있도록 부단히 노력을 해야겠다.

오늘 스케줄

09:00~09:20 팀 모닝 스크럼
09:20~12:00 데일리 과제 문제 풀이
12:00~13:00 점심 식사
13:00~17:00 데일리 과제 문제 풀이
17:00~17:40 팀 코드 선정 회의
18:00~18:20 기술 매니저님과 팀 코드 리뷰
18:20~19:20 저녁 식사
19:20~20:00 산책
20:00~00:00 백준 6문제 문제 풀이

오늘 목표

👉 데일리 과제 모두 풀기

👉 TIL 빠지지 않고 작성하기

👉 백준 6문제 문제 풀이

👉 북 스터디 참여

오늘 한 것

• 데일리 과제 모두 풀기
• TIL 빠지지 않고 작성하기
• 백준 6문제 문제 풀이

오늘 못한 것

• 북스터디 참여

알게된 것

⭐ DFS(Depth-first Search)

• 깊이 우선 탐색
• 연결된 노드를 따라서 계속 방문을 한 후에 연결된 노드들이 없을 때 그 전 노드로 되돌아가고 다시 연결된 노드를 따라서 탐색

특징

• 자기 자 신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
• 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
• 이 알고리즘을 구현할 떄 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다. -> 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.

자바에서의 DFS 구현 코드

방향 그래프 일 때의 DFS 구현 코드

import java.util.*;

class Graph {
    private int V; // 정점의 수
    private LinkedList<Integer> adj[]; // 인접 리스트

    // 생성자
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    // 그래프에 간선 추가
    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    // 주어진 시작 정점에서부터 도달 가능한 정점들을 DFS로 탐색
    void DFS(int s) {
        // 모든 정점을 방문하지 않은 상태로 초기화
        boolean visited[] = new boolean[V];

        // DFS를 위한 스택 생성
        Stack<Integer> stack = new Stack<>();

        // 현재 노드를 방문한 것으로 표시하고 스택에 넣음
        visited[s] = true;
        stack.push(s);

        while (!stack.isEmpty()) {
            // 스택에서 정점을 꺼내고 출력
            s = stack.pop();
            System.out.print(s + " ");

            // 꺼낸 정점의 모든 인접 정점을 확인
            // 방문하지 않은 인접 정점이 있다면 방문 표시하고 스택에 넣음
            for (int v : adj[s]) {
                if (!visited[v]) {
                    visited[v] = true;
                    stack.push(v);
                }
            }
        }
    }

    public static void main(String args[]) {
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("정점 2에서 시작하는 그래프의 DFS 탐색:");
        g.DFS(2);
    }
}

무방향 그래프 일 때의  DFS 구현 코드

import java.util.*;

class Graph {
    private int V; // 정점의 수
    private LinkedList<Integer> adj[]; // 인접 리스트

    // 생성자
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    // 그래프에 간선 추가
    void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v); // 무방향 그래프에서는 w에서 v로의 간선도 추가
    }

    // 주어진 시작 정점에서부터 도달 가능한 정점들을 DFS로 탐색
    void DFS(int s) {
        // 모든 정점을 방문하지 않은 상태로 초기화
        boolean visited[] = new boolean[V];

        // DFS를 위한 스택 생성
        Stack<Integer> stack = new Stack<>();

        // 현재 노드를 방문한 것으로 표시하고 스택에 넣음
        visited[s] = true;
        stack.push(s);

        while (!stack.isEmpty()) {
            // 스택에서 정점을 꺼내고 출력
            s = stack.pop();
            System.out.print(s + " ");

            // 꺼낸 정점의 모든 인접 정점을 확인
            // 방문하지 않은 인접 정점이 있다면 방문 표시하고 스택에 넣음
            for (int v : adj[s]) {
                if (!visited[v]) {
                    visited[v] = true;
                    stack.push(v);
                }
            }
        }
    }

    public static void main(String args[]) {
        Graph g = new Graph(5);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 4);

        System.out.println("정점 0에서 시작하는 그래프의 DFS 탐색:");
        g.DFS(0);
    }
}

 

🤔오늘의 반성

- 바쁘다는 핑계로 책을 안 읽고 있다.
- TIL을 늦게 작성했다.

 

👍 오늘의 칭찬

1. 지각하지 않았다.
2. 깃헙 1일 1커밋 달성
3. TIL을 빠지지 않고 작성했다.
4. 오늘의 데일리 과제 모두 풀었다.
5. 이번주 목표인 백준 골드5을 달성했다.

❗ 항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.
https://hanghae99.spartacodingclub.kr/reboot