[알고리즘] 기초 알고리즘 공부하기 -1 (알고리즘 종류)

알고리즘 종류 간략하게 정리하기

 

1. 정렬 알고리즘 

 - Quick Sort / Merge Sort / Heap Sort / Selection Sort / Bubble Sort

 

EX. Quick Sort 

 - 시간복잡도 : O(n log n)

 - 대량 데이터 정렬할 때 사용

 - 재귀적으로 피벗을 기준으로 왼쪽과 오른쪽 부분을 나누어 정렬

import java.util.Arrays;

public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) return;

        int pivot = arr[(left + right) / 2];
        int index = partition(arr, left, right, pivot);
        quickSort(arr, left, index - 1);
        quickSort(arr, index, right);
    }

    private static int partition(int[] arr, int left, int right, int pivot) {
        while (left <= right) {
            while (arr[left] < pivot) left++;
            while (arr[right] > pivot) right--;
            if (left <= right) {
                int temp = arr[left];
                arr[left] = arr[right];

 

2. 탐색 알고리즘

 - Binary Search, Linear Search

 

EX. Binary Search

 - 평균 시간복잡도 : O(log n)

 - 정렬된 배열에서 특정값 찾을 때 사용

 - 중간값과 비교하며 탐색 범위를 반으로 줄임

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

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        System.out.println(binarySearch(arr, 4));
    }
}

 

3. 그리디 알고리즘

 - 부분해가 최적의 해가 될 수 있다는 가정으로 진행하는 알고리즘.

   -> 쉽게 말해서 매 단계 별 최선의 선택을 한다면 전체 결과로써도 최선일때 사용 가능하다. 

 - 예를들어 동전 거스름돈을 최소 개수로 주는 방법 구하는 문제

   -> 매 단계에서 가장 큰 단위의 동전으로 거슬러 준다면 (단계별 최선의 선택) 결과적으로 전체를 봤을때 최소 동전으로 주는 방법 (전체의 최선의 선택)

import java.util.Arrays;

public class CoinChange {
    public static int minCoins(int[] coins, int amount) {
        Arrays.sort(coins);
        int count = 0;
        for (int i = coins.length - 1; i >= 0; i--) {
            count += amount / coins[i];
            amount %= coins[i];
        }
        return amount == 0 ? count : -1;
    }

    public static void main(String[] args) {
        int[] coins = {1, 5, 10, 25};
        System.out.println(minCoins(coins, 63));
    }
}

 

4. 동적 프로그래밍 (DP)

 - 이전 계산 결과를 재사용하여 최적해를 보장하며, 계산을 수행해가는 방식

 - 그리디와 유사하다고 느낄 수 있지만, 이전 계산에서 나오는 결과를 이용하는 방식이다. (재귀와 유사하나  시간 복잡도 상 DP 가 유리한 케이스가 있음)

import java.util.HashMap;
import java.util.Map;

public class Fibonacci {
    private static Map<Integer, Integer> memo = new HashMap<>();

    public static int fibonacci(int n) {
        if (n <= 1) return n;
        if (memo.containsKey(n)) return memo.get(n);

        int result = fibonacci(n - 1) + fibonacci(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(10));
    }
}

 

5. BFS / DFS (너비 우선 탐색 / 깊이 우선 탐색)

 - 시간복잡도 : O(V + E) / V는 정점 개수, E는 간선 개수

 - 탐색 문제들에 사용. 보통 BFS 문제는 DFS로도 가능하고 DFS는 BFS 로 풀 수 있으나 

   BFS는 최단 경로 찾기, 최소 이동 횟수 등에 주로 쓰이고, DFS 는 경로 탐색, 분리된 영역 감지 등 에 사용

 

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

public class MazeBFS {
    private static final int[][] DIRECTIONS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public static int bfsMaze(int[][] maze, int[] start, int[] end) {
        int rows = maze.length, cols = maze[0].length;
        boolean[][] visited = new boolean[rows][cols];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{start[0], start[1], 0});
        visited[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int x = cell[0], y = cell[1], dist = cell[2];

            if (x == end[0] && y == end[1]) return dist;

            for (int[] dir : DIRECTIONS) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && ny >= 0 && nx < rows && ny < cols && maze[nx][ny] == 1 && !visited[nx][ny]) {
                    queue.add(new int[]{nx, ny, dist + 1});
                    visited[nx][ny] = true;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[][] maze = {
                {1, 0, 1, 1, 1},
                {1, 1, 1, 0, 1},
                {0, 0, 0, 1, 1},
                {1, 1, 1, 1, 0},
                {1, 0, 1, 1, 1}
        };
        System.out.println(bfsMaze(maze, new int[]{0, 0}, new int[]{4, 4}));
    }
}

 

6. 백트래킹 

- 가능한 모든 경우의 수를 탐색하며, 만약 해당 경우의 수가 조건에 맞지 않으면 뒤돌아 가는 방식

- 주로 재귀를 사용하여 구현. 배치가 불가능한 경우를 조기에 걸러야 함

import java.util.ArrayList;
import java.util.List;

public class NQueen {
    public static List<int[]> nQueens(int n) {
        List<int[]> solutions = new ArrayList<>();
        int[] board = new int[n];
        solveNQueens(n, 0, board, solutions);
        return solutions;
    }

    private static void solveNQueens(int n, int row, int[] board, List<int[]> solutions) {
        if (row == n) {
            solutions.add(board.clone());
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isSafe(row, col, board)) {
                board[row] = col;
                solveNQueens(n, row + 1, board, solutions);
                board[row] = -1;
            }
        }
    }

    private static boolean isSafe(int row, int col, int[] board) {
        for (int i = 0; i < row; i++) {
            if (board[i] == col || Math.abs(board[i] - col) == row - i) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        List<int[]> solutions = nQueens(4);
        for (int[] solution : solutions) {
            for (int col : solution) {
                System.out.print(col + " ");
            }
            System.out.println();
        }
    }
}