Part of your World

DFS(깊이 우선 탐색, Depth-First Search)는 그래프나 트리를 탐색하는 알고리즘 중 하나이다. 이 방법은 주어진 그래프의 모든 정점(Vertex)을 방문하는 경로를 찾을 때 사용한다.

DFS는 이름에서 알 수 있듯이, 깊이 방향으로 우선 탐색하는 것을 기본 원리로 한다. 즉, 시작 노드에서 가능한 한 깊숙히 들어가면서 노드를 탐색하고, 더 이상 탐색할 자식 노드가 없을 경우 이전 노드로 돌아와서 그 다음 노드를 탐색하는 방식이다.

DFS의 동작 과정은 다음과 같다:

1. 시작 노드를 선택하여 방문하고 방문한 노드를 스택에 push한다.
2. 현재 방문한 노드에 인접한 노드 중에서 아직 방문하지 않은 노드가 있다면 그 노드를 방문하고 방문한 노드를 스택에 push한다. 만약 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 pop한다.
3. 더 이상 2번의 과정을 반복할 수 없을 때까지 계속 반복한다.

DFS는 스택 또는 재귀 호출을 이용하여 구현할 수 있으며, 그래프의 모든 노드를 방문하고 싶을 때, 경로 탐색을 해야할 때 주로 사용된다.

import java.util.*;

class Graph {
    private int numOfNodes;  // 노드의 수를 저장
    private LinkedList<Integer> adjListArray[];  // 인접 리스트 배열

    // 생성자
    Graph(int numOfNodes) {
        this.numOfNodes = numOfNodes;  // 노드의 수 설정
        // 배열의 크기를 노드의 수로 설정
        adjListArray = new LinkedList[numOfNodes];

        // 각 노드마다 인접 노드를 저장할 리스트 생성
        for (int i = 0; i < numOfNodes; i++) {
            adjListArray[i] = new LinkedList<>();
        }
    }

    // 무방향 그래프에 간선 추가
    void addEdge(int src, int dest) {
        // src에서 dest로의 간선 추가
        adjListArray[src].add(dest);
        // dest에서 src로의 간선 추가
        adjListArray[dest].add(src);
    }

    // 노드 u에서 시작하는 그래프의 DFS를 실행하는 함수
    void DFSUtil(int node, boolean[] visited) {
        // 현재 노드를 방문했다고 표시하고 노드 출력
        visited[node] = true;
        System.out.print(node + " ");

        // 이 정점과 인접한 모든 정점에 대해 재귀적으로 탐색
        Iterator<Integer> iterator = adjListArray[node].listIterator();
        while (iterator.hasNext()) {
            int n = iterator.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    // DFS 순회를 수행하는 함수. 재귀적인 DFSUtil()을 사용함.
    void DFS(int startNode) {
        // 모든 정점을 방문하지 않았다고 표시
        boolean[] visited = new boolean[numOfNodes];

        // 재귀적 도우미 함수를 호출하여 모든 정점에서 DFS 순회를 출력
        DFSUtil(startNode, visited);
    }
}

public class Main {
    public static void main(String args[]) {
        Graph graph = new Graph(5);  // 5개의 노드를 가진 그래프 생성
        graph.addEdge(0, 1);  // 노드 0과 1 사이에 간선 추가
        graph.addEdge(0, 4);  // 노드 0과 4 사이에 간선 추가
        graph.addEdge(1, 2);  // 노드 1과 2 사이에 간선 추가
        graph.addEdge(1, 3);  // 노드 1과 3 사이에 간선 추가
        graph.addEdge(1, 4);  // 노드 1과 4 사이에 간선 추가
        graph.addEdge(2, 3);  // 노드 2와 3 사이에 간선 추가
        graph.addEdge(3, 4);  // 노드 3과 4 사이에 간선 추가

        System.out.println("DFS traversal of the graph starting from node 0: ");
        graph.DFS(0);  // 노드 0에서 시작하는 그래프의 DFS 순회 시작
    }
}

DFS는 그래프의 모든 노드를 방문하는 알고리즘 중 하나로, 현재 정점에서 가능한 한 깊숙이 들어가서 노드를 방문한 후, 더 이상 방문할 노드가 없을 때 이전 노드로 돌아가 다음 노드를 방문하는 방식을 취한다. 이러한 방식은 스택의 LIFO(Last In First Out) 원칙을 따르는데, 이는 재귀 함수의 호출 스택으로 쉽게 구현할 수 있다.

위 코드에서는 Graph 클래스 내에 DFSUtil 메소드를 통해 실제 DFS 알고리즘이 구현되어 있다. DFSUtil 메소드는 인접 노드를 찾아서 아직 방문하지 않은 노드를 재귀적으로 탐색한다. DFS 메소드에서는 방문 여부를 저장하는 boolean 배열 **visited**를 초기화하고 시작 노드를 지정하여 DFS를 시작한다.

이 예제에서 그래프는 다음과 같이 구성된다.

  0
 / \\
1---4
| \\ |
|  \\|
2---3

그래프에 대해 DFS 함수를 호출하면 노드 **0**에서 시작하는 DFS 탐색 결과를 콘솔에 출력하게 됩니다. 출력된 결과는 DFS 탐색 순서에 따른 노드 번호이다.

예를 들어, 아래와 같은 그래프가 있다고 가정하면

  A
 / \\
B---C
| \\ |
|  \\|
D---E

이 그래프에 DFS를 적용한다면 다음과 같은 순서로 노드를 방문하게 된다.

1. 먼저 시작 노드인 **A**를 방문한다. (방문 노드: A)
2. **A**에 인접한 노드 중 하나인 B를 방문한다. (A -> B)
3. 다음으로 **B**에 인접한 노드 중 하나인 C를 방문한다. (A -> B -> C)
4. **C**에 인접한 노드 중 **A**와 **B**는 이미 방문한 상태이므로 E를 방문한다.(A -> B -> C -> E)
5. **E**에 인접한 노드 중 **B**와 **C**는 이미 방문했으므로 D를 방문한다. (A -> B -> C -> E -> D)
6. 모든 노드를 방문했으므로 탐색을 종료한다.

위와 같이 깊이를 우선적으로 탐색하게 되면, 처음 시작 노드에서 가장 멀리 있는 노드를 먼저 방문하게 된다. DFS는 이와 같은 특성 때문에 미로 찾기, 경로 탐색 등에서 많이 활용된다.

왜... \을 쓰면 \\로 기록될까요....ㅠㅠㅠ

동적 계획법 (Dynamic Programming, DP)은 복잡한 문제를 작은 하위 문제들로 나누어 풀고, 그 결과를 저장해 재사용하여 주어진 문제를 최적화하는 방법이다.

이는 '분할 정복' 알고리즘의 기본적인 원리를 따르지만, 동적 계획법은 각 하위 문제들이 중첩되어 있는 경우에 특히 효과적이다. 그래서, 동적 계획법은 공통의 하위 문제들을 여러 번 다시 풀지 않도록 이를 메모이제이션 (memoization)하여, 알고리즘의 계산 효율성을 대폭 향상시킨다.

동적 계획법은 일반적으로 두 가지 기본 단계를 거친다.

1. 하향식 접근법(Top-down): 문제를 하위 문제로 나눈다. 만약 하위 문제가 이미 해결되었다면, 저장된 결과를 사용한다. 아니라면, 문제를 해결하고 결과를 저장한다.
2. 상향식 접근법(Bottom-up): 가장 작은 하위 문제부터 시작하여, 작은 하위 문제들의 해결을 바탕으로 큰 문제의 해결책을 구성해 나간다.

동적 계획법은 최단 경로 문제, 0-1 배낭 문제, 피보나치 수열 등 다양한 문제에 적용될 수 있다. 그러나 동적 계획법이 모든 최적화 문제에 효과적인 것은 아니다. '최적 부분 구조(Optimal Substructure)'와 '중복된 하위 문제(Overlapping Subproblems)' 조건을 만족하는 문제에 대해서만 동적 계획법을 적용할 수 있다.

public class Main {
    public static long fib(int n) {
        long[] dp = new long[n+1];
        dp[0] = 0;
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(fib(10)); // 10 번째 피보나치 수를 출력
    }
}

dp라는 이름의 long형 배열은 메모이제이션을 위한 저장 공간으로 사용된다. 각 n에 대한 피보나치 결과가 이 배열에 저장된다. 이미 계산된 결과를 재사용할 수 있게 되어 중복 계산을 피하고 효율성을 높일 수 있다.

큐(Queue)는 컴퓨터 과학에서 사용되는 기본적인 자료 구조 중 하나이다. 큐는 '선입선출'(FIFO, First-In-First-Out) 원칙을 따르는 것으로 알려져 있다. 즉, 큐에 먼저 들어간 항목이 먼저 나오게 된다. 이는 실생활에서 줄을 서는 것과 비슷한 개념이다.

큐에서는 주로 다음 네 가지 기본 연산이 사용된다.

1. Enqueue: 큐의 뒤쪽에 항목을 추가한다.
2. Dequeue: 큐의 앞쪽에 있는 항목을 제거하고 반환한다. 이 연산을 수행하면, 큐에서 항목이 제거된다.
3. Front: 큐의 앞쪽에 있는 항목을 확인한다.
4. IsEmpty: 큐가 비어 있는지 확인한다.

큐는 다양한 분야에서 사용된다. 예를 들어, 운영 체제에서는 프로세스 스케줄링에 큐를 사용하고, 네트워크에서 패킷 전송을 위한 버퍼로서 큐를 사용한다. 또한, 너비 우선 탐색(BFS)와 같은 알고리즘에서도 큐는 핵심적인 역할을 한다.

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        queue.add(1);
        queue.add(2);
        queue.add(3);
        System.out.println("Queue: " + queue);

        int removedElement = queue.remove();
        System.out.println("Dequeued element: " + removedElement);
        System.out.println("Queue after dequeue operation: " + queue);

        int frontElement = queue.peek();
        System.out.println("Front element: " + frontElement);
        System.out.println("Queue after peek operation: " + queue);

        boolean isEmpty = queue.isEmpty();
        System.out.println("Is queue empty? " + isEmpty);
    }
}

Integer 타입의 Queue 객체를 생성하고, add 메소드를 사용하여 큐에 원소를 추가하고, remove 메소드를 사용하여 가장 앞의 원소를 제거하고, peek 메소드를 사용하여 가장 앞의 원소를 확인하며, isEmpty 메소드를 사용하여 큐가 비어 있는지 확인한다.