본문 바로가기

DP

[BOJ] 백준 11726 2xn 타일링 (Java)
Dot Algo∙ DS/PS 2021. 8. 18. [BOJ] 백준 11726 2xn 타일링 (Java) #11726 2xn 타일링 난이도 : 실버 3 유형 : DP 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net ▸ 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. ▸ 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) ▸ 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 문제 풀이 2xn타일링이 있을 때 2xn-1, 2xn-2, ... 에서 도출해낼 수 ..
[BOJ] 백준 1003번 피보나치 함수 (Java)
Dot Algo∙ DS/PS 2021. 8. 16. [BOJ] 백준 1003번 피보나치 함수 (Java) #1003 피보나치 함수 난이도 : 실버 3 유형 : DP 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net ▸ 문제 다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다. fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다. fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다. 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다. fibonacci(0)은 0을 출력하고, 0을 리턴한다. fibonacci(2)는 fibonac..
[BOJ] 백준 9095번 1,2,3 더하기 (Java)
Dot Algo∙ DS/PS 2021. 8. 16. [BOJ] 백준 9095번 1,2,3 더하기 (Java) #9095 1,2,3 더하기 난이도 : 실버 3 유형 : DP 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net ▸ 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. ▸ 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. ▸ 출력 각 테스트 케이스마다, n을 1, 2,..
[BOJ] 백준 1463번 1로 만들기 (Java)
Dot Algo∙ DS/PS 2021. 8. 16. [BOJ] 백준 1463번 1로 만들기 (Java) #1463 1로 만들기 난이도 : 실버 3 유형 : DP 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net ▸ 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. ▸ 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. ▸ 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 문제 풀이 DP문제로 바텀업, 탑다운 어떤 방식으로 접근해도 상관없다. 정..
[BOJ] 백준 14003번 가장 긴 증가하는 부분 수열 5 LIS - 이진탐색 (Java)
Dot Algo∙ DS/PS 2021. 8. 15. [BOJ] 백준 14003번 가장 긴 증가하는 부분 수열 5 LIS - 이진탐색 (Java) #14003 가장 긴 증가하는 부분 수열5 난이도 : 플레 5 유형 : 이진 탐색 / LIS / DP 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net ▸ 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. ▸ 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤..
[BOJ] 백준 14002번 가장 긴 증가하는 부분 수열 4 LIS - DP (Java)
Dot Algo∙ DS/PS 2021. 8. 15. [BOJ] 백준 14002번 가장 긴 증가하는 부분 수열 4 LIS - DP (Java) #14002 가장 긴 증가하는 부분 수열 4 난이도 : 골드 4 유형 : LIS / DP 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ▸ 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. ▸ 입력 첫째 ..
[알고리즘] 최장 공통 부분 수열 LCS - DP & 이진탐색 LIS (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 8. 10. [알고리즘] 최장 공통 부분 수열 LCS - DP & 이진탐색 LIS (Java) 최장 공통 부분 수열 LCS (Longest Common Subsequence) LCS(Longest Common Subsequence)는 LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 나타내지만 최장 공통 문자열(Longest Common Substring)을 말하기도 한다. 최장 공통 문자열(Longest Common Substring)은 반드시 부분 문자열이 연결된 형태여야한다. banana, vbankn 최장 공통 부분수열(Longest Common Subsequence)은 떨어져있어도 상관없다. bdanvv, vbkkanm 이번에 다룰 LCS 알고리즘은 최장 공통 부분수열(Longest Common Subsequence)이다. 이는 주어진 여러 개의 수열 ..
[알고리즘] 가장 긴 증가하는 부분 수열 LIS - DP & 이진탐색 (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 8. 9. [알고리즘] 가장 긴 증가하는 부분 수열 LIS - DP & 이진탐색 (Java) 가장 긴 증가하는 부분 수열 LIS LIS(Longest Increasing Subsequence)는 불연속 상관없이 가장 긴 증가하는 부분 수열을 구하는 알고리즘이다. 예시로, 수열 A = {10, 20, 10, 30, 20, 50}이 있다고 하면 해당 수열의 LIS는 {10, 20, 30, 50} 이다. 풀이 방법으로는 DP를 활용한 LIS, 이진탐색을 활용한 LIS 두 가지가 있다. DP는 단순하지만 시간복잡도가 O(n^2)을 가진다. 이진탐색을 활용하면 시간복잡도를 O(nlogn)을 가진다. 1. DP로 풀이하는 방법 dp는 1차원 배열로 dp[i]에는 0~i 증가하는 부분 수열의 크기를 나타낸다. dp[i] = 0~i의 증가하는 부분 수열 크기 수열 A = {10, 20, 10, 30, 20, ..

티스토리툴바

티스토리툴바