본문 바로가기

ps java7

[ps java] BOJ 9251 LCS 해설 LCS 웰-노운 DP 문제이다 [골드5]자주 쓰이는 곳이 많으니, 완벽히 숙지하자!https://www.acmicpc.net/problem/9251  LCS(Longest Common SubSequance): 최장 공통 부분 수열 문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.예제 입력 1ACAYKPCAPCAK예제 출력.. 2025. 3. 18.
[ps java] BOJ 9465 스티커 해설 조금 생각해봐야 하는 DP 문제이다 [실버1]2개의 dp를 돌려야만 풀 수 있는 좋은 문제! https://www.acmicpc.net/problem/9465 문제상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스.. 2025. 3. 17.
[ps java] BOJ 11053 가장 긴 증가하는 부분 수열 해설 LIS(Longest Increasing Subsequence)를 학습할 수 있는 웰-노운 DP 문제다! [실버2]https://www.acmicpc.net/problem/11053  문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)출력첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.예제 입력 1610 20 10.. 2025. 3. 11.
[ps java] BOJ 1149 RGB 거리 해설 DP를 학습할 수 있는 좋은 문제다! [실버1]https://www.acmicpc.net/problem/1149  문제RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.입력첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초.. 2025. 1. 31.
[ps java] BOJ 1912 연속합 해설 (카데인 알고리즘) DP를 학습하기 좋은 웰-노운 문제이다 [실버2] https://www.acmicpc.net/problem/1912 문제n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.입력첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.출력첫째 줄에 답을 출력한다.예제 입력 11010 -4 3 1 5.. 2025. 1. 31.
[ps java] 재귀 -> DP 변환 예시 코드(BOJ 9184) https://www.acmicpc.net/problem/9184재귀를 DP로 바꾸는 문제이다 [실버2]재귀 호출만 생각하면 신이 난다! 아닌가요?  아래와 같은 재귀 호출 알고리즘 코드가 있다하지만 a b c 에 15 15 15 만 입력하더라도 실행하는 데에 너무 많은 시간이 걸린다따라서 우리는 아래의 코드를 DP로 변형해 볼 것이다import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); whi.. 2025. 1. 19.
[ps java] 피보나치 수열 알고리즘(재귀, DP) 우리가 일반적으로 알고 있는 피보나치 수열에 대한 재귀 알고리즘은 다음과 같다import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); System.out.println(fibonacci(n)); br.close(); } private static int fibonacci(int n) { if (n == 0) {.. 2025. 1. 19.

티스토리툴바