728x90 다이나믹 프로그래밍35 [JAVA]백준 9251번: LCS www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 문제 설명 두 수열이 주어졌을 때 모두의 부분 수열이 되는 수열 중 가장 긴 길이를 찾는 문제이다. 재귀 함수로 dp로 구현한 문제. cache 배열 값의 의미는 문자열을 cache 배열의 인덱스부터 끝까지 잘랐다고 하였을 때 그 문자열들의 LCS 값이다. dp 함수의 인수로 첫 번째 문자열 인덱스와 두 번째 문자열 인덱스를 준다. 만약 이미 이 위치의 LCS .. 2021. 1. 11. [JAVA]백준 5904번: Moo 게임 www.acmicpc.net/problem/5904 5904번: Moo 게임 Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o www.acmicpc.net 1. 문제 설명 문자열 S(k)는 S(0)="moo", S(k)=S(k-1)+m+o가 k+2개+S(k-1)인 문자열이다. N이 주어졌을 때, S(k)의 N번째 글자를 구하는 프로그램을 작성하는 문제이다. N을 분할해 나가면서 문제를 해결하였다. 먼저 최초로 N보다 큰 문자열의 길이를 구한다. 구한 문자열이 S(X)라고 할 때, S(X)=S(X-1)+m+o가 X+2개+S(X-1.. 2021. 1. 2. [JAVA]백준 4779번: 칸토어 집합 www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 1. 문제 설명 -로 채워진 입력받은 수의 길이의 문자열을 만든 후 선의 길이가 1이 될 때까지 3 등분하고 가운데 문자열은 공백으로 바꾼다. 먼저 char 배열 전체를 공백으로 바꾸고 range가 1이 될때까지 삼등분하면서 재귀 호출하였다. 2. 코드 import java.awt.image.BufferedImageFilter; import java.io.*; import java.lang.reflect.Arr.. 2020. 12. 28. 이전 1 ··· 6 7 8 9 다음 728x90