[LG U+ 유레카 4기] WEEK 03 - 알고리즘 (4)

Soohwan Lim·2026년 4월 20일
algorithm멀티캠퍼스부트캠프부트캠프유레카4기

유레카부트캠프

목록 보기
12/31
post-thumbnail

완전 탐색, 순열(Permutation)

1. 오늘의 학습 흐름

  • 지난 주 자료구조 복습, 재귀 마무리
  • 완전 탐색(Brute-Force) 개요
  • 순열 구현 4단계: for문 중복순열 → for문 순열 → 재귀 순열 → visited 최적화
  • 문제 풀이: BOJ 15649, SWEA 규영이와 인영이의 카드게임
  • BitMask (boolean 배열 대체)

2. 완전 탐색 (Brute-Force)

탐색할 수 있는 모든 상황을 전부 시도하여 정답을 찾는 알고리즘이다.

선형 자료에서의 완전 탐색은 Sequential Search로, 배열의 처음부터 끝까지 모두 찾아보는 방식이다. 시간 복잡도는 O(N)이다.

경우의 수를 따지는 문제들은 크게 세 가지다.

  • 순열: 순서가 있는 선택 (nPr)
  • 조합: 순서가 없는 선택 (nCr)
  • 부분집합: 포함/비포함 여부

이것들을 구현하는 방법이 DFS, BackTracking이다. 비선형 자료(Tree, Graph)를 탐색하는 방법으로는 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)가 있다.

완전 탐색
├── Sequential Search (선형)
└── 경우의 수 (순열/조합/부분집합)
    └── DFS = BackTracking ← 오늘 핵심
        └── Best First Search (우선순위 기반 탐색)

3. 순열 구현 4단계

1단계 - for문 중복 순열 (n³)

3개의 원소에서 3개를 뽑는 경우를 단순 for문으로 구현하면, 같은 원소가 중복으로 선택되는 중복 순열이 된다.

int[] data = {1, 2, 3};
int N = data.length;
int cnt = 0;

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        for (int k = 0; k < N; k++) {
            cnt++;
            System.out.printf("%d %d %d%n", data[i], data[j], data[k]);
        }
    }
}
// 경우의 수: N³ = 27

2단계 - for문 순열 (중복 제거)

같은 인덱스를 두 번 쓰지 않도록 조건을 추가하면 순열이 된다.

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if (i != j) {                      // i와 j가 다를 때만
            for (int k = 0; k < N; k++) {
                if (k != i && k != j) {    // k가 i, j와 다를 때만
                    cnt++;
                    System.out.printf("%d %d %d%n", data[i], data[j], data[k]);
                }
            }
        }
    }
}
// 경우의 수: N! = 6

시간복잡도는 여전히 N³이지만, 실제 출력되는 경우의 수는 N!이다.

문제는 N이 커지거나 뽑는 개수(r)가 달라지면 for문을 그만큼 중첩해야 한다는 거다. r=5면 for문 5개를 중첩해야 한다. 이걸 재귀로 해결한다.

3단계 - 재귀 중복 순열 nTTr (Permutation1)

for문의 각 단계를 재귀 호출로 대체한다. depth가 R에 도달하면 하나의 순열 완성이다.

static int N, R;
static int[] input;
static int[] numbers;  // 뽑은 순열 저장

public static void permutation(int depth) {
    if (depth == R) {              // 기저 조건: R개 다 뽑았으면
        System.out.println(Arrays.toString(numbers));
        return;
    }
    for (int i = 0; i < N; i++) {
        numbers[depth] = input[i];
        permutation(depth + 1);    // 다음 자리 선택
    }
}
// 시간복잡도: O(N^R) - 중복 허용
// 9TT8: 154ms (안전) / 9TT9: 1400ms (위험)

아직 중복 제거가 없어서 같은 원소를 여러 번 선택하는 중복 순열이다.

Permutation2 - 재귀에서 중복 제거 (label 활용)

이미 뽑은 원소인지 numbers 배열을 뒤져서 확인하는 방법이다.

public static void permutation(int depth) {
    if (depth == R) {
        tc++;
        return;
    }
    top:
    for (int i = 0; i < input.length; i++) {
        for (int j = 0; j < depth; j++) {
            if (numbers[j] == input[i]) continue top;  // 이미 선택된 원소면 skip
        }
        numbers[depth] = input[i];
        permutation(depth + 1);
    }
}

중복 제거는 되지만 매번 numbers 배열을 처음부터 순회해야 해서 비효율적이다. 이걸 visited 배열로 O(1)로 개선한다.

4단계 - visited 배열로 중복 제거 (Permutation3, 가장 중요)

visited 배열로 이미 선택된 원소를 O(1)로 확인한다. 이것이 실전에서 가장 많이 쓰는 패턴이다.

static boolean[] visited = new boolean[N];
static int[] numbers = new int[R];

public static void permutation(int depth) {
    if (depth == R) {
        tc++;
        System.out.println(Arrays.toString(numbers));
        return;
    }
    for (int i = 0; i < input.length; i++) {
        if (visited[i]) continue;      // 이미 선택된 원소면 skip (O(1))
        visited[i] = true;             // ① 선택
        numbers[depth] = input[i];
        permutation(depth + 1);        // ② 탐색
        visited[i] = false;            // ③ 선택 해제 (BackTracking 핵심!)
    }
}

세 줄이 BackTracking의 전부다.

① visited[i] = true   → 선택
② permutation(depth+1) → 탐색
③ visited[i] = false  → 선택 해제 (되돌아가기)

선택 해제가 없으면 한 번 쓴 원소를 다시는 쓸 수 없다. visited가 Permutation2의 numbers 배열 순회를 O(1)로 단축시켜줘서 훨씬 빠르다.

4. 시간복잡도 비교

방법시간복잡도경우의 수
for문 중복 순열O(N³)N³
for문 순열 (중복 제거)O(N³)N!
재귀 순열 (visited)O(N!)N!

for문 버전은 r이 고정일 때만 쓸 수 있고, 재귀 버전은 r이 바뀌어도 depth 파라미터 하나만 조절하면 된다.

5. 문제 풀이 - SWEA 규영이와 인영이의 카드게임

순열 BackTracking을 실전 문제에 바로 적용한 케이스다.

규영이 카드 9장이 주어지면 나머지 9장은 자동으로 인영이 카드가 된다. 인영이 카드의 모든 배치(순열)를 시도하면서 규영이의 승/패 횟수를 센다.

static boolean[] visited = new boolean[9];

public static void solve(int depth, int scoreQ, int scoreI) {
    if (depth == 9) {               // 9장 다 매칭되면 결과 판정
        if (scoreQ > scoreI) win++;
        else if (scoreQ < scoreI) lose++;
        return;
    }
    for (int i = 0; i < 9; i++) {
        if (!visited[i]) {
            visited[i] = true;
            int valQ = inputQ[depth]; // 규영이 depth번째 카드
            int valI = inputI[i];     // 인영이 i번째 카드
            if (valQ > valI) {
                solve(depth + 1, scoreQ + valQ + valI, scoreI);
            } else {
                solve(depth + 1, scoreQ, scoreI + valQ + valI);
            }
            visited[i] = false;
        }
    }
}

Permutation3의 구조와 완전히 동일하다. visited로 중복 방지하고, 선택-탐색-선택해제. 달라진 건 기저 조건에서 점수를 비교하는 로직뿐이다.

오늘 풀면서 느낀 부족한 점 두 가지:

  • Java I/O 처리 패턴 (BufferedReader + StringTokenizer) 손에 안 익음 → 반복 숙달 필요
  • DFS 기본 틀이 바로 안 나옴 → 아래 틀 외워두기

DFS 기본 틀

static boolean[] visited;
static int[] numbers;

static void dfs(int depth) {
    if (depth == R) {           // 기저 조건
        // 결과 처리
        return;
    }
    for (int i = 0; i < N; i++) {
        if (visited[i]) continue;
        visited[i] = true;      // 선택
        numbers[depth] = input[i];
        dfs(depth + 1);         // 탐색
        visited[i] = false;     // 선택 해제
    }
}

알고리즘 문제 I/O 기본 틀 (암기용)

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());
    // 처리
    sb.append("#").append(tc).append(" ").append(answer).append("\n");
}
System.out.print(sb);

6. BitMask - boolean 배열을 bit 연산으로 대체

정수의 이진수 표현을 자료구조로 쓰는 기법이다. 1이면 켜져있다/true/원소 있음, 0이면 꺼져있다/false/원소 없음을 의미한다.

왜 쓰는가

수행 시간: 배열 O(N) → BitMask O(1)
코드 길이: 반복문 + 다중 연산자 → bit 연산 한 줄
메모리:   원소 수만큼 배열 → 변수 하나 (int=32개, long=64개 표현)

기본 bit 연산

int bit1 = 0b10101;
int bit2 = 0b00000;
int bit3 = 0b11111;

bit1 | bit2  // OR  → 0b10101 (하나라도 1이면 1)
bit1 & bit2  // AND → 0b00000 (둘 다 1이어야 1)
bit1 | bit3  // OR  → 0b11111
bit1 & bit3  // AND → 0b10101

8 >> 1  // 오른쪽 1칸 이동 → 4  (2의 1승으로 나눈 효과)
8 << 1  // 왼쪽 1칸 이동  → 16 (2의 1승으로 곱한 효과)

4.1 공집합과 꽉찬 집합

int A = 0;           // 공집합: 모든 bit가 0
int A = (1 << N) - 1; // 꽉찬 집합: N개의 bit가 모두 1

4.2 K번째 원소 추가

A |= (1 << K);   // K번째 bit를 1로 설정
// 예: K=5 → A = 0b100000

4.3 K번째 원소 삭제

A &= ~(1 << K);  // K번째 bit를 0으로 설정
// ~(1<<K): K번째만 0이고 나머지는 모두 1인 마스크
// A와 AND하면 K번째만 0이 됨

4.4 K번째 원소 포함 여부 확인

if ((A & (1 << K)) == 0) {
    // K번째 원소 없음 (0)
}
if ((A & (1 << K)) != 0) {
    // K번째 원소 있음 (1)
}

visited 배열로 비교하면:

// boolean[] 방식
if (!visited[K]) { ... }

// BitMask 방식
if ((visited & (1 << K)) == 0) { ... }

4.5 최소 원소 찾기 (마지막 1의 위치)

int result = A & -A;  // A의 이진수에서 가장 낮은 위치의 1을 추출
// 예: 0b110100 → 0b000100 (2번째 bit)
// 펜윅 트리(Fenwick Tree) 구현에서 사용

-A는 2의 보수라서 A의 맨 오른쪽 1만 살아남는다. 지금 당장 쓸 일은 없지만 나중에 세그먼트 트리, 펜윅 트리 배울 때 나온다.

visited를 BitMask로 바꾼 순열

static int visited = 0;  // boolean[] visited 대체

public static void permutation(int depth) {
    if (depth == R) {
        System.out.println(Arrays.toString(numbers));
        return;
    }
    for (int i = 0; i < N; i++) {
        if ((visited & (1 << i)) != 0) continue;   // 이미 선택됨
        visited |= (1 << i);                         // 선택
        numbers[depth] = input[i];
        permutation(depth + 1);
        visited &= ~(1 << i);                        // 선택 해제
    }
}

7. BackTracking 개념

오늘 배운 visited 패턴이 BackTracking이다.

선택 → 탐색 → 선택 해제

선택 해제가 핵심이다. 이게 없으면 DFS(깊이 우선 탐색)이고, 선택 해제가 있어서 되돌아올 수 있으면 BackTracking이다.

BackTracking이 DFS에 "가지치기(pruning)"를 추가한 개념이다. 유망하지 않은 경로는 탐색을 중단하고 되돌아온다.

8. 핵심 정리

오늘 순열을 for문 → 재귀로 발전시키는 과정을 보면서, 재귀가 왜 필요한지 완전히 이해됐다.

for문 순열의 문제는 r이 달라질 때마다 코드를 통째로 다시 짜야 한다는 거다. r=3이면 3중 for문, r=5면 5중 for문. 재귀는 depth 파라미터 하나로 이걸 해결한다. 코드 구조 자체가 달라지지 않는다.

visited 배열의 선택-해제 패턴은 앞으로 DFS, 백트래킹 문제에서 계속 나올 거다. 지금 확실히 이해해두는 게 중요하다.

9. 키워드 정리

완전 탐색 Brute-Force Sequential Search 경우의 수 순열 조합 부분집합 DFS BFS BackTracking BitMask

10. 내일의 목표

  • 수요일 코테 준비
  • 토요일 GSAT 준비
profile
Soohwan Lim
developer
이전 포스트

[LG U+ 유레카 4기] WEEK 02 - 알고리즘 (3)

다음 포스트

[LG U+ 유레카 4기] WEEK 03 - 알고리즘 (5)

0개의 댓글