C - [백준 6603] 로또 (feat. 백트래킹)

참조 포스트

2025.01.02 - [Computer Science/알고리즘 문제] - C - [백준 1759] 암호 만들기

C - [백준 1759] 암호 만들기 (feat. 백트래킹 + DFS)

2025.01.06 - [Computer Science/알고리즘 문제] - C - [백준 14888] 연산자 끼워넣기

C - [백준 14888] 연산자 끼워넣기 (feat. 백트래킹 + DFS)

 

 

 

https://www.acmicpc.net/problem/6603

BOJ_6603 로또 

이 문제는 조합(Combination)과 백트래킹(Backtracking)을 사용하며, 주어진 숫자 배열에서 6개의 숫자를 선택하는 모든 조합을 출력하는 문제입니다. 조합을 생성하기 위해 백트래킹(Backtracking)을 사용하며, 출력 순서를 유지하기 위해 배열을 오름차순 정렬합니다.

 

예를 들어, 입력이 다음과 같다면:

7 1 2 3 4 5 6 7

출력은 다음과 같습니다:

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
2 3 4 5 6 7

여기서 숫자 집합의 첫 번째 값은 숫자 개수를 나타내며, 이후 숫자는 선택 가능한 숫자입니다. 입력은 0이 주어질 때 종료됩니다.

---

Checkpoint

 

백트래킹으로 조합을 구하는 알고리즘 설계를 연습할 수 있는 좋은 문제 입니다. 그 전에 N과 M, 암호만들기 등 백트래킹의 문제를 풀 때 "연속적 상황에서 경우의 수 구하기" 가 백트래킹의 기본 동작 원리라고 생각하여, 순서나 경로에 따른 백트래킹 설계에 필수적인 줄 알았습니다. 

하지만 소문난 칠공주(1941) 문제의 알고리즘 설계에 실패하면서, 학습 중 누락된 내용이 있다는 것을 인식하게 되었고, 해당 문제를 접하면서 백트래킹에 대한 정의를 다시 잡을 수 있을 뿐더러, 제 알고리즘 설계 능력에 조합이라는 키워드를 추가할 수 있게 되었습니다.

 

백트래킹은 모든 경우의 수를 탐색한다 + 그래프(트리)간의 level 이동이 가능하다 라는 특징이 있습니다.

 

• 모든 경우의 수를 탐색한다 == 조합을 생성한다.
• 그래프(트리) 간의 level 이동이 가능하다 == 연속성, 방향성 등에 관한 configuration을 설계한다.

상단의 두 목록은 현재 머리 속에 정리되어있는 백트래킹의 핵심 내용입니다. 주목할 것은 2번째에 해당하는 "level 이동이 가능하다" 인데, 이는 포스트를 추가적으로 기재하여 내용을 보충해볼까합니다.

 

 

---

해결 방법

1. 조합 개념 활용

• 조합은 n개의 숫자 중 r개를 고르는 경우의 수입니다. 여기서는 r = 6이며, 주어진 숫자 집합에서 가능한 모든 조합을 구해야 합니다.

2. 백트래킹을 사용한 구현

• 백트래킹은 모든 경우를 탐색하면서 조건에 맞지 않으면 탐색을 중단하는 기법입니다. 이 문제에서는 조합을 구할 때 이미 6개의 숫자를 선택했으면 탐색을 멈춥니다.

3. 입력과 출력

• 입력은 여러 줄로 주어질 수 있으며, 각 줄은 하나의 숫자 집합을 나타냅니다.
• 출력은 각 숫자 집합에 대해 가능한 조합을 한 줄씩 출력하며, 각 테스트 케이스 사이에는 빈 줄을 추가합니다.

---

1.  

구현 코드

/*
BOJ_6603_로또
https://www.acmicpc.net/problem/6603
*/

#include <stdio.h>
#include <stdlib.h>
int arry[13];
int N = 0;
int com[6];

int compare(const void *a, const void *b)    // 오름차순 비교 함수 구현
{
    int num1 = *(int *)a;    // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴
    int num2 = *(int *)b;    // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴

    if (num1 < num2)    // a가 b보다 작을 때는
        return -1;      // -1 반환
    
    if (num1 > num2)    // a가 b보다 클 때는
        return 1;       // 1 반환
    
    return 0;    // a와 b가 같을 때는 0 반환
}


void combination(int depth, int idx){
    if(depth == 6){
        for(int i = 0; i < 6; i ++){
            printf("%d ", com[i]);
        }
        printf("\n");
        return;
    }

    for(int i = idx; i < N; i ++){
        com[depth] = arry[i];
        combination(depth + 1, i + 1);
    }
    
}


int main() {
    while(1){
        scanf("%d", &N);
        if(N == 0){
            break;
        }
        for(int i = 0; i < N; i ++){
            scanf("%d", &arry[i]);
        }
        // 오름차순
        // 정렬할 배열, 요소 개수, 요소 크기, 비교 함수를 넣어줌
        qsort(arry, N, sizeof(int), compare);
        // 조합
        combination(0, 0);
        printf("\n");
        
    }
    
    return 0;
}

 

코드 구성 요소

1. 전역 변수 및 함수 선언

int arry[13];  // 입력받은 숫자들을 저장하는 배열 (최대 12개의 숫자)
int N = 0;     // 입력된 숫자의 개수
int com[6];    // 선택된 조합을 저장하는 배열

• arry: 입력받은 숫자들을 저장합니다.
• com: 현재 선택된 6개의 숫자를 저장합니다.

---

2. 정렬 함수 (compare)

int compare(const void *a, const void *b) {
    int num1 = *(int *)a;
    int num2 = *(int *)b;

    if (num1 < num2)
        return -1;
    if (num1 > num2)
        return 1;
    return 0;
}

• 목적: 숫자 배열 arry를 오름차순으로 정렬합니다.
• qsort 함수에 전달되어 숫자를 정렬하는 비교 함수로 사용됩니다.

---

3. 조합 생성 함수 (combination)

void combination(int depth, int idx) {
    if (depth == 6) {
        for (int i = 0; i < 6; i++) {
            printf("%d ", com[i]);
        }
        printf("\n");
        return;
    }

    for (int i = idx; i < N; i++) {
        com[depth] = arry[i];  // 현재 숫자를 선택
        combination(depth + 1, i + 1);  // 다음 숫자 선택
    }
}

• 매개변수:
  • depth: 현재 선택된 숫자의 개수
  • idx: 숫자를 선택할 시작 위치
• 기능:
  1. depth == 6인 경우, com 배열의 내용을 출력합니다.
  2. 반복문을 통해 arry[idx]부터 시작하여 숫자를 선택하며 재귀 호출합니다.
  3. i + 1을 사용하여 다음 호출에서 중복되지 않게 선택 범위를 좁힙니다.

---

4. main 함수

int main() {
    while (1) {
        scanf("%d", &N);  // 숫자 개수 입력
        if (N == 0) {
            break;  // 입력이 0이면 종료
        }

        for (int i = 0; i < N; i++) {
            scanf("%d", &arry[i]);  // 숫자 입력
        }

        qsort(arry, N, sizeof(int), compare);  // 숫자 배열 정렬
        combination(0, 0);  // 조합 생성 시작
        printf("\n");  // 테스트 케이스 간 빈 줄 추가
    }

    return 0;
}

• 입력:
  1. N을 통해 숫자 개수를 입력받습니다.
  2. 숫자 배열 arry를 채웁니다.
• 정렬:
  • qsort를 사용하여 숫자 배열을 오름차순으로 정렬합니다.
• 조합 생성:
  • combination(0, 0)을 호출하여 조합 생성을 시작합니다.
• 출력:
  • 각 테스트 케이스가 끝날 때마다 빈 줄을 출력합니다.

---

코드 흐름

1. 입력받기:
   • 숫자 개수 N과 숫자 배열 arry를 입력받습니다.
2. 정렬:
   • qsort로 배열을 정렬하여 출력 순서를 유지합니다.
3. 조합 생성:
   • combination 함수로 가능한 모든 6개의 숫자 조합을 출력합니다.
4. 반복:
   • 입력이 0이 될 때까지 위 과정을 반복합니다.

---

출력 예시

입력:

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

출력:

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
2 3 4 5 6 7

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
...

 

---

주요 개념

1. 정렬 (qsort):
   • 정렬을 통해 조합 결과가 항상 오름차순으로 출력됩니다.
2. 조합:
   • depth와 idx를 활용하여 중복 없이 숫자를 선택합니다.
3. 백트래킹:
   • 조건(depth == 6)에 도달하면 조합을 출력하고, 탐색을 종료합니다.

---

시간 복잡도

1. 정렬:
   • qsort의 시간 복잡도는 O(N \log N)입니다.
2. 조합 탐색:
   • 조합의 개수는 C(N,6))이며, 이는 O(N6)에 가까운 탐색이 이뤄집니다.

최악의 경우 N=12일 때도 충분히 실행 가능한 범위입니다.

 

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.