자바 코딩테스트 강좌, 조합 알아보기

1. 서론

프로그래밍 알고리즘과 데이터 구조는 현대의 소프트웨어 개발에서 매우 중요한 역할을 합니다.
코딩 테스트의 주요 부분 중 하나는 조합(combination) 문제입니다.
여기에 대한 이해는 알고리즘적으로 문제를 해결하는 데 필요한 기초를 제공합니다.
이 글에서는 조합의 개념, 자바로 이 문제를 해결하는 방법, 그리고 예제 문제 풀이 과정을 상세히 설명하겠습니다.

2. 조합이란?

조합은 N개의 객체 중에서 R개를 선택하는 방법의 수를 의미합니다.
일반적으로 조합은 순서에 관계없이 선택된 객체의 집합을 나타냅니다.
예를 들어, {A, B, C}라는 세 개의 객체가 있을 때 이 중 두 개를 선택할 수 있는 조합은 다음과 같습니다:

{A, B}
{A, C}
{B, C}

조합의 수는 다음의 수학적 공식을 사용하여 계산합니다:

C(N, R) = N! / (R! * (N – R)!)

이 공식에서 N은 객체의 총 수, R은 선택할 객체의 수, “!”는 팩토리얼을 의미합니다.

3. 문제 정의

이번 글에서 풀어볼 문제는 다음과 같습니다:

N개의 정수가 주어질 때, K개를 선택하여 만들 수 있는 모든 조합을 출력하시오.
입력의 순서는 고려하지 않는다.

4. 문제 해결 접근법

이 문제는 재귀(recursion)를 활용하여 해결할 수 있습니다.
선택과 비선택의 경우를 나누어 조합을 생성하는 방식입니다.
다음은 이 문제를 해결하기 위한 알고리즘의 기본 매커니즘입니다:

조합을 만들기 위한 배열을 선언합니다.
재귀 함수를 정의하여 조합을 생성합니다.
기저 조건을 설정하여 재귀 호출을 종료합니다.
조합이 완성되면 결과를 출력합니다.

이러한 방식은 모든 조합을 생성하기 위해 각 숫자에 대해 선택과 비선택을 반복적으로 수행하게 됩니다.

5. 자바 코드 구현


import java.util.ArrayList;
import java.util.List;

public class Combination {
    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5}; // 조합을 생성할 숫자 배열
        int K = 3; // 선택할 개수
        List> result = new ArrayList<>(); // 결과를 저장할 리스트
        generateCombinations(numbers, K, 0, new ArrayList(), result);
        
        // 결과 출력
        for (List combination : result) {
            System.out.println(combination);
        }
    }

    // 조합을 생성하는 재귀 함수
    private static void generateCombinations(int[] numbers, int K, int start, List combination, List> result) {
        // 기저 조건: 선택한 개수가 K개가 되면 결과에 추가
        if (combination.size() == K) {
            result.add(new ArrayList<>(combination));
            return;
        }

        // 조합 생성
        for (int i = start; i < numbers.length; i++) {
            combination.add(numbers[i]); // 선택
            generateCombinations(numbers, K, i + 1, combination, result); // 재귀 호출
            combination.remove(combination.size() - 1); // 선택 해제
        }
    }
}

위 코드는 재귀를 통해 조합을 만들고 결과를 출력하는 방식을 보여줍니다.
`generateCombinations` 함수는 현재 숫자의 인덱스를 시작점으로 하여 조합을 생성합니다.
이때, 선택된 숫자는 `combination` 리스트에 추가되고, K개의 숫자를 선택하면 결과에 추가됩니다.

6. 시간 복잡도 분석

조합 문제의 시간 복잡도는 O(C(N, K))입니다.
여기서 C(N, K)는 N개의 객체 중 K개를 선택하는 조합의 수를 나타냅니다.
재귀 호출의 깊이는 K가 되는데, 이는 K개를 선택하기 위해서 발생하는 호출의 수와 관련이 있습니다.
따라서 N이 커질수록 조합의 수는 급격히 증가합니다.
실질적으로, 조합을 계산하는데 들어가는 시간은 특히 K가 N의 절반에 가까운 경우 매우 커질 수 있습니다.

7. 결론

조합 문제는 알고리즘 문제에서 자주 출제되며, 다양한 변형이 존재합니다.
본 칼럼에서는 조합의 개념과 자바를 통한 구현 방법을 배웠습니다.
알고리즘적으로 조합의 구조를 이해하게 되면, 보다 복잡한 문제도 쉽게 해결할 수 있습니다.
조합 문제를 푸는 연습을 통해 코딩 테스트에서 좋은 결과를 기원합니다!