알고리즘 정리 및 예제

≣ 목차

동적 계획법 (Dynamic Programming, DP)

예제: 피보나치 수열 (Fibonacci Sequence)

 

• 문제 설명: 피보나치 수열의 n번째 숫자를 구하는 문제입니다.

• 접근 방법: DP를 사용해 재귀적으로 구하는 대신, 중복 계산을 피하고, 계산된 값을 배열에 저장해 최적화를 할 수 있습니다.

public class FibonacciDP {
    public static void main(String[] args) {
        int n = 10;
        System.out.println(fibonacci(n));  // Output: 55
    }

    public static int fibonacci(int n) {
        if (n <= 1) return n;

        int[] dp = new int[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];
    }
}

추가 예제: 최소 동전 개수 (Coin Change)

 

• 문제 설명: 주어진 금액을 만들기 위해 필요한 최소 동전 개수를 구하는 문제입니다.

• 접근 방법: DP 배열을 이용해 금액을 만들 수 있는 최소 동전 수를 기록하며 구합니다.

public class CoinChangeDP {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println(coinChange(coins, amount));  // Output: 3
    }

    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }
}

백트래킹 (Backtracking)

예제: N-Queen 문제

 

• 문제 설명: N x N 체스판 위에 N개의 퀸을 서로 공격하지 못하게 배치하는 방법을 찾는 문제입니다.

• 접근 방법: 백트래킹을 사용해 퀸을 한 줄씩 배치하고, 불가능한 경우 이전 단계로 돌아가며 해결합니다.

public class NQueens {
    private static List<List<String>> solutions = new ArrayList<>();

    public static void main(String[] args) {
        int n = 4;
        List<List<String>> result = solveNQueens(n);
        System.out.println(result);
    }

    public static List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }
        backtrack(board, 0);
        return solutions;
    }

    private static void backtrack(char[][] board, int row) {
        if (row == board.length) {
            solutions.add(construct(board));
            return;
        }

        for (int col = 0; col < board.length; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                backtrack(board, row + 1);
                board[row][col] = '.';
            }
        }
    }

    private static boolean isValid(char[][] board, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }

        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }

        for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }

        return true;
    }

    private static List<String> construct(char[][] board) {
        List<String> result = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            result.add(new String(board[i]));
        }
        return result;
    }
}

트리(Tree)

예제: 이진 트리 순회 (Binary Tree Traversal)

 

• 문제 설명: 이진 트리를 전위(pre-order), 중위(in-order), 후위(post-order) 방식으로 순회하는 방법을 구합니다.

• 접근 방법: 재귀적으로 각 순회 방법에 따라 좌, 우 노드를 탐색합니다.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

public class TreeTraversal {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        System.out.println("Pre-order: ");
        preOrder(root);  // Output: 1 2 4 5 3

        System.out.println("\nIn-order: ");
        inOrder(root);  // Output: 4 2 5 1 3

        System.out.println("\nPost-order: ");
        postOrder(root);  // Output: 4 5 2 3 1
    }

    public static void preOrder(TreeNode node) {
        if (node == null) return;
        System.out.print(node.val + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    public static void inOrder(TreeNode node) {
        if (node == null) return;
        inOrder(node.left);
        System.out.print(node.val + " ");
        inOrder(node.right);
    }

    public static void postOrder(TreeNode node) {
        if (node == null) return;
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.val + " ");
    }
}

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

예제: 그래프에서 DFS 구현

 

• 문제 설명: 주어진 그래프에서 DFS를 이용해 모든 노드를 방문하는 방법을 구합니다.

• 접근 방법: 스택 또는 재귀 호출을 사용해 깊이 우선으로 노드를 탐색합니다.

import java.util.*;

public class DFSExample {
    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(2));
        graph.put(2, Arrays.asList(0, 3));
        graph.put(3, Arrays.asList(3));

        boolean[] visited = new boolean[4];
        dfs(0, graph, visited);
    }

    public static void dfs(int node, Map<Integer, List<Integer>> graph, boolean[] visited) {
        visited[node] = true;
        System.out.print(node + " ");

        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor, graph, visited);
            }
        }
    }
}

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

예제: 그래프에서 BFS 구현

 

• 문제 설명: 주어진 그래프에서 BFS를 이용해 모든 노드를 방문하는 방법을 구합니다.

• 접근 방법: 큐(Queue)를 이용해 너비 우선으로 노드를 탐색합니다.

import java.util.*;

public class BFSExample {
    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(2));
        graph.put(2, Arrays.asList(0, 3));
        graph.put(3, Arrays.asList(3));

        bfs(0, graph);
    }

    public static void bfs(int start, Map<Integer, List<Integer>> graph) {
        boolean[] visited = new boolean[4];
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.add(start);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");

            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }
}

그리디 알고리즘 (Greedy Algorithm)

• 핵심 개념: 매 순간 가장 최적이라고 생각되는 선택을 하여 최종 해답을 구하는 방법입니다. 일반적으로 탐욕적 선택을 통해 전체 최적 해를 구할 수 있는 경우에 사용됩니다.

 

예제: 회의실 배정 문제 (Meeting Room Scheduling)

 

• 문제 설명: 여러 회의 일정이 주어졌을 때, 가장 많은 회의를 배정할 수 있는 방법을 구하는 문제입니다.

• 접근 방법: 끝나는 시간이 가장 빠른 회의를 먼저 선택하는 것이 최적입니다.

import java.util.Arrays;

public class MeetingRoomScheduling {
    public static void main(String[] args) {
        int[][] meetings = {{1, 4}, {2, 3}, {3, 5}, {7, 8}};
        System.out.println(maxMeetings(meetings));  // Output: 3
    }

    public static int maxMeetings(int[][] meetings) {
        Arrays.sort(meetings, (a, b) -> a[1] - b[1]);

        int count = 0;
        int lastEnd = 0;

        for (int[] meeting : meetings) {
            if (meeting[0] >= lastEnd) {
                count++;
                lastEnd = meeting[1];
            }
        }

        return count;
    }
}

이분 탐색 (Binary Search)

• 핵심 개념: 정렬된 배열에서 원하는 값을 반씩 나누어 탐색하여 빠르게 찾아내는 알고리즘입니다. 일반적으로 O(log n)의 시간 복잡도를 가집니다.

 

예제: 이분 탐색

 

• 문제 설명: 정렬된 배열에서 특정 값을 찾는 문제입니다.

• 접근 방법: 배열을 절반씩 나누어 찾으려는 값이 중간값보다 큰지 작은지에 따라 탐색 범위를 줄여 나갑니다.

public class BinarySearchExample {
    public static void main(String[] args) {
        int[] sortedArray = {1, 3, 5, 7, 9};
        int target = 5;
        System.out.println(binarySearch(sortedArray, target));  // Output: 2
    }

    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;  // 찾지 못했을 때
    }
}

투 포인터 (Two Pointers)

• 핵심 개념: 배열이나 리스트를 순회할 때 두 개의 포인터를 동시에 움직이면서 문제를 해결하는 방법입니다. 흔히 배열에서 합을 구하거나 구간을 찾는 문제에 사용됩니다.

 

예제: 두 수의 합 (Two Sum)

 

• 문제 설명: 정렬된 배열에서 두 수의 합이 주어진 값이 되는 경우를 찾는 문제입니다.

• 접근 방법: 두 포인터를 배열의 양 끝에서 시작하여 합을 구하고, 목표값보다 크거나 작으면 포인터를 조정합니다.

public class TwoSumTwoPointers {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 6};
        int target = 6;
        int[] result = twoSum(nums, target);
        System.out.println(result[0] + ", " + result[1]);  // Output: 1, 3
    }

    public static int[] twoSum(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left < right) {
            int sum = nums[left] + nums[right];

            if (sum == target) {
                return new int[] {left, right};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }

        return new int[] {-1, -1};  // 찾지 못했을 때
    }
}

슬라이딩 윈도우 (Sliding Window)

• 핵심 개념: 고정된 크기 또는 가변적인 크기의 창을 배열에서 움직이면서 문제를 해결하는 방법입니다. 주로 부분 배열의 최대값이나 최소값, 특정 조건을 만족하는 구간을 찾는 문제에서 많이 사용됩니다.

 

예제: 최대 부분합 (Maximum Subarray Sum of Size K)

 

• 문제 설명: 길이가 K인 부분 배열 중 가장 큰 합을 구하는 문제입니다.

• 접근 방법: 윈도우를 왼쪽에서 오른쪽으로 한 칸씩 이동시키며 합을 구합니다.

public class SlidingWindowExample {
    public static void main(String[] args) {
        int[] nums = {2, 1, 5, 1, 3, 2};
        int k = 3;
        System.out.println(maxSum(nums, k));  // Output: 9
    }

    public static int maxSum(int[] nums, int k) {
        int maxSum = 0, windowSum = 0;

        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }

        maxSum = windowSum;

        for (int i = k; i < nums.length; i++) {
            windowSum += nums[i] - nums[i - k];
            maxSum = Math.max(maxSum, windowSum);
        }

        return maxSum;
    }
}

유니온 파인드 (Union Find)

• 핵심 개념: 서로 다른 집합을 표현하고, 두 집합이 같은지를 효율적으로 판단할 수 있는 자료구조입니다. 주로 그래프에서 사이클 탐지와 연결 요소 판단에 사용됩니다.

 

예제: 섬의 개수 (Number of Islands)

 

• 문제 설명: 2D 격자에서 연결된 1들이 하나의 섬을 형성한다고 할 때, 섬의 개수를 구하는 문제입니다.

• 접근 방법: 유니온 파인드를 사용해 서로 연결된 육지를 하나의 집합으로 병합합니다.

public class UnionFindExample {
    public static void main(String[] args) {
        int[][] grid = {
            {1, 1, 0, 0},
            {1, 1, 0, 0},
            {0, 0, 1, 1},
            {0, 0, 1, 1}
        };
        System.out.println(numIslands(grid));  // Output: 2
    }

    public static int numIslands(int[][] grid) {
        if (grid == null || grid.length == 0) return 0;

        int rows = grid.length, cols = grid[0].length;
        UnionFind uf = new UnionFind(rows * cols);

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    int currentIndex = r * cols + c;

                    if (r > 0 && grid[r - 1][c] == 1) {  // 위쪽과 연결
                        uf.union(currentIndex, (r - 1) * cols + c);
                    }
                    if (c > 0 && grid[r][c - 1] == 1) {  // 왼쪽과 연결
                        uf.union(currentIndex, r * cols + (c - 1));
                    }
                }
            }
        }

        Set<Integer> uniqueIslands = new HashSet<>();
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    uniqueIslands.add(uf.find(r * cols + c));
                }
            }
        }

        return uniqueIslands.size();
    }
}

class UnionFind {
    private int[] root;

    public UnionFind(int size) {
        root = new int[size];
        for (int i = 0; i < size; i++) {
            root[i] = i;
        }
    }

    public int find(int x) {
        if (root[x] == x) {
            return x;
        }
        return root[x] = find(root[x]);  // 경로 압축
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            root[rootY] = rootX;
        }
    }
}

최단 경로 알고리즘 (Shortest Path Algorithm)

• 핵심 개념: 주어진 그래프에서 시작점부터 다른 노드까지의 최단 경로를 찾는 알고리즘입니다. 대표적인 알고리즘으로 다익스트라 알고리즘과 벨만-포드 알고리즘이 있습니다.

 

예제: 다익스트라 알고리즘 (Dijkstra’s Algorithm)

 

• 문제 설명: 가중치가 있는 그래프에서 시작점에서 다른 모든 노드까지의 최단 경로를 구하는 문제입니다.

• 접근 방법: 최소 우선순위 큐(힙)을 사용해 현재까지의 최단 경로를 업데이트합니다.

import java.util.*;

public class DijkstraExample {
    public static void main(String[] args) {
        int[][] edges = {
            {0, 1, 4}, {0, 2, 1}, {1, 3, 1}, {2, 1, 2}, {2, 3, 5}
        };
        int n = 4;
        int start = 0;
        System.out.println(Arrays.toString(dijkstra(n, edges, start)));  // Output: [0, 3, 1, 4]
    }

    public static int[] dijkstra(int n, int[][] edges, int start) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>());
        }

        for (int[] edge : edges) {
            graph.get(edge[0]).add(new int[] {edge[1], edge[2]});
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        pq.add(new int[] {start, 0});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int node = current[0];
            int currentDist = current[1];

            if (currentDist > dist[node]) continue;

            for (int[] neighbor : graph.get(node)) {
                int nextNode = neighbor[0];
                int weight = neighbor[1];

                if (currentDist + weight < dist[nextNode]) {
                    dist[nextNode] = currentDist + weight;
                    pq.add(new int[] {nextNode, dist[nextNode]});
                }
            }
        }

        return dist;
    }
}