하다보면 늘겠지

n개 중에 c개를 뽑는 가짓 수를 의미한다. import java.util.*; public class Main { //메모이제이션 사용해야 재귀가 많이 안 뻗음!!! //구한 값을 다시 안구한다! int[][] dy = new int[35][35]; public int DFS(int n, int r){ //메모이제이션!!! if(dy[n][r] > 0) return dy[n][r]; //1을 리턴하는 경우 if(n == r || r == 0) return 1; else return dy[n][r]=DFS(n-1, r-1) + DFS(n-1, r); } public static void main(String[] args) { Main T = new Main(); Scanner kb = new Scanne..

중복순열문제와는 다르게 사용 여부를 체크하는 배열이 필요하다. 그리고 1부터 N까지의 순열이 아니고 입력값 배열로 주어진다. 크게 보자면 중복순열을 방지하기위해 사용 여부 체크하는 배열만 달라졌다! 사용 여부를 체크하는 배열 - ch 출력할 숫자를 넣어놓을 배열 - pm 순열로 사용할 숫자들이 들어있는 배열 - arr import java.util.*; public class Main { static int[] pm, ch, arr; static int n, m; public void DFS(int L){ //순열의 완성 if(L == m) { for(int x : pm) System.out.print(x + " "); System.out.println(); } else { //n가닥으로 뻗어나가야 한다..

부분집합 문제와는 다르게 동전을 여러개 쓸 수 있다. 여기선 해당 인덱스의 동전을 사용한다. 라고 재귀호출 L == n 이 되면 모두 1원으로 바꾸어주는 것 ~ 5원으로 바꾸어주는 것에 대한 조합(?)들이 만들어진다. ★구해둔 동전의 갯수가 있을 때 그 갯수보다 많이 거슬러주는 부분을 찾아볼 필요가 없다. BFS가 좀 더 맞는답. 1.DFS import java.util.*; public class Main { static int n, m, answer = Integer.MAX_VALUE; //L을 동전의 갯수,sum을 L개의 동전의 총합이라 생각 public void DFS(int L, int sum, Integer[] arr) { //동전의 총합이 m보다 크면 만들 수 없음 if(sum > m) re..

이전 문제랑은 다르게 이 문제부터는 가지가 2 가닥이 아닌 여러 가닥으로(N번) 뻗는다. 출력할 숫자를 넣어놓을 배열이 필요하다. L은 숫자를 뽑는 갯수로 설정한다. import java.util.*; public class Main { static int[] pm; static int n, m; public void DFS(int L) { if(L==m) { for(int x : pm) System.out.print(x + " "); System.out.println(); } else { //2가닥이 아닌 N가닥씩 뻗어나가야함. for(int i = 1; i

이것도 부분집합 개념의 문제라고 볼 수 있다. - 이걸 생각해낼 줄 알아야함 여기선 해당 인덱스의 문제를 푼다/풀지 않는다 라고 재귀호출 단, 제한 시간을 넘어가면서 풀 순 없다. L번째에 있는 문제를 푼다/풀지 않는다 인것! L == n이 되면 모든 문제를 푼 것 ~ 모든 문제를 풀지 않는 것에 대한 조합(?)들이 만들어진다. 푸는 여부에 따른 문제 수, 점수의 합, 시간의 합을 인자로 보낸다. import java.util.*; public class Main { static int answer = Integer.MIN_VALUE, n, m; public void DFS(int L, int sum, int time, int[] ps, int[] pt) { //풀기로한 문제들의 시간이 제한 시간을 초과..

앞의 문제와 같이 부분집합 개념의 문제라고 볼 수 있다. - 이걸 생각해낼 줄 알아야함 여기선 해당 인덱스의 원소(바둑이의 무게)를 트럭에 태운다/태우지 않는다라고 재귀호출 L번째 인덱스에 있는 바둑이의 무게를 더한다/더하지않는다 인것! L == n이 되면 바둑이들의 무게를 모두 더한것 ~ 모두 더하지 않는 것에 대한 조합(?)들이 만들어진다. 태우는 여부에 따른 바둑이의 수, 바둑이들의 무게의 합, 해당 배열을 매개변수로 사용한다. import java.util.*; public class Main { static int answer = Integer.MIN_VALUE, c, n; public void DFS(int L, int sum, int[] arr) { //트럭 용량보다 바둑이들을 더 많이 태울..

부분집합 구하기 문제처럼 해당 숫자를 사용한다/사용하지 않는다로 재귀호출 했던 것 처럼 여기선 해당 인덱스의 원소를 부분집합의 합으로 사용한다/사용하지 않는다라고 재귀호출 L번째 인덱스에 있는 숫자를 더한다/더하지않는다 인것! L == n 이 되면 모두 더하는 것 ~ 모두 더하지 않는 것에 대한 조합(?)들이 만들어진다. 매개변수로는 사용여부에 따라 합칠 숫자의 갯수, 합칠 숫자들의 합, 배열로 설정한다. import java.util.*; public class Main { static String answer = "NO"; static int n, total = 0; boolean flag = false; public void DFS(int L, int sum, int[] arr) { //합이 같은경..

1번 정점에서 각 정점으로 가는 최소 이동 간선수를 출력하시오 6 9 1 3 1 4 2 1 2 5 3 4 4 5 4 6 6 2 6 5 graph.get(0) - [] graph.get(1) - [3,4] graph.get(2) - [1,5] graph.get(3) - [4] graph.get(4) - [5,6] graph.get(5) - [] graph.get(6) - [2,5] 경로 탐색과 마찬가지로 방문한 정점에 대해서 체크해주는 배열이 필요하다. 여기서 방문 체크 이유는 해당 정점을 방문 했다는게 최단 거리를 구했다는 의미이기 때문이다. 경로 탐색과는 다르게 방문 체크를 푸는 작업을 하지 않아도 된다. 1.최단거리는 BFS라고 생각하면 된다.! 1번 정점에서 한번 만에 가는 정점, 두번 만에~, 세..

방향 그래프의 1번 정점에서 n번 정점으로 가는 모든 경로의 가지 수를 출력하시오. 첫 줄은 정점 , 간선 수 5 9 1 2 1 3 1 4 2 1 2 3 2 5 3 4 4 2 4 5 1 2 3 4 5 1 2 5 1 3 4 2 5 1 3 4 5 1 4 2 5 1 4 5 graph.get(1) - [2,3,4] graph.get(2) - [1,3,5] graph.get(3) - [4] graph.get(4) - [2,5] import java.util.*; public class Main { static int n, m, answer = 0; static ArrayList graph; static int[] ch; public void DFS(int v) {//현재의 지점은 v if(v==n) answer+..

방향 그래프의 1번 정점에서 n번 정점으로 가는 모든 경로의 가지 수를 출력하시오. 첫 줄은 정점 , 간선 수 5 9 1 2 1 3 1 4 2 1 2 3 2 5 3 4 4 2 4 5 1 2 3 4 5 1 2 5 1 3 4 2 5 1 3 4 5 1 4 2 5 1 4 5 무방향 그래프 - graph[a][b] = 1 / graph[b][a] = 1 방향 그래프 - graph[a][b] = 1 가중치 방향 그래프 - graph[a][b] = c 정점 갯수가 많아지면 인접행렬은 메모리 낭비와 시간 복잡도가 길어진다. 그때 인접리스트 사용하면 된다. 현재는 인접행렬로 연습. 인접행렬은 N제곱 크기 만큼 배열로 만들어야 하므로 정점이 많아질 때 인접리스트를 사용하는게 좋다. 그리고 갈 수 있는 정점을 확인하는것도 ..