본문 바로가기

알고리즘/백준126

[Java] BOJ 11055번 가장 큰 증가 부분 수열 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 풀이 LIS(최장 증가 수열)을 응용하여 해결했습니다. LIS(최장 증가 수열)처럼 증가하는 긴 수열을 구하는 것은 동일하지만 이때, 합이 가장 큰 수열을 구해야 한다는 점을 주의해야 합니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringT.. 2021. 5. 6.
[Java] BOJ 11054번 가장 긴 바이토닉 부분 수열 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 가장 긴 바이토닉 부분 수열은 앞에서부터 가장 긴 증가하는 부분 수열의 개수 + 뒤에서부터 가장 긴 증가하는 부분 수열의 개수에다가 자기 자신은 두 번 들어갔으므로 1을 빼어 해결할 수 있었습니다. 예를 들어, 수열 1 5 2 1 4 3 4 5 2 1의 경우를 보면, 빨간색으로 쓴 1번은 앞에서부터 증가하는 부분 수열의 개수이고, 파란색으로 쓴 2번의 경우 뒤에서 부터 가장 긴 증가하는 부분 수열이 됩니다. 그리고 LBS는 초록색처럼 1번과 2번을 더해주되 i번째의 숫자가 두 .. 2021. 5. 5.
[Java] BOJ 1699번 제곱수의 합 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 풀이 최대 항의 최대 개수는 1^2으로만 이루어진 경우이므로 memo[i] = i로 초기화하였습니다. i - (j ^ 2)인 수의 최대항의 개수 + 1중 최소인 값을 찾아 해결했습니다. 예를 들어 i = 5, j = 2라면 5 - (2 ^ 2) = 1이므로 memo[1]의 최대 항의 최소 개수는 1입니다. 때문에, 1 + (2 ^ 2)를 하면 원래 i인 5가 되므로 문제에서 요구한 제곱수의 합으로 표현되므로 memo[1] .. 2021. 4. 30.
[Java] BOJ 9251번 LCS 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 DP를 이용해서 해결했습니다. 코드 주석에 설명을 포함했습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static String S1, S2; public static int[][] memo; public static void main.. 2021. 4. 29.
[Java] BOJ 1904번 01타일 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 풀이 점화식인 memo[i] = memo[i - 1] + memo[i - 2]를 사용해서 해결했습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public final static int mod = 15746; public static int N; public static int[] memo = new .. 2021. 4. 28.
[Java] BOJ 2623번 음악프로그램 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 풀이 위상정렬을 사용하여 해결했습니다. 코드 import java.io.*; import java.util.*; public class Main { public static int N, M; public static int[] in; public static int[][] adj; public static void main(String[] args) throws IOException { BufferedReader br = new Buffere.. 2021. 4. 23.

티스토리툴바