JUINTINATION

문제 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 0번부터 N-1번으로 번호가 매겨진 사람들 중에 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 확인하는 문제입니다. A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 코드 자바 import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTok..

문제 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이 ..