JUINTINATION

문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제로 깊이우선탐색과 너비우선탐색의 개념을 익히는 문제입니다. 코드 자바 import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; i..

문제 https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 n개의 정수로 이루어진 수열 중에서 수열에서 수를 하나 제거할 수 있을 때 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 값을 구하는 문제입니다. 코드 자바 탑다운 방식을 이용한 코드입니다. dp1 배열은 임의의 수 x가 있을 때 arr[x]가 맨 오른쪽에 있을 때 수열에서 수를 하나 제거하지 않고 연속된 몇 개의 수의 합 중 가장 큰 값을 의미합니다. continous 함수..

문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 n개의 정수로 이루어진 수열 중에서 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 값을 구하는 문제입니다. 코드 자바 탑다운 방식을 이용한 코드입니다. dp 배열은 임의의 수 x가 있을 때 arr[x]가 맨 오른쪽에 있을 때 연속된 몇 개의 수의 합 중 가장 큰 값을 의미합니다. continous 함수 안에서 dp[idx]가 null이라면 coninous(idx - 1)를 재귀적으로..

문제 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 9251번 문제를 응용한 문제로 LCS(Longest Common Subsequence, 최장 공통 부분 수열)를, 즉 문자로 된 두 수열이 주어졌을 때 모두의 부분 수열이 되는 수열 중 가장 긴 것을 구하는 문제입니다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 됩니다. 코드 C언어 바텀업 방식을 이용한 코드입니다. d..

문제 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 0부터 n까지의 정수 k개를 더해서 그 합이 n이 되는 경우의 수를 구하는 문제입니다. 이때 덧셈의 순서가 바뀐 경우는 다른 경우(1+2와 2+1은 서로 다른 경우)이며 한 개의 수를 여러 번 쓸 수도 있습니다. 코드 자바 탑다운 방식을 이용한 코드입니다. dp 배열은 임의의 수 x, y가 있을 때 x를 만들어야 할 때 더할 수 있는 남은 횟수가 y인 경우의 수를 의미합니다. decomposition 함수에서 y가 1이라면 x를 수 1개를 이용하여 만들 수 있는 경우는 x 1가지 이므로 1을 반환하고 y가 1이 ..

문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 여행에 필요하다고 생각하는 n개의 무게와 가치를 가지는 물건이 있을 때 최대 k만큼의 무게만을 넣을 수 있는 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구하는 문제입니다. 코드 자바 탑다운 방식을 이용한 코드입니다. dp 배열은 임의의 수 x, y가 있을 때 1번부터 x번 사이에서 물건을 여러 개 골랐을 때 가방이 더..