728x90 Algorithm70 [Java] 순열/조합/부분집합 💡순열(Permutation) : 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열(permutation)이라고 한다. (나무위키) //nPr public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); R = sc.nextInt(); input = new int[N]; numbers = new int[R]; isSelected = new boolean[N]; // 방문 여부를 체크하기 위함 for (int i = 0; i < N; i++) { input[i] = sc.nextInt(); } permutation(0); } private static v.. 2022. 8. 30. [Java] 조합 (Combination) 순열과 조합의 차이 뽑힌 자리 (순서의 의미 X )→ 조합 뽑힌 자리 (순서의 의미 0 )→ 순열💡 조합 nCr import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class CombinationTest { static int N, R; static int totalCnt; static int[] arr, input; // nCr: n까지의 수 중 r개를 모두 뽑아서 순서있게 나열함(1 중복체크가 필요 없어짐! arr[cnt] = input[i]; // 다음 수 뽑으러 com.. 2022. 8. 30. [Java] 순열(permutation) 순열과 조합의 차이 뽑힌 자리 (순서의 의미 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; stati.. 2022. 8. 30. [Java] BFS(Breadth First Search) 💡BFS(Breadth First Search) : 너비 우선 탐색 이라는 의미를 가진 BFS는 쉽게말해 가까운 노드부터 탐색하는 알고리즘이다. BFS구현에는 선입선출 방식인 큐 자료구조를 사용한다. 💡BFS 동작 방식 탐색 시작 노드를 큐에 삽입 후 방문처리 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입 후 방문처리 2번의 과정을 더 이상 수행할 수 없을 때까지 반복 1️⃣ 시작노드인 1을 큐에 삽입하고 방문처리함 2️⃣ 큐에서 1을 꺼내고 방문하지 않은 2, 3, 8을 모두 큐에 삽입 후 방문처리함 3️⃣ 큐에서 노드 2를 꺼낸 뒤, 방문하지 않은 인접노드 7을 큐에 삽입 후 방문처리함 4️⃣ 큐에서 노드 3을 꺼내고 방문하지 않은 인접노드인 4,5를 모두.. 2022. 8. 30. 이전 1 ··· 9 10 11 12 다음 728x90 반응형