View
λ°μν
μμ΄κ³Ό μ‘°ν©μ μ°¨μ΄
λ½ν μ리 (μμμ μλ―Έ 0 )β μμ΄ λ½ν μ리 (μμμ μλ―Έ X )β μ‘°ν©
π‘ μμ΄
nPr : μ¬κΈ°μ rμ 루νλ₯Ό ꡬμ±νλ κ°μκ° λλ€. κ·Έλ¬λ, rμ μκ° λ―Έμ μ΄λΌλ©΄ μ¬κ·λ‘ ꡬνν΄μΌ νλ€.
μ¬κ· κ²°μ μμΈ: λ¬λΌμ§λ μκ° λ¬΄μμΈκ°? λ½ν μκ° μ μ₯λ μ리, λ½νλ μμ λ±μ΄ μμΌνλ€!!
nPn
// 1,2,3μ ν¬ν¨νλ μμ΄μ μμ±νλ μ¬κ·ν¨μ
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class PermutationTest1 {
static int N;
static int totalCnt;
static int[] arr;
static boolean[] isSelected;
// nPn: 1λΆν° nκΉμ§μ μ μ€ n κ°λ₯Ό λͺ¨λ λ½μμ μμμκ² λμ΄ν¨
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
totalCnt = 0;
arr = new int[N];
isSelected = new boolean[N + 1]; // 0μ΄ μλ 1λΆν° μμ
permutation(0);
System.out.println("μ΄ κ²½μ°μ μ :" + totalCnt);
}
/***** μ¬κ· ν¨μ ꡬν *****/
private static void permutation(int cnt) {
if (cnt == N) {
totalCnt++;
System.out.println(Arrays.toString(arr));
return;
}
// κ°λ₯ν λͺ¨λ μμ λν΄μ νμ
for (int i = 1; i <= N; i++) {
// μλλλ μκ° μ νλμλκ°?
if (isSelected[i])// true -> μ¬μ©μ€μΈ μ
continue;
// μ¬μ©λμ§ μμ μ
arr[cnt] = i;
isSelected[i] = true;// κ·Έ μκ° μ¬μ©μ€
// λ€μ μ λ½μΌλ¬
permutation(cnt + 1);
// μ¬μ© λμλ μλ₯Ό λ€μ λλλ¦Ό
isSelected[i] = false;
}
}
}
nPr
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class PermutationTest2 {
static int N, R;
static int totalCnt;
static int[] arr, input;
static boolean[] isSelected;
// nPr: nκΉμ§μ μ μ€ rκ°λ₯Ό λͺ¨λ λ½μμ μμμκ² λμ΄ν¨(1<=r<=n)
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
totalCnt = 0;
input = new int[N];
arr = new int[R];
isSelected = new boolean[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
input[i] = Integer.parseInt(st.nextToken());
}
permutation(0);
System.out.println("μ΄ κ²½μ°μ μ :" + totalCnt);
}
private static void permutation(int cnt) {
if (cnt == R) {
totalCnt++;
System.out.println(Arrays.toString(arr));
return;
}
// κ°λ₯ν λͺ¨λ μμ λν΄μ νμ ->(input λ°°μ΄μ λͺ¨λ μλ₯Ό μλν΄μΌν¨ )
for (int i = 0; i < N; i++) {
// μλλλ μκ° μ νλμλκ°?
if (isSelected[i])// true -> μ¬μ©μ€μΈ μ
continue;
// μ¬μ©λμ§ μμ μ
arr[cnt] = input[i];
isSelected[i] = true;// κ·Έ μκ° μ¬μ©μ€
// λ€μ μ λ½μΌλ¬
permutation(cnt + 1);
// μ¬μ© λμλ μλ₯Ό λ€μ λλλ¦Ό
isSelected[i] = false;
}
}
}
λ°μν
'μκ³ λ¦¬μ¦' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[Java] BFS / DFS μΈμ 리μ€νΈμ μ¬κ· (0) | 2022.08.30 |
---|---|
[Java] μμ΄/μ‘°ν©/λΆλΆμ§ν© (0) | 2022.08.30 |
[Java] μμ΄/μ‘°ν©/λΆλΆμ§ν© (0) | 2022.08.30 |
[Java] μ‘°ν© (Combination) (0) | 2022.08.30 |
[Java] BFS(Breadth First Search) (0) | 2022.08.30 |
reply