알고리즘 정리 (완전탐색)

2023년 12월 07일 TIL

기업 코테를 대비하기 위해 알고리즘을 풀고 있으나
슬슬 머리를 굴려서 솔루션을 완성하는데 부족함을 느끼고 있다.
해서 알고리즘의 종류를 공부하고 정리하기로 한다.

알고리즘 정리

• 완전 탐색법
• [] ()

완전 탐색법

완전탐색법은 모든 가능한 경우의 수를 찾아내는 알고리즘

단순 (Brute Force)

Brute Force

반복문과 조건문을 사용하여 모든 경우의 수를 전부 찾는 방식이다.

특징

• 난이도 : 일반적으로 쉬움 알고리즘 지식 없이 구현 가능
• 시간 복잡도 : 매우 비효율적 대부분의 경우 시간 복잡도가 높아 대용량 데이터나 복잡한 문제에는 비효율적일 수 있음
• 비고 : 메모리가 버텨주는 한 모든 경우의 수를 탐색 하기 때문에, 반드시 solution 을 찾을 수 있음.

예시

 > 1부터 10까지의 숫자 중, 3개를 고르는  모든 조합 출력

public class BruteForceExample {
    public static void main(String[] args) {
        for (int i = 1; i <= 10; i++) {
            for (int j = i + 1; j <= 10; j++) {
                for (int k = j + 1; k <= 10; k++) {
                    System.out.println(i + " " + j + " " + k);
                }
            }
        }
    }
}

재귀

재귀

자기 자신을 호출하여 주어진 문제를 해결하는 함수

특징

• 난이도 : 이해만 한다면 쉬움 문제에 따라 다르지만 기본적인 재귀는 쉽게 구현 가능
• 시간 복잡도 : 케바케 필요한 부분만 사용하면 괜찮지만 그렇게 효율적이진 않음.
• 비고 : 보통 피보나치 와 하노이의 탑 공부할 때 재귀를 처음 접하지만,
  피보나치를 재귀로 푸는건 비효율적

예시

 > 하노이의 탑

하노이의 탑

public class HanoiTower {
    public static void main(String[] args) {
        moveTower(3, 'A', 'B', 'C');
    }

    public static void moveTower(int disk, char from, char helper, char to) {
        if (disk == 1) {
            System.out.println("원판 1을 " + from + "에서 " + to + "로 이동");
        } else {
            moveTower(disk - 1, from, to, helper);
            System.out.println("원판 " + disk + "을 " + from + "에서 " + to + "로 이동");
            moveTower(disk - 1, helper, from, to);
        }
    }
}

순열

순열 (Permutation)

순서를 고려하여 집합의 요소들을 나열하는 방법

특징

• 난이도: 중간 - 알고리즘 구현에 조금 익숙해져야 쉽게 구현 가능
• 시간 복잡도: 케바케 - 순열의 개수가 많아질수록 시간 복잡도가 증가함
• 비고: 순서가 중요할 때 사용하며, n!의 경우의 수를 가짐

예시

 > 1부터 3까지의 숫자로 만들 수 있는 모든 순열 출력

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        permute(arr, 0); // 순열 생성 함수
    }

      // 순열 생성 재귀
    public static void permute(int[] arr, int k) {
        if (k == arr.length) {
            for (int i : arr) {
                System.out.print(i + " "); // 현재 순열
            }
            System.out.println();
        } else {
            for (int i = k; i < arr.length; i++) {
                swap(arr, i, k); // k <-> i 교환
                permute(arr, k + 1); // 다음 원소 생성 재귀
                swap(arr, i, k); // 되돌리기
            }
        }
    }

      // i <-> j 위치 스왑용
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

비트마스크

비트 마스크

비트 연산을 사용하여 여러 상태를 효율적으로 표현하고 조작하는 기법

특징

• 난이도: 중상 - 비트 연산에 대한 이해가 필요
• 시간 복잡도: 효율적 - 상태의 표현과 조작을 빠르게 할 수 있음
• 비고: 비트 연산을 이용하여, 데이터의 삽입, 삭제, 조회 등을 빠르게 수행할 수 있음

예시

 > 집합 {1, 2, 3}의 모든 부분집합 출력

    public static void main(String[] args) {
        int[] set = {1, 2, 3};
        int n = set.length;

        for (int i = 0; i < (1 << n); i++) { // 모든 부분 집합에 대한 루프
            System.out.print("{ ");
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) > 0) { // j번째 비트가 1인 경우
                    System.out.print(set[j] + " ");
                }
            }
            System.out.println("}");
        }
    }

백트래킹

백 트래킹 (Backtracking)

백 트래킹

결정 트리를 통해 모든 가능한 해를 탐색하는 동시에, 불필요한 경로는 조기에 제거하는 기법

특징

• 난이도: 중상 - 탐색 과정에서 조건 판단과 결정이 필요
• 시간 복잡도: 변수적 - 불필요한 경로를 제거함으로써 효율적인 경우가 많음
• 비고: 불가능한 경우를 조기에 감지하여 시간 낭비를 줄임

예시

 > N-Queen 문제 (N x N 체스판에 N개의 퀸을 서로 공격할 수 없게 배치)

public class NQueen {
    static int N = 4; // 퀸의 개수 및 체스판의 크기
    static int[] board = new int[N]; // 각 행에 배치된 퀸의 열 위치
    static int solutions = 0;

    public static void main(String[] args) {
        solveNQueen(0);
        System.out.println("Total solutions: " + solutions);
    }

    public static void solveNQueen(int row) {
        if (row == N) { // 모든 퀸을 배치했을 경우
            solutions++;
            return;
        }
        for (int col = 0; col < N; col++) {
            board[row] = col;
            if (isSafe(row)) { // 현재 행의 퀸이 안전한지 검사
                solveNQueen(row + 1);
            }
        }
    }

    // 현재 행의 퀸이 안전한지 검사하는 함수
    private static boolean isSafe(int row) {
        for (int i = 0; i < row; i++) {
            if (board[i] == board[row] || Math.abs(board[row] - board[i]) == Math.abs(row - i)) {
                return false; // 같은 열이나 대각선에 퀸이 존재
            }
        }
        return true;
    }
}

BFS & DFS

따로 작성