서론
백준 N과 M 시리즈 문제를 풀면서 순열과 조합이 너무 헷갈려서 간단하게 정리하고자 글을 작성했다.
조합
- 조합은 순서가 상관없는 모임을 의미하고, 순서가 상관 없기 때문에 {1, 2, 3}, {1, 3, 2}, {2, 1, 3} 모두 같은 결과로 취급한다.
- 순서가 상관없기 때문에 1, 2, 3 이라는 3개의 숫자로 이루어져있다는 점에서 똑같은 취급을 하는 것이다.
재귀로 조합 구현하기
재귀로 조합을 구현할 때, 시작점을 정한 후 그 전의 요소는 다시는 쳐다보지 않는 것이 중요하다.
4개 중에서 2개를 뽑는다는 가정 하에 예제를 보면
{1, 2, 3, 4} 4개의 숫자 중에서 순서와 상관없이 2개의 숫자를 뽑는 것이다.
대략적으로 결과를 적어보면 아래와 같은 결과가 나타난다.
1 2
1 3
1 4
2 3
2 4
3 4여기서 중요한 점은 위에서 언급한대로 시작점을 정한 후 그 전 요소는 다시는 쳐다보지 않는다는 것이다.
쉽게 설명해보면
처음 시작점이 1인 경우 {1, 2}, {1, 3}, {1, 4}까지 쭉 나오고 이 다음에 시작점이 2가 될 것이다.
{2, 3}, {2, 4}를 보면 시작점이 2가 되는 순간 1은 쳐다도 보지 않고 심지어 1은 어디에도 포함되어 있지 않다.
왜냐하면 1이 들어가는 순간 이미 선택해놓은 조합이 존재하기 때문이다.
더 쉽게 풀어쓰면
시작점이 1인 경우 {1, 2}, {1, 3}, {1, 4}이고
시작점이 2인 경우 {2, 1}, {2, 3}, {2, 4} 나올 수 있는 조합이다.
여기서 굵게 표시한 {1, 2}, {2, 1}은 조합 관점에서 서로 같은 결과이다. 이러한 이유로 조합은 시작점이 정해지면 그 전 요소는 다시는 쳐다보지 않는다라는 말이 나올 수 있는 것이다.
문제 풀기
이를 바탕으로 N과 M(2) 문제를 풀어보자
N과 M 시리즈를 풀다보면 만나는 문제이다. 입출력 예시를 봤을 때, 이 문제는 조합으로 충분히 풀 수 있는 문제이다.
하지면 이 문제에서 중요한 건 시작점이다.
조합은 시작점을 정한 후 그 전 요소는 쳐다보지 않기 때문이다.
그래서 시작점을 정할 start 변수를 선언하고 이를 이용하여 조합을 풀어날 것이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static int[] selected;
static boolean[] visited;
static StringBuilder sb = new StringBuilder();
public static void rec_func(int depth) {
if (depth == M + 1) {
for (int i = 1; i <= M; i++) {
sb.append(selected[i]).append(" ");
}
sb.append("\n");
} else {
int start = selected[depth - 1];
if (start == 0) {
start = 1;
}
for (int i = start; i <= N; i++) {
if (!visited[i]) {
selected[depth] = i;
visited[i] = true;
rec_func(depth + 1);
selected[depth] = 0;
visited[i] = false;
}
}
}
}
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 + 1];
visited = new boolean[N + 1];
rec_func(1);
System.out.println(sb);
}
}순열
- 순열은 주어진 수열에서 순서에 따라 결과가 달라지는 방식을 순열이라고 한다.
- 말 그대로, 순서가 존재하는 열 이라는 뜻
- 순열에서 {1, 2, 3}과 {1, 3, 2}, {2, 1, 3}은 모두 순서가 다르기 때문에 다른 결과로 가져올 수 있다.
재귀로 순열 구현하기
순열과 조합의 차이는 순서의 유무이다.
조합에는 순서가 없기 때문에, 시작점을 두고 그 이전의 요소를 쳐다보지 않았지만, 순열에는 순서가 보장되어야 하기 때문에 이전 요소를 다 확인해야한다.
조합은 {1, 2} == {2, 1} 이므로 시작점이 2가 되면 더 작은 요소인 1은 쳐다 보지 않았다면
순열은 {1, 2} != {2, 1} 이므로 시작점이 2가 되어도 더 작은 요소인 1을 쳐다 보게 된다.
이를 바탕으로 N과 M(1) 문제를 풀어보자
조합과는 다르게 이 문제는 시작점을 신경써주지 않아도 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* n과 m 중복 없이 순서대로 출력 (순열)
*/
public class BOJ_15649_1 {
static int N, M;
static int[] selected;
static boolean[] visited;
static StringBuilder sb = new StringBuilder();
private static void rec_func(int depth) {
if (depth == M + 1) {
for (int i = 1; i <= M; i++) {
sb.append(selected[i]).append(" ");
}
sb.append("\n");
} else {
for (int i = 1; i <= N; i++) {
if (!visited[i]) {
visited[i] = true;
selected[depth] = i;
rec_func(depth + 1);
visited[i] = false;
}
}
}
}
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 + 1];
visited = new boolean[N + 1];
rec_func(1);
System.out.println(sb);
}
}
