순열에 대한 통찰
개요
안녕하세요.
오늘은 알고리즘문제에 자주 등장하는 순열문제를 재귀호출로 풀어보려 합니다.
순열은 조합과 비슷한 점이 많아 문제를 풀다 서로 혼동해 틀리는경우가 많습니다.
백준 ➡️ 단계별로 풀기 ➡️ 백트래킹 단계에 나온 2가지 순열 패턴 개념을 정리하고, 문제를 풀며 살펴보겠습니다.
순열
먼저 순열(Permutation)의 개념을 볼까요.
|
|
출처 : 나무위키 순열 |
만약 1, 2, 3이라는 3개의 원소를 갖는 집합에서,
하나의 원소만 나열하면,
(1), (2), (3) 세 가지
두개의 원소를 선택, 나열하면,
(1,2), (1, 3), (2,1), (2,3), (3,1), (3,2) 여섯가지
세 원소라면,
(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1) 여섯가지
위 수식을 활용해 정리하면,
- 3개의 원소집합 중 하나의 원소를 나열 = 3P1
- 3개의 원소집합 중 두개의 원소를 나열 = 3P2
- 3개의 원소집합 중 세개의 원소를 나열 = 3P3
참고로 0! 은 1입니다. 왜 0인지는 한번 스스로 찾아 이해해보세요.
이제 순열에 대한 통찰이 생겼다면 백준 문제풀이로 검증해 봅시다.
백준 15649
문제를 살펴보겠습니다.
|
|
출처 : 백준 15649번 문제 |
방금 배운 순열의 nPr 을 묻는 문제이군요.
n개의 집합원소에서 r개를 나열하면 정답입니다.
잘 생각해야 할 부분은, 순열의 3P1 = 3을 출력하는게 아니라 모든 원소를 나열해야
합니다.
C++ 소스코드
#include <iostream>
#include <deque>
using namespace std;
// 순열 (순서 O, 중복 X)
void permutation(deque<int>& q, int n, int r)
{
if(q.size() == r)
{
for(auto& i: q)
cout << i << ' ';
cout << '\n';
return;
}
for(int i=1; i<=n; i++)
{
if(std::find(q.begin(), q.end(), i) == q.end())
{
q.push_back(i);
permutation(q, n, r);
q.pop_back();
}
}
}
int main()
{
int n, r;
cin >> n >> r;
deque<int> q;
permutation(q, n, r);
return 0;
}
Python 소스코드
글을 다 포스팅하고 파이썬이 없으니 마음이 허전해 파이썬 코드도 추가 유첨합니다. 😮💨
(결과는 C++코드와 동일하며 코드 설명은 C++로 진행)
from collections import deque
def permutation(q, n, r):
if len(q) == r:
for i in q:
print(i, end=' ')
print()
return
for i in range(1, n+1):
if i not in q:
q.append(i)
permutation(q, n, r)
q.pop()
n, r = map(int, input().split(' '))
q = deque()
permutation(q, n, r)
3 2를 입력하면, 3P2에 대한 6가지 결과가 출력됩니다.
코드분석
1. 헤더 및 네임스페이스
#include <iostream> #include <deque> using namespace std;
#include <iostream>: 콘솔 입출력을 위한 헤더 파일입니다.
#include <deque>: 덱(deque) 자료구조를 사용하기 위한 헤더 파일입니다.
deque는 동적 배열로, 양쪽 끝에서 삽입과 삭제가 가능한 자료구조입니다.
using namespace std;: 표준 네임스페이스를 사용합니다. (std:: 생략 가능)
2. 순열 함수 선언
void permutation(deque<int>& q, int n, int r)
이 함수는 순열을 재귀적으로 구합니다.
매개변수 설명:
deque<int>& q: 현재까지 선택한 숫자들을 저장하는 덱입니다.
int n: 전체 숫자의 범위 (1부터 n까지).
int r: 뽑을 숫자의 개수.
3. 재귀의 종료 조건
if(q.size() == r)
{
for(auto& i: q)
cout << i << ' ';
cout << '\n';
return;
}
종료 조건: 만약 q의 크기가 rr과 같다면, 더 이상 숫자를 추가할 필요가 없으므로 현재의 조합을 출력하고 종료합니다.
동작:
for(auto& i: q): q에 저장된 모든 숫자를 출력합니다.
cout << '\n';: 한 조합이 끝난 뒤 줄 바꿈을 합니다.
4. 재귀 호출 및 숫자 선택
for(int i=1; i<=n; i++)
{
if(std::find(q.begin(), q.end(), i) == q.end())
{
q.push_back(i);
permutation(q, n, r);
q.pop_back();
}
}
반복문: i를 1부터 nn까지 순회하며 각 숫자를 선택합니다.
std::find(q.begin(), q.end(), i) == q.end():
현재 숫자 i가 q에 포함되어 있는지 확인합니다.
포함되지 않았다면 (== q.end()), 숫자 i를 추가합니다.
(std::find() 함수는 해당 덱의 반복자에서 i를 찾지 못하면 Iterator의 end() 를 반환, 참고로 end()는 덱의 마지막 요소가 아님 X )
q.push_back(i): 숫자 i를 덱의 끝에 추가합니다.
permutation(q, n, r): 재귀 호출을 통해 i를 선택한 상태에서 다음 숫자를 선택합니다.
q.pop_back(): 현재 숫자 ii를 제거하여 원래 상태로 복원합니다.
이를 백트래킹(Backtracking)이라고 합니다.
5. 메인 함수
int main()
{
int n, r;
cin >> n >> r;
deque<int> q;
permutation(q, n, r);
return 0;
}
입력 받기: 사용자로부터 n과 r 값을 입력받습니다.
초기화: 빈 덱 q를 생성합니다.
순열 함수 호출: permutation(q, n, r)을 호출하여 순열을 구합니다.
백준 15651
앞선 순열 문제와 차이점은 중복을 허용한다는 점입니다.
|
| 출처 : 백준 15651번 문제 |
C++ 소스코드
#include <iostream>
#include <deque>
using namespace std;
// 순열 (순서 O, 중복 O)
void permutation(deque<int>& q, int n, int r)
{
if(q.size() == r)
{
for(auto& i: q)
cout << i << ' ';
cout << '\n';
return;
}
for(int i=1; i<=n; i++)
{
q.push_back(i);
permutation(q, n, r);
q.pop_back();
}
}
int main()
{
int n, r;
cin >> n >> r;
deque<int> q;
permutation(q, n, r);
return 0;
}
중복을 허용하므로, 3P3 을 입력하면 27개의 결과가 나와야 합니다.
앞선 15649 문제 코드와 차이점은, 18번 라인의 find() 함수로 값이 있는지 여부를 체크하는 부분만 빼고 동일합니다.
이상으로 순열에 대한 설명을 마치고 다음은 조합을 다루어 보겠습니다.
감사합니다.
댓글
댓글 쓰기