순열과 조합 공부

2025-07-13 5 분 소요

이 글은 순열과 조합을 재귀로 구현한 것을 정리한 내용입니다.

순열과 조합을 구현할 때 트리 구조로 생각하면 구현하는데 도움을 줍니다.

순열

#include <iostream>
#include <vector>

using namespace std;

int R; // 선택한 데이터 수
vector<int> v; // 주어진 데이터 모음
vector<int> result; // 선택한 데이터 모음
int visited[4]; // 방문 체크

// 결과 출력 함수
void print() {
	cout << "[ ";
	for (int i = 0; i < result.size(); i++) {
		cout << result[i]<<" ";
	}
	cout << "]\n";
}

// dfs를 통해 순열 처리
void dfs(int level) {
	if (level == R) {
		print();
		return;
	}

	for (int i = 0; i < v.size(); i++) {
		if(!(visited[i]==0)) continue;

		visited[i] = 1;
		result[level] = v[i];
		dfs(level + 1);
		visited[i] = 0;

	}

}

int main() {

	// 주어진 데이터 초기화
	v = {1,2,3};

	// 선택할 데이터 수 입력
	R=2;
    result = vector<int>(R);

	dfs(0);

	return 0;
}

주어진 1, 2, 3 중에서 2개의 수를 선택해서 나열하는 코드입니다.
순열은 DFS 트리와 방문 체크 리스트를 사용합니다.
해당 함수의 매개변수는 트리 깊이(level)를 받습니다.
선택한 수(R)와 트리 깊이(level)가 같으면 결과를 출력하고 재귀를 종료하기 위해 리턴합니다.
for문으로 0 ~ 배열 크기-1까지 탐색합니다.
- i번 배열에 방문하지 않았다면 방문 체크합니다.
- result의 현재 깊이에 해당하는 위치에 값을 넣습니다.
- 다음 자식 노드에 방문하기 위해 재귀함수 호출합니다.
- 재귀가 종료되면 방문 체크를 해제한다.

코드 풀이 과정

다음 설명은 주어진 v = {1, 2, 3} 중에서 2개의 수를 선택해서 나열하는 과정을 보여줍니다.

sample

초기 상태

sample

f(0)을 호출하면 트리 깊이가 0이기 때문에 재귀를 진행합니다.
for문으로 0 ~ 2까지 탐색합니다.
0번 배열은 방문하지 않았기 때문에 방문체크 합니다.
result의 현재 깊이인 0번째에 주어진 수 v[0] 을 넣습니다.
다음 자식 노드에 방문하기 위해 f(level+1) 즉, f(1)를 호출합니다.

sample

f(1)을 호출하면 트리 깊이가 1이기 때문에 재귀를 진행합니다.
for문으로 0~2까지 탐색합니다.
0번 배열은 이미 방문했기 때문에 넘어갑니다.
1번 배열은 방문하지 않았기 때문에 방문체크 합니다.
result의 현재 깊이인 1번째에 주어진 수 v[1]을 넣습니다.
다음 자식 노드에 방문하기 위해 f(2)를 호출합니다.

sample

f(2)를 호출하면 트리 깊이가 2이기 때문에 재귀를 종료합니다.
result의 내용을 [1 2]로 출력합니다.
f(1)로 돌아갑니다.

sample

f(1)로 돌아오면 1번 방문 기록을 해제합니다.
2번 배열은 방문하지 않았기 때문에 방문체크 합니다.
result의 현재 깊이인 1번째에 주어진 수 v[2]을 넣습니다.
다음 자식 노드에 방문하기 위해 f(2)를 호출합니다.

sample

f(2)를 호출하면 트리 깊이가 2이기 때문에 재귀를 종료합니다.
result의 내용을 [1 3]로 출력합니다.
f(1)로 돌아갑니다.

sample

f(1)로 돌아오면 2번 방문 기록을 해제합니다.
더이상 방문할 곳이 없어서 f(0)으로 돌아갑니다.

sample

f(0)으로 돌아오면 0번 방문 기록을 해제합니다.
1번 배열은 방문하지 않았기 때문에 방문체크 합니다.
result의 현재 깊이인 0번째에 주어진 수 v[1]을 넣습니다.
다음 자식 노드에 방문하기 위해 f(1)을 호출합니다.

sample

f(1)을 호출하면 트리 깊이가 1이기 때문에 재귀를 진행합니다.
for문으로 0~2까지 탐색합니다.
0번 배열은 방문하지 않았기 때문에 방문체크 합니다.
result의 현재 깊이인 1번째에 주어진 수 v[0]을 넣습니다.
다음 자식 노드에 방문하기 위해 f(2)를 호출합니다.
이 과정을 f(0)이 더이상 방문할 수 없을 때까지 반복합니다.

조합

#include <iostream>
#include <vector>

using namespace std;

vector<int> v; // 주어진 데이터 모음
vector<int> result; // 선택한 데이터 모음
int R; // 선택한 데이터 수

// dfs를 통해 조합 처리
void dfs(int level, int idx) {
	if (level == R) {
        cout<<"[";
		for (int i=0; i < result.size(); i++) {
			cout << result[i]<<" ";
		}
		cout << "]\n";
		return;
	}

	for (int i = idx; i < v.size(); i++) {
		result[level] = v[i];
		dfs(level + 1, i + 1);

	}

}

int main() {

	// 주어진 데이터 초기화
	v = { 1,2,3};

	// 선택한 데이터 수 입력
	R=2;
	result = vector<int>(R);

	dfs(0, 0);

	return 0;
}

주어진 1, 2, 3 중에서 2개의 수를 선택하는 코드입니다.
조합은 DFS 트리를 이용해서 풀고, 트리를 탐색할 때 다음 시작점을 가지고 갑니다.
해당 함수의 매개변수는 트리 깊이(level)와 다음 시작점(idx)을 받습니다.
선택한 수(R)와 트리 깊이(level)가 같으면 결과를 출력하고 재귀를 종료하기 위해 리턴합니다.
for문으로 다음 시작점 ~ 배열 크기-1까지 탐색합니다.
- result의 현재 깊이에 해당하는 위치에 값을 넣습니다.
- 다음 자식 노드에 방문하기 위해 재귀함수 호출합니다.

코드 풀이 과정

다음 그림은 주어진 v = {1, 2, 3} 중에서 2개의 수를 선택하는 과정을 보여줍니다.

sample

초기 상태

sample

f(0,0)을 호출하면 트리 깊이가 0이기 때문에 재귀를 진행합니다.
시작점이 0이기 때문에 for문으로 0 ~ 2까지 탐색합니다.
i = 0이 됩니다.
result의 현재 깊이인 0번째에 주어진 수 v[0]을 넣습니다.
다음 자식 노드에 방문하기 위해 f(level+1, i+1) 즉, f(1,1)를 호출합니다.

sample

f(1,1)을 호출하면 트리 깊이가 1이기 때문에 재귀를 진행합니다.
시작점이 1이기 때문에 for문으로 1 ~ 2까지 탐색합니다.
i = 1이 됩니다.
result의 현재 깊이인 1번째에 주어진 수 v[1]을 넣습니다.
다음 자식 노드에 방문하기 위해 f(2,2)를 호출합니다.

sample

f(2,2)를 호출하면 트리 깊이가 2이기 때문에 재귀를 종료합니다.
result의 내용을 [1 2]로 출력합니다.
f(1,1)로 돌아갑니다.

sample

f(1,1)로 돌아오면 i = 2가 됩니다.
result의 현재 깊이인 1번째에 주어진 수 v[2]을 넣습니다.
다음 자식 노드에 방문하기 위해 f(2,3)를 호출합니다.

sample

f(2,3)를 호출하면 트리 깊이가 2이기 때문에 재귀를 종료합니다.
result의 내용을 [1 3]로 출력합니다.
f(1,1)로 돌아갑니다.

sample

f(1,1)로 돌아오면 더이상 방문할 곳이 없어서 f(0,0)로 돌아갑니다.

sample

f(0,0)로 돌아오면 i=1이 됩니다.
result의 현재 깊이인 0번째에 주어진 수 v[1]을 넣습니다.
다음 자식 노드에 방문하기 위해 f(1,2)를 호출합니다.

sample

f(1,2)를 호출하면 트리 깊이가 1이기 때문에 재귀를 진행합니다.
시작점이 2이기 때문에 for문으로 2 ~ 2까지 탐색합니다.
i = 2이 됩니다.
result의 현재 깊이인 1번째에 주어진 수 v[2]을 넣습니다.
다음 자식 노드에 방문하기 위해 f(2,3)를 호출합니다.

sample

f(2,3)를 호출하면 트리 깊이가 2이기 때문에 재귀를 종료합니다.
result의 내용을 [2 3]로 출력합니다.
f(1,2)로 돌아갑니다.
이 과정을 f(0,0)이 더이상 방문할 수 없을 때까지 반복합니다.

응용

응용1 - 다른 변수 타입 활용

vector<string> v2; // 주어진 데이터 모음 
vector<string> result2; // 선택한 데이터 모음
int R; // 선택한 데이터 수

변수 타입을 문자열로 바꿔서 사용할 수 있습니다.
다른 변수를 사용해도 응용이 가능합니다.

#include <iostream>
#include <vector>

using namespace std;

vector<string> v2; // 주어진 데이터 모음 
vector<string> result2; // 선택한 데이터 모음
int R; // 선택한 데이터 수

// dfs 함수
void dfs(int level, int idx) {
	if (level == R) {
		for (int i=0; i < result2.size(); i++) {
			cout << result2[i]<<" ";
		}
		cout << "\n";
		return;
	}

	for (int i = idx; i < v2.size(); i++) {
		result2[level] = v2[i];
		dfs(level + 1, i + 1);

	}

}

int main() {

	// 주어진 데이터 초기화
	v2 = {"aa", "bb", "cc"};

	// 선택한 데이터 수 입력
	R = 2;
	result2 = vector<string>(R);

	dfs(0, 0);

	return 0;
}

응용2 - 지도 활용

백준 14502 연구소와 같은 문제에서 연구소에 3개의 벽을 세우는 방법이 조합을 활용하는 것 입니다.
자세히 설명하면 연구소의 빈 칸 중에서 3개를 선택해서 벽을 세우는 것 입니다.

sample

그림과 같이 2차원 배열의 구조를 A, B, C, D로 구역을 나누어 생각하면 응용1과 같은 방식으로 문제를 해결할 수 있습니다.

참조

Twitter Facebook LinkedIn

Lee Jeong Beom

순열과 조합 공부

순열

코드 풀이 과정

조합

코드 풀이 과정

응용

응용1 - 다른 변수 타입 활용

응용2 - 지도 활용

참조

공유하기

참고

투 포인터 공부

C++ 소수 판별하기

데이터 타입의 범위와 시간 제한 공부

백준 7569 토마토 풀이 (BFS)