[Algorithm] Combination - 조합

개요

---

알고리즘 문제를 풀면서 대진표를 짜는 문제를 마주한적이 있었는데 무작정 중첩 for문을 돌렸던 기억이 있다. 당연히 코드는 엉망이 되었고 문제도 겨우겨우 풀어서 제출했었는데 이번에 조합을 구하는 문제를 풀어보면서 조합을 구하는 알고리즘을 제대로 정리해야겠다는 생각이 들었다. 재귀를 이용한 조합 알고리즘을 이해하고 언제든 활용할 수 있도록 정리해보도록 하자

 

 

Combination 구하기

---

• 조합은 nCr에 대한 내용만 이해하고 있다면 재귀를 이용해 손쉽게 구현할 수 있다. 코드상으로 조합의 대상이되는 n의 크기를 가진 배열과 깊이 r의 재귀를 이용해 nCr, n개의 원소 중 r개를 중복없이 선택하는 조합을 만들 수 있다. 
• A, B, C, D, E 5개의 팀이 있다고 할때, 모든 팀이 다른팀과 1번씩 만나는 대진표를 만들어보자. 대진은 총 5C2, 10가지가 나올 것이고 대진의 순서를 정한다면 10*개의 경우의수가 나올것이다. 아래 자료구조를 이용해서 모든 경우의 수를 구해보자.

//팀 정보를 가지고 있는 배열
char[] teams = {"A", "B", "C", "D", "E"};

//대진 확정 정보 기록을 위한 배열
boolean[] vis = new boolean[teams.length];

//대진 정보를 가질 클래스
class Bracket {
    private char team1;
    private char team2;
    
    public Bracket(char team1, char team2) {
        this.team1 = team1;
        this.team2 = team2;
    }
    
    public char getTeam1() {
        return team1;
    }
    public char getTeam2() {
        return team2;
    }
}

//모든 대진 정보를 저장할 자료구조
List<Bracket> brackets = new ArrayList<>();

 

• 필요한 자료구조를 모두 선언했으니 Combination을 수행하는 함수를 만들어보자. nCr에서 현재까지 몇개의 팀을 선택했는지에 대한 정보를 담고있는 변수 r과 중복 대진을 방지하기 위한 sIdx를 매개변수로 받도록 선언했다.

public void combination(int r, int sIdx) {}

 

• 조합을 구하기위한 모든 준비가 끝났다. combination 내부 로직과 함께 실제 코드를 작성해보자. 우선, 재귀를 이용할 것이기 때문에 종료를 위한 조건문이 필요하다. r을 이용할 것인데 처음 재귀에 들어갈때 2를 넣고 r을 감소시키며 0이 될때 재귀를 종료하도록 했다.또한, 종료 시점에 vis를 탐색한 뒤 Braket을 생성해서 모든 대진 정보를 담는 brakets에 넣어준다.

public void combination(int r, int sIdx) {
    if(r == 0) {
        brackets.add(createBracket());
        return;
    }
}

public Bracket createBracket() {
    String bracket = "";
    for(int i=0; i<vis.length; i++) {
        if(vis[i]) bracket += teams[i];
    }
    return new Bracket(bracket.charAt(0), bracket.charAt(1));
}

 

• 마지막으로, 재귀를 구현하면 combination 함수가 완성된다. 반복문의 시작 index가 sIdx인것은 A, B팀 대진이 이미 brakets에 추가되었는데 B, A팀 대진이 다시 추가되는 것을 방지하기 위해서이다.

public void combination(int r, int sIdx) {
    if(r == 0) {
        brackets.add(createBracket());
        return;
    }

    for(int i=sIdx; i<teams.length; i++) {
        vis[i] = true;
        combination(r-1, i+1);
        vis[i] = false;
    }
}

public Bracket createBracket() {
    String bracket = "";
    for(int i=0; i<vis.length; i++) {
        if(vis[i]) bracket += teams[i];
    }
    return new Bracket(bracket.charAt(0), bracket.charAt(1));
}

 

 

• 알고리즘이라고 하면 대표적으로 이름이 있는, 유명한 알고리즘을 살펴보기 바빴는데 요즘 들어 낮은 레벨의 알고리즘 문제를 풀면서 이런 조합 알고리즘도 매우 중요하다고 생각이 든다. 기본기가 많이 잡히는 느낌. 아래는 앞에서 구현한 팀 대진 조합의 전체 코드와 결과이다.

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

public class Main {
    private char[] teams = {'A', 'B', 'C', 'D', 'E'};
    private boolean[] vis = new boolean[teams.length];
    private final List<Bracket> brackets = new ArrayList<>();

    public void solution() {
        combination(2, 0);
    }

    public void combination(int r, int sIdx) {
        if(r == 0) {
            brackets.add(createBracket());
            return;
        }

        for(int i=sIdx; i<teams.length; i++) {
            vis[i] = true;
            combination(r-1, i+1);
            vis[i] = false;
        }
    }

    public Bracket createBracket() {
        String bracket = "";
        for(int i=0; i<vis.length; i++) {
            if(vis[i]) bracket += teams[i];
        }
        return new Bracket(bracket.charAt(0), bracket.charAt(1));
    }
}

class Bracket {
    private char team1;
    private char team2;

    public Bracket(char team1, char team2) {
        this.team1 = team1;
        this.team2 = team2;
    }

    public char getTeam1() {
        return team1;
    }
    public char getTeam2() {
        return team2;
    }
}

 

 

[ 참고자료 ]

https://loosie.tistory.com/286

[알고리즘] 순열, 조합 알고리즘 정리 (Java)