코딩연습이 좋아서/이론이 좋아서

DFS, BFS 활용 - 수열 추측하기

설명가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다.예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오.단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.입력첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다.N은 가장 윗줄에 있는 숫자의 개수를 의미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다.출력첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다.답이 존재하지 않는 경..

DFS, BFS 활용 - 조합의 경우수(메모이제이션)

설명로 계산합니다.하지만 여러분은 이 공식을 쓰지않고 다음 공식을 사용하여 재귀를 이용해 조합수를 구해주는 프로그램을 작성하세요.입력첫째 줄에 자연수 n(3출력첫째 줄에 조합수를 출력합니다.예시 입력 1 5 3예시 출력 110예시 입력 2 33 19예시 출력 2818809200 import java.util.Scanner;public class Main { static int[][] a = new int[35][35]; public static int DFS(int n, int r) { if (a[n][r] > 0) return a[n][r]; if (r == 0 || n == r) return 1; else return a[n][r] = DFS(n - 1..

DFS, BFS 활용 - 동전교환(DFS)

설명다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가?각 단위의 동전은 무한정 쓸 수 있다.입력첫 번째 줄에는 동전의 종류개수 N(1그 다음줄에 거슬러 줄 금액 M(1출력첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.예시 입력 1 31 2 515예시 출력 13힌트출력 설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다. import java.util.Arrays;import java.util.Collections;import java.util.Scanner;public class Main { static int n; static int m; static int answer = Integer.MAX_VALUE; p..

DFS, BFS 활용 - 중복순열 구하기(DFS)

1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 입력설명첫번째 줄에 자연수 N(3 출력설명첫번째 줄에 결과를 출력합니다.출력순서는 사전순으로 오름차순으로 출력합니다. 입력예제3 2출력예제1 11 21 32 12 22 33 1 import java.util.Scanner;public class Main { static int n; static int m; static int[] pm; public static void DFS(int L) { if (L == m) { for (int i : pm) { System.out.print(i + " "); ..

DFS, BFS 활용 - 최대점수 구하기(DFS)

설명이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다.제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다.(해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)입력첫 번째 줄에 문제의 개수N(1두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.출력첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.예시 입력 1 5 2010 525 1215 86 37 4예시 출력 141 import java.util.Scanner;public class Main { static int..

DFS, BFS 활용 - 바둑이 승차(DFS)

설명철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울수가 없다.철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.입력첫 번째 줄에 자연수 C(1둘째 줄부터 N마리 바둑이의 무게가 주어진다.출력첫 번째 줄에 가장 무거운 무게를 출력한다.예시 입력 1 259 58158423361예시 출력 1242 import java.util.Scanner;public class Main { static int c; static int n; static int max = 0; public static void DFS..

DFS, BFS 활용 - 합이 같은 부분집합(DFS : 아마존 인터뷰)

설명N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다.예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.입력첫 번째 줄에 자연수 N(1두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.출력첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.예시 입력 1 61 3 5 6 7 10 예시 출력..

Recursive, Tree, Graph(DFS, BFS 기초) - 그래프 최단거리(BFS)

1번 정점에서 각 정점으로 가는 최소 이동 간선수를 출력하세요. 입력설명첫째 줄에는 정점의 수 N(1 출력설명1번 정점에서 각 정점으로 가는 최소 간선수를 2번 정점부터 차례대로 출력하세요. 입력예제6 9 1 3 1 4 2 1 2 5 3 4 4 5 4 6 6 2 6 5 출력예제2 : 3 3 : 1 4 : 1 5 : 2 6 : 2 import java.util.*;public class Main { static int n; static int m; static int[] ch; static int[] d; static List> graph; public static void BFS(int v) { Queue queue = new LinkedList(); ..

Recursive, Tree, Graph(DFS, BFS 기초) - 경로탐색(인접리스트, ArrayList)

방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요.첫째 줄에는 정점의 수 N(1 입력예제5 91 21 31 42 12 32 53 44 24 5출력예제6 import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class Main { static int n; static int m; static int answer = 0; static int[] ch; static List> graph; public static void DFS(int v) { if (v == n) answer++; else { ..

Recursive, Tree, Graph(DFS, BFS 기초) - 경로 탐색(인접행렬)

방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요.첫째 줄에는 정점의 수 N(1 입력예제5 9 1 2 1 3 1 4 2 1 2 3 2 5 3 4 4 2 4 5출력예제6 import java.util.Scanner;public class Main { static int n; static int m; static int answer = 0; static int[] ch; static int[][] graph; public static void DFS(int v) { if (v == n) answer++; else { for (int i = 1; i - 한번 방문 한 것은 c..