하다보면 늘겠지

이것도 부분집합 개념의 문제라고 볼 수 있다. - 이걸 생각해낼 줄 알아야함 여기선 해당 인덱스의 문제를 푼다/풀지 않는다 라고 재귀호출 단, 제한 시간을 넘어가면서 풀 순 없다. 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제곱 크기 만큼 배열로 만들어야 하므로 정점이 많아질 때 인접리스트를 사용하는게 좋다. 그리고 갈 수 있는 정점을 확인하는것도 ..

루트 노드 1에서 말단 노드까지의 길이 중 가장 짧은 길이를 구하시오.(최단 거리는 BFS) import java.util.*; class Node { int data; Node lt, rt; //자식 노드들의 주솟값 public Node(int val) { data=val; lt=rt=null; } } public class Main { Node root; public int BFS(Node root) { Queue Q = new LinkedList(); Q.offer(root); int L = 0; while(!Q.isEmpty()) { //레벨의 길이를 구하자! int len = Q.size(); //1 2 4 8 .... for(int i = 0; i < len; i++) { Node cur = ..

루트 노드 1에서 말단 노드까지의 길이 중 가장 짧은 길이를 구하시오. 가장 짧은 경로를 DFS로 푸는건 매우 비효율적이나 학습을 위한 문제풀이임. import java.util.*; class Node { int data; Node lt, rt; public Node(int val) { data=val; lt=rt=null; } } public class Main { Node root; public int DFS(int L, Node root) { if(root.lt == null && root.rt == null) return L; else return Math.min(DFS(L+1, root.lt), DFS(L+1, root.rt)); } public static void main(String[] ..

현수의 위치에서 3갈래로 (앞으로 1,뒤로 1, 앞으로 5) 레벨 탐색하면된다. 이동한 위치에 대해서 방문처리 해주는 배열이 필요하다. - 길이는 10001 여기서 방문처리의 이유는 효율성 때문이다. 5번 위치에서 뻗어나가다가 5번 위치가 되었을 때 그 5번 위치에 또 탐색하는 것은 비효율적이다. import java.util.*; public class Main { int answer = 0; //3가지 점프 종류 int[] dis = {1, -1, 5}; //방문했던 위치인지 확인하는 배열 int[] ch; Queue Q = new LinkedList(); public int BFS(int s, int e) { //좌표는 1~10000 사이임 ch = new int[10001]; //처음 현수의 위치..

아래 그림과 같은 이진트리를 레벨탐색으로 출력하세요. 뺀 다음 데이터 찍고 자식들을 넣은 다음 레벨업 시켜 -> 계속 반복 import java.util.*; class Node { int data; Node lt, rt; public Node(int val) { data=val; lt=rt=null; } } public class Main { Node root; public void BFS(Node root) { Queue Q = new LinkedList(); //루트 노드는 넣어둔다. Q.offer(root); int L = 0; //맨 처음 루트 노트는 0 L은 레벨 while(!Q.isEmpty()) { int len = Q.size(); System.out.print(L + " : "); fo..