[알고리즘] 백트래킹을 이용한 순열/조합 및 알고리즘 성능 분석(Big-O, Omega, Theta)

1. 백트래킹(Backtracking)으로 순열과 조합 구하기

순열 (Permutation)

• 순열은 n개의 서로 다른 원소를 모든 가능한 순서로 나열한 것을 의미
• 총 경우의 수는 n! (팩토리얼) 임
• 예를 들어 {1, 2, 3} 세 개의 숫자로 만들 수 있는 모든 순열은 다음과 같음

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

• 모든 순열은 백트래킹이라는 알고리즘 기법으로 생성할 수 있음
• 해결책을 찾는 과정에서 더 이상 진행할 수 없을 때, 이전 단계로 돌아가 다른 가능성을 탐색하는 방법임

백트래킹 아이디어:

• path 배열: 지금까지 선택한 원소들을 저장
• used 배열:
  - 특정 원소를 이미 사용했는지 여부를 표시
  - 이를 통해 중복 선택을 방지
• 탐색 과정:
  - 아직 사용하지 않은 원소를 하나 선택해 path에 추가하고, 다음 원소를 선택하기 위해 재귀적으로 함수를 호출
• 완성 조건: path의 길이가 n이 되면 하나의 순열이 완성

탐색 트리 예시 (n=3)

- 아래 그림은 {1, 2, 3}으로 순열을 생성하는 과정을 트리 구조로 나타낸 것임
- 루트에서 시작하여 각 깊이에서 사용하지 않은 숫자를 선택해 내려가며, 리프 노드에 도달하면 하나의 순열이 완성

C 코드 예시

#include <stdio.h>
#define N 3 // 원소 개수 [cite: 39, 40]

int nums[N] = {1, 2, 3}; [cite: 41, 44]
int used[N] = {0}; // 사용 여부 체크 배열 (0으로 초기화) [cite: 42, 43]
int path[N]; // 현재 순열을 저장하는 배열 [cite: 45]

void backtrack(int depth) {
    // 깊이가 N에 도달하면 하나의 순열이 완성됨
    if (depth == N) { [cite: 47]
        // path에 저장된 순열 출력
        for (int i = 0; i < N; i++) { [cite: 51, 52, 53]
            printf("%d ", path[i]); [cite: 54, 55]
        }
        printf("\n"); [cite: 57]
        return; [cite: 58]
    }

    // 모든 원소를 순회
    for (int i = 0; i < N; i++) { [cite: 59]
        // 아직 사용하지 않은 원소라면
        if (!used[i]) { [cite: 60]
            used[i] = 1; // 사용했다고 표시 [cite: 62]
            path[depth] = nums[i]; // 경로에 추가 [cite: 66]
            backtrack(depth + 1); // 다음 깊이로 재귀 호출 [cite: 67]
            used[i] = 0; // 되돌리기 (가장 중요!). 다음 탐색을 위해 사용 여부를 초기화 [cite: 68, 69, 70]
        }
    }
}

int main() {
    backtrack(0); [cite: 73]
    return 0; [cite: 74]
}

 

출력 결과

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 

---

조합 (Combination)

• n개의 원소 중에서 순서를 고려하지 않고 k개를 선택하는 것
• 예를 들어 {1, 2, 3, 4}에서 2개를 뽑는 조합은 다음과 같음

1, 2
1, 3
1, 4
2, 3
2, 4
3, 4

• {1, 2}와 {2, 1}은 순열에서는 다른 경우지만 조합에서는 같은 경우로 취급

백트래킹 아이디어:

- 조합에서는 순서가 중요하지 않으므로, 오름차순으로만 원소를 선택하도록 하여 중복을 피함

- 예를 들어, 1 다음에는 1보다 큰 2, 3, 4만 올 수 있도록 제한하는 방식

• used 배열 대신, 재귀 호출 시 **다음 탐색을 시작할 인덱스(start)**를 넘겨줌
• for문은 start 인덱스부터 시작하여 이전에 선택한 원소보다 작은 값은 고려하지 않음

C 코드 예시

#include <stdio.h>

#define N 4 // 전체 원소 개수 [cite: 93, 94]
#define K 2 // 뽑을 원소 개수 [cite: 96, 97]

int nums[N] = {1, 2, 3, 4}; [cite: 95]
int path[100]; // 선택한 원소를 저장하는 배열 [cite: 98]

void backtrack(int start, int depth) {
    // K개의 원소를 모두 뽑았으면 조합 완성
    if (depth == K) { [cite: 100]
        // path에 저장된 조합 출력
        for (int i = 0; i < K; i++) { [cite: 102]
            printf("%d ", path[i]); [cite: 103]
        }
        printf("\n"); [cite: 105]
        return; [cite: 106]
    }

    // start 인덱스부터 순회하여 다음 원소 선택
    for (int i = start; i < N; i++) { [cite: 111]
        path[depth] = nums[i]; // 경로에 현재 원소 추가
        // 다음 원소는 현재 위치(i) 다음부터 탐색하도록 i+1을 넘김
        backtrack(i + 1, depth + 1); [cite: 114]
        // backtrack(i + 1, depth + 1); ➡️ backtrack(i, depth + 1)로 변경시 중복을 허용하는 순열임
    }
}

int main() {
    printf("n=%d, k=%d 조합 결과: \n", N, K); [cite: 117]
    backtrack(0, 0); // 인덱스 0, 깊이 0부터 탐색 시작 [cite: 121]
    return 0; [cite: 118]
}

---

2. 알고리즘 성능 분석: Big-O, Omega, Theta

- 알고리즘의 효율성을 표현하기 위해 점근 표기법을 사용

- 이는 입력 크기(n)가 커질 때 실행 시간이 어떻게 변하는지를 나타냄

주요 점근 표기법

• O(g(n)) (Big-O):
  - 상한(Upper Bound)을 나타냄
   - 알고리즘의 실행 시간이 최악의 경우에도 $g(n)$보다 빠르거나 같다는 것을 의미
  - "아무리 늦어도 이 정도 시간 안에는 끝난다"는 의미
• Ω(g(n)) (Big-Omega):
  - 하한(Lower Bound)을 나타냄
  - 알고리즘의 실행 시간이 최상의 경우에도 최소한 $g(n)$만큼은 걸린다는 것을 의미
  - "아무리 빨라도 이 시간보다는 오래 걸린다"는 의미
• Θ(g(n)) (Theta):
  - 상한과 하한이 동일할 때 사용
  - 알고리즘의 실행 시간이 항상 $g(n)$과 유사한 증가율을 가짐을 의미
  - "알고리즘의 실행 시간은 대략 이 정도다"라는 가장 정밀한 표현

표기법 (Asymptotic Form)	관계 (Relationship)	의미
f(n)∈O(g(n))	f(n)≤g(n)	$f(n)$의 증가율은 $g(n)$보다 작거나 같다. (상한)
f(n)∈Ω(g(n))	f(n)≥g(n)	$f(n)$의 증가율은 $g(n)$보다 크거나 같다. (하한)
f(n)∈Θ(g(n))	f(n)≡g(n)	$f(n)$의 증가율은 $g(n)$과 같다. (평균)
f(n)∈o(g(n))	f(n)<g(n)	$f(n)$의 증가율은 $g(n)$보다 명백히 작다. (등호 제외)
f(n)∈ω(g(n))	f(n)>g(n)	$f(n)$의 증가율은 $g(n)$보다 명백히 크다. (등호 제외)

시간 복잡도 증가율 순서

• 일반적으로 함수의 증가율은 다음 순서를 따름

- logan<nb<cn (단, b>0,c>1)

• 이는 로그 함수가 다항 함수보다, 다항 함수가 지수 함수보다 느리게 증가한다는 것을 의미
• 알고리즘 선택 시 중요한 기준이 됨