[Argorithm]조합

📝개요

DP의 기본 조합에 대해 알아보자!!

📝조합 

조합은 주어진 요소들 중에서 특정 개수만큼을 선택하는 문제를 말한다.
조합은 수학적 원리를 기반으로 다양한 알고리즘적 접근 방식을 통해 해결한다!!

조합

• 조합은 주어진 집에서 순서와 상관없이 특정 개수의 원소를 선택하는 방법이다.
• 예를 들어, 집합 {1,2,3}에서 2개를 선택하는 조합은 {1, 2}, {1, 3}, {2, 3}이다.

조합의 수

• 주어진 집합의 원소의 수가 N일때, 그 중에서 K개를 선택하는 경우의 수는 C(N,K)라 표기한다.

📌순열과의 차이?

조합의 수는 순열의 계산식과 매우 유사하나 1가지 다른 특징이있다.

• 분모에 K!를 곱한다.

이는 조합의 특징에 있다. 조합은 순서 상관없이 경우의 수를 구하기 때문에 K!를 이용해서 중복되는 것들을 제거한다.!!

 

📌조합과 백트레킹

그렇다면 조합의 순서 상관없는 경우를 어떻게 제거할까??

• 백트래킹(backtracking)
  • 문제를 해결하기 위해 가능한 모든 경우를 탐색하면서 조건에 맞지 않는 경우에는 되돌아가는 기법

이 방법을 사용하면 조합 문제를 해결하는데 매우 효과적일 수 있다.

백트래킹은 다음 방식으로 접근한다.

1.  현재 상태 확인 : 현재 선택된 원소들이 조건을 만족하는지 확인
2.  재귀 호출 : 현재 상태에서 가능한 모든 다음 원소를 호출
3.  되돌아가기 : 현재 상태에서 가능한 모든 선택을 한 후 다음 선택을 위해 상태를 되돌림

 

📝문제 풀어보기

N과 M (2) 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

84724

63174

44596

73.898%

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1 복사

3 1

예제 출력 1 복사

1
2
3

예제 입력 2 복사

4 2

예제 출력 2 복사

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

예제 입력 3 복사

4 4

예제 출력 3 복사

1 2 3 4

 

 

해당 문제는 전형적인 조합 + 백트래킹 문제이다.

• 조합 : 순서에 상관없이 N개의 수열 중 M개를 골라 출력

import java.io.*;
import java.util.*;

public class Main {
    static int N, M; // N: 전체 숫자의 범위 (1부터 N까지), M: 조합에서 선택할 숫자의 개수
    static int[] selected; // 현재 조합을 저장할 배열
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 전체 숫자의 범위
        M = Integer.parseInt(st.nextToken()); // 조합에서 선택할 숫자의 개수
        
        selected = new int[M]; // 선택된 숫자를 저장할 배열 초기화
        generateCombinations(1, 0); // 조합 생성을 시작합니다. start는 1부터 시작하고, depth는 0부터 시작
    }
    
    // 조합을 생성하는 함수
    // start: 현재 조합을 생성할 때 시작할 숫자
    // depth: 현재 조합의 깊이 (선택한 숫자의 개수)
    static void generateCombinations(int start, int depth) {
        // 현재 조합이 M개 숫자를 모두 선택했으면 결과를 출력합니다
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                System.out.print(selected[i] + " "); // 선택된 숫자 출력
            }
            System.out.println(); // 한 조합 출력 후 줄 바꿈
            return;
        }
        
        // start부터 N까지의 숫자를 사용하여 조합을 생성
        for (int i = start; i <= N; i++) {
            selected[depth] = i; // 현재 깊이에 i를 선택
            generateCombinations(i + 1, depth + 1); // 다음 숫자와 깊이로 재귀 호출
            // 백트래킹: 다음 조합을 위해 현재 선택한 숫자 i를 제거하고 다음 숫자를 시도합니다
        }
    }
}