본문 바로가기
728x90

전체 글129

[JAVA]백준 14002번: 가장 긴 증가하는 부분 수열 4 www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 1. 문제 설명 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하고 가장 긴 증가하는 부분수열의 길이와 가장 긴 증가하는 부분 수열을 출력하는 문제이다. 먼저 dp배열을 사용하여 현재 위치를 포함하여 만들 수 있는 가장 긴 증가하는 부분수열의 길이를 저장하였다. 그리고 cache 배열을 사용하여 현재 위치에서 가장 긴 .. 2021. 1. 20.
[JAVA]백준 1915번: 가장 큰 정사각형 www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 1. 문제 설명 0과 1로 된 n*m 배열이 있을 때 1로만 구성되어있는 가장 큰 정사각형의 크기를 구하는 문제이다. 현재 위치를 (X, Y)라고 할 때 현재 위치를 포함하고 만들 수 있는 가장 큰 정사각형의 길이를 cache 배열에 저장한다고 하자. cache [X][Y] 값은 cache [X-1][Y-1], cache [X-1][Y], cache [X][Y-1]의 최솟값의 1을 더한 값이다. cache [][] 값은 현재 위치에서 cache [][] 값만큼의 길이를 가진 정사각.. 2021. 1. 18.
[JAVA]백준 1520번: 내리막 길 www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. 문제 설명 지도가 있을 때 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 문제이다. list 배열로 지도를 입력받고 list 배열과 같은 크기의 cache 배열을 만들고 -1로 채운다. -1로 채우는 이유는 현재 위치를 방문했는지 방문하지 않았는지 구분하기 위해서이다. 그 후 재귀를 통해 현재 위치와 각각의 상, 하, 좌, 우 list 값을 비교해 다.. 2021. 1. 16.
[JAVA]백준 5557번: 1학년 www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 1. 문제 설명 숫자가 주어질 때 +,-만 사용하여 만들 수 있는 올바른 등식의 수를 구하는 문제이다. 재귀함수와 for문을 이용하여 풀었다. 1) 재귀 함수 점화식 x가 인덱스 번호, y가 현재까지 합이라고 한다면 cache[x][y]=cache[x+1][y+list[x+1]]+cache[x+1][y-list[x+1]] 이다. 2) for문 점화식 x가 현재 인덱스 번호, y가 인덱스 x-1까지의 합이.. 2021. 1. 16.
728x90

티스토리툴바