주요 알고리즘

1. 정렬(Sorting)

: 정렬은 가장 기본적인 알고리즘 문제 중 하나입니다. 다양한 정렬 알고리즘을 이해하고, 그 특성과 시간 복잡도를 고려하는 것이 중요합니다.

주요 알고리즘:
- 버블 정렬(Bubble Sort): 인접한 두 값을 비교하여 정렬하는 단순한 방법입니다. 시간 복잡도: O(n^2).
- 선택 정렬(Selection Sort): 배열에서 가장 작은 값을 찾아서 교환하는 방식입니다. 시간 복잡도: O(n^2).
- 삽입 정렬(Insertion Sort): 이미 정렬된 부분에 새로운 값을 삽입하여 정렬하는 방식입니다. 시간 복잡도: O(n^2).
- 퀵 정렬(Quick Sort): 분할 정복 알고리즘을 사용하여 데이터를 정렬합니다. 평균 시간 복잡도: O(n log n).
- 병합 정렬(Merge Sort): 분할 후 병합하여 정렬하는 알고리즘입니다. 시간 복잡도: O(n log n).
- 힙 정렬(Heap Sort): 힙을 이용한 정렬 방법입니다. 시간 복잡도: O(n log n).

 

활용 예시:
- 리스트나 배열을 오름차순 또는 내림차순으로 정렬하는 문제.
- 두 배열 병합하기 (정렬된 상태로).

 

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Partitioning index
            int pi = partition(arr, low, high);
            
            // Recursively sort elements before and after partition
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                // Swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // Swap arr[i + 1] and arr[high]
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        
        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        int n = arr.length;
        quickSort(arr, 0, n - 1);
        
        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

 

2. 탐색(Searching)

: 탐색 알고리즘은 주어진 데이터에서 원하는 값을 찾는 문제입니다.

주요 알고리즘:
- 선형 탐색(Linear Search): 배열을 처음부터 끝까지 탐색합니다. 시간 복잡도: O(n).
- 이진 탐색(Binary Search): 정렬된 배열에서 반으로 나누어 값을 찾는 방법입니다. 시간 복잡도: O(log n).

활용 예시:
- 정렬된 배열에서 특정 값을 찾는 문제.
- 이진 탐색 트리(BST)에서의 탐색.

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            if (arr[mid] == target) {
                return mid;  // Target found
            }
            
            if (arr[mid] < target) {
                low = mid + 1;  // Search the right half
            } else {
                high = mid - 1;  // Search the left half
            }
        }
        
        return -1;  // Target not found
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13};
        int target = 7;
        int result = binarySearch(arr, target);
        
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found");
        }
    }
}

3. 그래프 알고리즘(Graph Algorithms)

: 그래프는 노드와 엣지로 구성된 데이터 구조입니다. 그래프 알고리즘은 주로 경로 탐색이나 연결성을 확인하는 데 사용됩니다.

주요 알고리즘:
- 깊이 우선 탐색(DFS, Depth-First Search): 가능한 한 깊게 탐색한 후, 더 이상 탐색할 수 없으면 백트래킹하는 방식입니다.
- 너비 우선 탐색(BFS, Breadth-First Search): 인접한 노드를 먼저 탐색하고, 그 다음으로 멀리 떨어진 노드를 탐색하는 방식입니다.
- 다익스트라 알고리즘(Dijkstra's Algorithm): 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘입니다.
- 플로이드-워셜(Floyd-Warshall Algorithm): 모든 노드 쌍에 대해 최단 경로를 구하는 알고리즘입니다.
- 최소 신장 트리(MST, Minimum Spanning Tree): 크루스칼(Kruskal), 프림(Prim) 알고리즘을 사용해 최소 신장 트리를 찾는 방법입니다.

활용 예시:
- 최단 경로 문제 (두 지점 사이의 최단 거리 구하기).
- 연결 요소 찾기 (그래프의 연결된 부분들).
- 가장 짧은 경로를 찾는 문제 (다익스트라, 벨만-포드).

import java.util.*;

public class BFS {
    static class Graph {
        int vertices;
        LinkedList<Integer>[] adjList;

        Graph(int vertices) {
            this.vertices = vertices;
            adjList = new LinkedList[vertices];
            for (int i = 0; i < vertices; i++) {
                adjList[i] = new LinkedList<>();
            }
        }

        void addEdge(int v, int w) {
            adjList[v].add(w);
        }

        void BFS(int start) {
            boolean[] visited = new boolean[vertices];
            Queue<Integer> queue = new LinkedList<>();
            
            visited[start] = true;
            queue.add(start);

            while (!queue.isEmpty()) {
                int vertex = queue.poll();
                System.out.print(vertex + " ");
                
                for (int neighbor : adjList[vertex]) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        queue.add(neighbor);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        
        System.out.println("Breadth-First Search starting from vertex 0:");
        graph.BFS(0);
    }
}

 

4. 동적 프로그래밍(Dynamic Programming)

: 동적 프로그래밍은 하위 문제를 해결한 결과를 저장해 두고 이를 재사용하는 알고리즘입니다. 보통 최적화 문제에서 많이 사용됩니다.

주요 알고리즘:
- 피보나치 수열(Fibonacci Sequence): 재귀적으로 계산하는 방법을 동적 프로그래밍으로 최적화합니다.
- 배낭 문제(Knapsack Problem): 제한된 용량 내에서 가장 큰 가치를 가지는 아이템을 선택하는 문제입니다.
- 최대 부분 수열(Sum Subsequence): 연속된 부분 배열의 합이 최대인 값을 구하는 문제.
- 최단 경로 문제: 벨만-포드 알고리즘 등.

활용 예시:
- 최대 부분합을 구하는 문제.
- 배낭 문제와 같이 제한된 조건 내에서 최적화하는 문제.

public class Fibonacci {
    public static int fibonacci(int 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];
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci of " + n + " is: " + fibonacci(n));
    }
}

 

5. 분할 정복(Divide and Conquer)

: 분할 정복은 문제를 작은 부분 문제로 나누어 해결하고, 그 해결책을 합쳐서 최종 결과를 도출하는 방식입니다.

주요 알고리즘:
- 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort): 데이터를 분할한 후, 정렬한 결과를 병합합니다.
- 스트라이센 알고리즘(Strassen's Matrix Multiplication): 행렬을 분할하여 빠르게 곱하는 알고리즘입니다.

활용 예시:
- 병합 정렬 및 퀵 정렬 문제.
- 큰 행렬 곱셈 문제 등.

public class MergeSort {
    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        for (int i = 0; i < n1; i++) {
            leftArr[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            rightArr[j] = arr[mid + 1 + j];
        }

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k] = leftArr[i];
                i++;
            } else {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = leftArr[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }

    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        int n = arr.length;

        mergeSort(arr, 0, n - 1);

        System.out.println("Sorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

6. 그리디 알고리즘(Greedy Algorithm)

: 그리디 알고리즘은 각 단계에서 최선의 선택을 하는 방법입니다. 하지만, 전체 문제에서 최적의 해를 보장하지는 않습니다.

주요 알고리즘:
- 동전 교환 문제: 최소 동전 개수로 특정 금액을 만드는 문제.
- 프림 알고리즘(Prim's Algorithm): 최소 신장 트리(MST)를 구하는 알고리즘.
- 최대-최소 값 문제: 그리디 방식으로 해결할 수 있는 문제들.

활용 예시:
- 최소 동전 교환 문제.
- 활동 선택 문제(최대 활동을 선택하기).

import java.util.*;

public class CoinChange {
    public static int minCoins(int[] coins, int amount) {
        Arrays.sort(coins); // Sorting coins in ascending order
        int count = 0;
        
        for (int i = coins.length - 1; i >= 0; i--) {
            while (amount >= coins[i]) {
                amount -= coins[i];
                count++;
            }
        }
        
        return count;
    }

    public static void main(String[] args) {
        int[] coins = {1, 5, 10, 25};  // Coin denominations
        int amount = 63;
        
        System.out.println("Minimum coins required: " + minCoins(coins, amount));
    }
}

 

7. 백트래킹(Backtracking)

백트래킹은 가능한 모든 경우의 수를 탐색하여 조건에 맞는 해를 찾는 방식입니다.

주요 알고리즘:
- N-Queens 문제: N개의 퀸을 N×N 체스판에 배치할 때, 서로 공격하지 않도록 배치하는 문제.
- 부분 집합 구하기: 가능한 부분 집합을 모두 구하는 문제.

활용 예시:
- 퍼즐 문제 (스도쿠 해결, N-Queens 문제).
- 부분 집합 생성.

public class NQueens {
    static int N = 4;
    
    public static boolean isSafe(int[][] board, int row, int col) {
        for (int i = 0; i < col; i++) {
            if (board[row][i] == 1) {
                return false;  // Check row
            }
        }
        
        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 1) {
                return false;  // Check upper diagonal
            }
        }
        
        for (int i = row, j = col; j >= 0 && i < N; i++, j--) {
            if (board[i][j] == 1) {
                return false;  // Check lower diagonal
            }
        }
        
        return true;
    }

    public static boolean solveNQueens(int[][] board, int col) {
        if (col >= N) {
            return true;
        }

        for (int i = 0; i < N; i++) {
            if (isSafe(board, i, col)) {
                board[i][col] = 1;
                if (solveNQueens(board, col + 1)) {
                    return true;
                }
                board[i][col] = 0;  // Backtrack
            }
        }

        return false;
    }

    public static void printBoard(int[][] board) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] board = new int[N][N];
        
        if (solveNQueens(board, 0)) {
            printBoard(board);
        } else {
            System.out.println("Solution does not exist");
        }
    }
}

 

8. 슬라이딩 윈도우(Sliding Window)

슬라이딩 윈도우는 배열이나 문자열에서 연속된 부분을 효율적으로 탐색하는 알고리즘입니다.

주요 알고리즘:
- 최대 합 부분 배열: 슬라이딩 윈도우를 사용하여 부분 배열을 탐색하면서 최적화합니다.
- 문자열 패턴 매칭: 연속된 부분에서 특정 패턴을 찾는 문제.

활용 예시:
- 최대 연속 부분 합 문제.
- 문자열 내 부분 문자열 문제.

public class SlidingWindow {
    public static int maxSum(int[] arr, int k) {
        int n = arr.length;
        int maxSum = 0, windowSum = 0;
        
        // Calculate sum of first

 

9. 문자열 알고리즘(String Algorithms)

문자열 처리 문제는 주로 문자열 검색, 문자열 비교 등에 관한 문제입니다.

주요 알고리즘:
- KMP 알고리즘: 문자열 내에서 특정 패턴을 효율적으로 찾는 알고리즘.
- 트라이(Trie) 자료구조: 문자열 검색을 빠르게 하기 위한 자료구조.
- 라빈-카프(Rabin-Karp): 문자열 해시를 이용한 검색 알고리즘.

활용 예시:
- 문자열 검색.
- 중복 문자 찾기.

 

public class KMP {
    public static int[] computeLPSArray(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];
        int len = 0;
        int i = 1;

        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    public static void KMPSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] lps = computeLPSArray(pattern);

        int i = 0;  // index for text[]
        int j = 0;  // index for pattern[]

        while (i < n) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }

            if (j == m) {
                System.out.println("Pattern found at index " + (i - j));
                j = lps[j - 1];
            } else if (i < n && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
    }

    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        KMPSearch(text, pattern);
    }
}