블로그를 이전하였습니다. 2023년 11월부터 https://bluemiv.github.io/에서 블로그를 운영하려고 합니다. 앞으로 해당 블로그의 댓글은 읽지 못할 수 도 있으니 양해바랍니다.
반응형
순열
[1, 2, 3]
의 순열은 [1, 2, 3]
, [1, 3, 2]
, [2, 1, 3]
, [2, 3, 1]
, [3, 1, 2]
, [3, 2, 1]
이다.
이처럼 같은 원소가 중복되지 않고, 조합하여 나올 수 있는 모든 경우의 집합을 뜻한다.
재귀와 스택을 이용해서 순열을 생성하는 코드를 작성한다.
코드
아래 2가지 자료구조를 사용한다.
Stack<Integer> stack
: 원소를 담을 스택boolean[] chosen
: 이미 포함한 원소를 구분하기 위한 불리안 배열
private static void search(Stack<Integer> stack) {
if (stack.size() >= n) {
System.out.println(stack.toString());
} else {
for(int i=1; i<=n; i++) {
if(chosen[i]) continue; // 이미 뽑은 경우는 SKIP
chosen[i] = true; // 포함
stack.push(i);
search(stack);
chosen[i] = false; // 제외
stack.pop();
}
}
}
전체 코드
import java.util.Stack;
public class Permutation {
private static boolean[] chosen; // 뽑은 원소를 기록
private static int n;
public static void main(String[] args) {
n = 3;
chosen = new boolean[n+1];
final Stack<Integer> stack = new Stack<>();
search(stack);
}
private static void search(Stack<Integer> stack) {
if (stack.size() >= n) {
System.out.println(stack.toString());
} else {
for(int i=1; i<=n; i++) {
if(chosen[i]) continue; // 이미 뽑은 경우는 SKIP
chosen[i] = true; // 포함
stack.push(i);
search(stack);
chosen[i] = false; // 제외
stack.pop();
}
}
}
}
실행결과
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
순열 문제 풀기
2020/04/03 - [Algorithm/Beakjoon] - 백준 Ex.15649번 - N과 M(1) 순열 문제 (with Python3)
2020/04/03 - [Algorithm/Beakjoon] - 백준 Ex.15650 - N과 M(2) - 순열 (with Python3)
반응형
'Algorithm' 카테고리의 다른 글
팩토리얼 구하기 알고리즘 (with Python3) (0) | 2020.03.16 |
---|---|
집합을 이용한 중복 제거 알고리즘 (with Python3) (0) | 2020.03.16 |
Java 멱집합 구하기 (PowerSet) (0) | 2020.02.23 |
최댓값 찾기 알고리즘 (with Python3) (0) | 2020.02.19 |
알고리즘의 시간 복잡도 - 빅오(O) 표기법 (0) | 2020.02.16 |