본문 바로가기
728x90

분류 전체보기129

[JAVA]백준 2225번: 합분해 www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1. 문제 설명 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 세는 문제이다. Top down 방식과 Bottom up 두 가지 방식으로 풀 수 있다. 1) Top down 변수 remain을 남은 합, k_use를 현재까지 더한 정수의 개수라고 한다면 cache [remain][k_use]=cache [remain-1][k_use]+cache [remain][k_use-1]이다. 점화식을 이용하여 위의 식을 얻을 수 있다. cache [remain][k_use]= ∑cache [remain-x][k_use-1] (0 2021. 1. 15.
[JAVA]백준 11054번: 가장 긴 바이토닉 부분 수열 www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 1. 문제 설명 가장 긴 바이 토닉 수열의 길이를 구하는 문제이다. 바이 토닉 수열은 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1... > Sn을 만족하는 수열을 말한다. 가장 긴 증가하는 부분수열 문제를 풀었다면 어렵지 않게 해결할 수 있다. 왼쪽에서 시작해서 증가하는 부분 수열 문제를 풀고 오른쪽 끝에서 시작하여 증가하는 부분 수열 문제를 풀고 두 문제를 합쳐서 제일 긴 바이토닉 수열의 .. 2021. 1. 12.
[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.
728x90

티스토리툴바