본문 바로가기
728x90

알고리즘115

[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.
[JAVA]백준 1725번: 히스토그램 www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 1. 문제 설명 주어진 히스토그램에 대해 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하는 문제이다. 종만북의 분할 정복 예시 문제 울타리 잘라내기 문제와 같은 문제이다. 종만북의 풀이과정 같이 3가지의 형태로 문제를 분할하여서 풀었다. 막대그래프를 반으로 잘랐을 때 가장 큰 직사각형은 3가지의 경우로 존재할 수 있다. 1. 가장 큰 직사각형은 왼쪽 그래프에만 있을 경우 2. 가.. 2021. 1. 2.
728x90

티스토리툴바