본문 바로가기

전체 글

 (268)
DP 필수 문제집 - 1주차 생각보다 점화식 찾기가 힘들었고 특히 DP에 어떤것을 기억할지 정하는 것이 힘들다 위 DP필수문제를 다 풀고 아래 알고리즘을 풀어봐야겠다. 이진탐색 알고리즘과 (Binary) 최장 증가 수열 알고리즘 (LIS)
[백준 java] 1890 - 점프 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net dp에 경로의 수를 저장하면서 도착 경로의 수를 구하는 문제이다. 원래는 해당 경로를 지났다는 표시만 하고 board[ i ] [ j ] 의 다음 목적지인 아래값이 x 축으로 이동하면 board[ i + board[ i ] [ j ] ] [ j ] y 축으로 이동하면 board[ i ] [ j + board[ i ] [ j ] ] 목적지인 board[ N-1 ] [ N-1 ] 에 도달하면 count ++ 하는 방식으로 계산했는데 이렇게 하면 이전에서 ..
[백준 java] 11048 - 이동하기 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 입력받은 숫자들을 2차원 int배열에 넣고 해당 배열을 사용하여 dp[i][j]의 값을 구한다. dp[i][j-1] 와 dp[i-1][j] 의 값을 비교하여 dp[i][j]를 구한다. 만약 b[1][2]의 총 최대값을 구하려면 b[0][2]와 b[1][1] 을 비교하여 큰 값을 b[1][2]과 더하여 dp에 저장한다. 이것을 dp[N][M]까지 반복하여 계산하면 사탕수의 최대값을 구할 수 있다. import java.io.BufferedReader;..
[백준 java] 10884 - 쉬운 계단 수 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제풀이 첫째줄 n을 입력받는다. 여기서 n은 자릿수를 나타낸다 n=2 두자릿수 중 계단 수를 찾는다. (총 17개) 1 : 10, 12 (2개) 2 : 21, 23 (2개) 3 : 32, 34 (2개) 4 : 43, 45 (2개) 5 : 54, 56 (2개) 6 : 65, 67 (2개) 7 : 76, 78 (2개) 8 : 87, 89 (2개) 9 : 98 (1개) 만약 n이 3이라면 n=3 1 : 123, 121, 101 (4개) 2 : 210, 212, 232, 234 (4개) 두번째 자릿수의 경우의 수는 n=2에서 구한 갯수가 들어간다. 예를들어 첫번째 자릿수가 2이면 두..
[백준 java] 11057 - 오르막 수 오르막 수 만들기 1112 1234 1345 이런식으로 인접한 숫자가 같거나 점점 오르는 형태의 수여야한다. 따라서 첫번 째 수에따라 만들 수 있는 수가 달라진다. 두 자리 수를 만들때 첫번째 숫자가 1이면 1 2 3 4 5 6 7 8 9 를 붙여 9개의 숫자를 만들 수 있고 첫번째 숫자가 4이면 44 45 46 47 48 49 6개 숫자를 만들 수 있다 세 자리 숫자를 만들때 만약 첫 숫자가 0이면 뒤에 모든 숫자가 올 수 있으니 두자리 숫자의 전체 갯수 55개의 숫자가 올 수 있고 첫 숫자가 1이면 55에서 두번 째 자리 숫자가 0이 올 수 없다 따라서 0으로 만들 수 있는 두자리 수를 다 빼줘야한다. 위 연산을 계산하기 위해 2차원 배열 dp를 만들었고 dp[ i ][ j ]에서 i는 i자릿수, j..
[백준 java] 11727 - 2xn 타일링 2 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 내가 푼 방법은 n = 1부터 5까지 구하고 해당 결과로 점화식을 찾았다. n = 1 : 1개 n = 2 : 3개 n = 3 : 5개 n = 4 : 11개 따라서 dp[n] = dp[n-1] + dp[n-2]*2 이란 점화식이 나온다. 내가 푼 해결방식은 너무 별로라서 다른 풀이를 찾아봤는데 다음과 같이 n=3일때 사각형 배치 방식은 시작이 n=2 으로 시작하거나 n=1 에 2x1사각형 가로로 두 개 or 2x2사각형 하나가 붙어있는 형태 즉 n=1로 두가지 형태를 만들 수 있게 된다. 따라서..
동적 계획법 알고리즘 (Dynamic Programming) 동적 계획법 동적 : 프로그램이 실행되면서 필요한 메모리를 할당하는 기법을 의미한다. 큰 문제를 작은 문제로 나누어 풀고 결과를 저장하고 재활용하는 알고리즘이다 대표적인 문제로 피보나치의 수 f(n) = f(n-1) + f(n-2) 가 있다. DP의 사용 조건 1. 반복되는 부분문제 (Overlapping Subproblems) 부분문제가 반복되지 않는다 = 재사용이 불가능 하니 DP알고리즘을 사용할수 없다. 피보나치의 수에서는 다음과 같이 반복되는 항이 있어 재활용이 가능하다. 2. 최적부분 구조 (Optimal Substructure) 구하려는 문제(큰 문제) 정답을 작은 문제 최적의 합으로 구할수가 있다. 큰 문제 f(n) 는 작은 문제 f(n-1) + f(n-2) 로 계산이 가능하다. 재귀함수와 ..
DP 필수문제 문제집 시작 DP문제집중 가장 쉬운 문제들로 구성된거 같다. ( 다른건 플레티넘 다이아 문제가 너무 많아서... )

티스토리툴바