블로그를 이전하였습니다. 2023년 11월부터 https://bluemiv.github.io/에서 블로그를 운영하려고 합니다. 앞으로 해당 블로그의 댓글은 읽지 못할 수 도 있으니 양해바랍니다.
반응형
1. 순열
[1, 2, 3]의 순열은 [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] 이다.
이처럼 같은 원소가 중복되지 않고, 조합하여 나올 수 있는 모든 경우의 집합을 뜻한다.
재귀와 스택을 이용해서 순열을 생성하는 코드를 작성한다.
2. 코드
아래 2가지 자료구조를 사용한다.
Stack<Integer> stack: 원소를 담을 스택boolean[] chosen: 이미 포함한 원소를 구분하기 위한 불리안 배열
<java />
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();
}
}
}
2.1. 전체 코드
<java />
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();
}
}
}
}
2.1.1. 실행결과
<html />[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]
3. 순열 문제 풀기
2020/04/03 - [Algorithm/Beakjoon] - 백준 Ex.15649번 - N과 M(1) 순열 문제 (with Python3)
백준 Ex.15649번 - N과 M(1) 순열 문제 (with Python3)
본 문제는 백준 알고리즘(https://www.acmicpc.net/)에게 있습니다. 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서..
memostack.tistory.com
2020/04/03 - [Algorithm/Beakjoon] - 백준 Ex.15650 - N과 M(2) - 순열 (with Python3)
백준 Ex.15650 - N과 M(2) - 순열 (with Python3)
본 문제는 백준 알고리즘(https://www.acmicpc.net/)에게 있습니다. 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서..
memostack.tistory.com
반응형
'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 |
