매일 조금씩

문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 규칙을 찾아서 점화식을 세운다. n=5 까지 작은 문제들의 답을 넣고, n=6 부터는 dp[n] = dp[n-1] + dp[n-5] 로 구할 수 있다. 결과를 담을 배열의 자료형이 long형이어야 한다. 소스코드 package dp; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamR..

문제 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 풀이 타일을 0과1로 표현했을 뿐이지 아래와 동일한 문제이다. dp[1] = 1 dp[2] = 2 dp[3]부터는 아래 점화식을 따른다. dp[i] = dp[i-1]+ dp[i-2] 2021.10.29 - [Problem Solving/Programmers] - [프로그래머스] 2 x n 타일링 (Java) [프로그래머스] 2 x n 타일링 (Java) 문제 https://programmers.c..

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 DP문제로, Index를 차례대로 증가시키면서 해당 Index 왼편에 올 수 있는 바이토닉 부분 수열의 최대 개수를 구한다. 이때 기준 Index에서 작은 Index를 체크하면서, 기준보다 작은 수의 바이토닉 수열 최대 개수 중에 최대 값을 구한 후 +1을 해주면 된다. 아래 문제의 왼쪽 편만 구한 것이다. ..

문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 기준 숫자에서 왼쪽과 오른쪽을 나눈다. left[i] = i번째 수의 왼편에 올 수 있는 오름차순 부분 수열의 최대 개수 right[i] = i번째 수의 오른편에 올 수 있는 내림차순 부분 수열의 최대 개수 left[i] + right[i] 의 최대값에 1을 더한 것이 답이 된다. (1을 더하는 이유는 left, right에 기준 숫자가 빠져있기 때문) 차례대로 index를 증가 또는 감소 시키면서 채워나..

문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 DP문제가 제일 어렵다. DP문제는 사고의 전환이 필요하다. 나한테 너무 어려운 부분... 어쨌든 해당 문제는 구글링을 통해 힌트를 조금 얻어서 풀었다. dp[i][j] = i자리수에서 j로 끝나는 계단수의 개수 N(자리수)가 1일 때 1, 2, 3, 4, 5, 6, 7, 8, 9 dp[1][0] = 0 dp[1][1] = 1, dp[1][2] = 1 ... dp[1][8] =1 dp[1][9] = 1 N이 2일 때 10 / dp[2][0] = 1 21 / dp[2][1] = 1 12, 32, / d..

문제 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 풀이 DP를 이용하여 풀었다. 작은 문제들의 답을 구한다. dp[2] = 1, N이 2일 때는 최소 횟수가 1이다. (2으로 나눔) dp[3] = 1, N이 3일 때는 최소 횟수가 1이다 (3으로 나눔) ..

문제 https://programmers.co.kr/learn/courses/30/lessons/12914# 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 풀이 완전 탐색으로 풀면 시간 초과가 발생한다. 가만 보니 2 x n 타일링 문제와 동일하다. 아래 문제에서 세로 타일 한개를 1칸, 가로타일 두 개를 2칸으로 해당 문제에 대입할 수 있다. DP문제로 점화식을 이용해서 풀 수 있다. 2021.10.29 - [Alogirthm/Programmers]..

문제 https://programmers.co.kr/learn/courses/30/lessons/12900 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr 풀이 DP 방식으로 풀 수 있다. 코드는 정말 간단한데 점화식을 세우는 게 쉽지 않다. 타일이 가로로 끝나는 것과 세로로 끝나는 것을 분류해보면 아래와 같다. 가로길이가 i일 때, 타일링의 경우의 수는 = i-1의 경우의 수와 i-2의 경우의 수를 합한 것이다. i-1의 경우의 수에서 세로 타일을 붙임 i-2의 경우의 수에서 가로 타일을 붙임 ..