0과 1의 쉼터

[Code Tree] 서로 다른 BST 개수 세기 [Python]

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-number-of-unique-bst/description 서로 다른 BST 개수 세기 설명 | 코드트리서로 다른 BST 개수 세기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약1 ~ N으로 이루어진 서로 다른 BST의 개수를 구하자.아이디어서로 다른 BST는 루트 노드에 따라 좌우를 구성하는 서브트리가 달라진다.1 ~ N에 대해 root가 K이면, 왼쪽 서브트리는 1 ~ K - 1, 오른쪽 서브트리는 K + 1 ~ N 노드들을 가진다.점화식은 다음과 같다.dp[i] : 노드 i개로 ..

[Code Tree] 사각형 채우기 3 [Python]

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-rectangle-fill-3/description 사각형 채우기 3 설명 | 코드트리사각형 채우기 3를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약2 * N 크기의 사각형에 1 * 2, 2 * 1, 1 * 1 크기의 사각형으로 채우는 방법의 수를 구하자.아이디어점화식은 다음과 같다.dp[i] : 2 * i 크기 사각형을 채우는 방법의 수1*1 사각형으로 인해 변수가 많아졌다. 하나씩 살펴보자.dp[1]은 21 한 개와, 11 두 개로 만들 수 있다.(dp[1] = 2)dp[2]는 예..

[Code Tree] 사각형 채우기 [Python]

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-rectangle-fill/description 사각형 채우기 설명 | 코드트리사각형 채우기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약2 * N 크기의 사각형에 1 * 2, 2 * 1 크기의 사각형으로 채우는 방법의 수를 구하자.아이디어점화식은 다음과 같다.dp[i] : 2 * i 크기 사각형을 채우는 방법의 수2 * i 크기의 사각형을 채우기 위한 방법은 2 * (i - 1) 사각형에 2 * 1 사각형 하나를 붙이는 경우와, 2 * (i - 2) 사각형에 1 * 2 사각형 두개를..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-climbing-stairs/description 계단 오르기 설명 | 코드트리계단 오르기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약주어진 규칙대로만 계단을 오를 수 있을 때, N층 높이의 계단을 오르는 모든 경우의 수를 구하자.아이디어점화식은 다음과 같다.dp[i] : i 번째 계단을 오르는 모든 경우의 수계단은 2칸 또는 3칸씩만 오를 수 있으므로, 현재 계단까지 오르기 위해서는 2/3칸 낮은 계단에서 올라오는 경우의 수만 존재하기 때문이다.dp[i] = 1, { N = 2 o..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/intro-fibonacci-number/description 피보나치 수 설명 | 코드트리피보나치 수를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약N번째 피보나치 수를 구하기 위해 DP로 점화식을 구현하자.피보나치 수열은 다음을 따른다.dp[i] = 1, N ≤ 2dp[i] = dp[i - 1] + dp[i - 2], N > 2N = int(input())# Please write your code here.def fibo(N): if N == 1 or N == 2: return 1..

문제11049번: 행렬 곱셈 순서 11049번: 행렬 곱셈 순서 boj.ma 풀이문제 요약행렬 N개의 곱셈 순서를 적절히 정해, 곱셈 연산 수의 최소값을 구해야 한다.아이디어행렬 곱셈은 결합 순서에 따라 계산 비용이 달라진다.따라서, 각 구간 [L, R]을 적절히 나누는 위치 t를 찾아 최소 비용을 계산해야 한다.점화식은 다음과 같다.dp[L][R]: L ~ R 구간의 최소 곱셈 비용dp[L][R] = dp[L][t] + dp[t + 1][R] + (matrix[L][0] * matrix[t][1] * matrix[R][1])행렬이 1개 일 때행렬이 1개 일 때, 즉 L == R일 때는 연산을 하지 않으므로, dp[L][L] = 0이 된다. // Solve int[][] dp =..

문제2225번: 합분해 2225번: 합분해 boj.ma 풀이정수 K개의 합이 N이 되도록 만드는 경우의 수를 세는 문제다.덧셈의 순서가 바뀐 경우는 다른 경우이지만, 동일한 수에 대한 연산은 하나의 경우로 볼 수 있다.ex) 1+2, 1+2는 다른 경우, 1+1, 1+1은 피연산자의 순서는 다르지만, 덧셈의 순서(?)는 다르다.dp[N][K] : 정수 K로 N을 만드는 경우의 수초기값부터 설정하자.dp[0][K]인 경우 0만 가능하다. for (int k = 1; k dp[N][1]은 N자신만 가능하다. for (int i = 1; i dp[N][K]는 dp[N - 1][K]의 맨 뒤 요소를 1늘리는 경우와dp[N][K-1]에 0을 추가해주는 경우로 볼 수 있다. f..

문제https://www.acmicpc.net/problem/10844 풀이정수 N이 주어졌을 때, 길이가 N인 수 중 문제에 주어진 ‘계단 수’가 몇 개 인지 알아내는 문제다.우선 N이 1일 때 존재하는 계단 수는 1 ~ 9이다. int[][] dp = new int[N + 1][11]; for (int j = 1; j N이 2일 때는 이전 계단 수에서 1을 더하거나 뺀 값들이 새로운 계단 수가 된다.따라서 점화식을 다음과 같이 정의할 수 있다.dp[i][j] : 길이가 i이면서, 마지막 숫자가 j로 끝나는 계단 수dp[i][0]은 dp[i - 1][1]에서 1을 뺀 결과이고, dp[i][9]는 dp[i - 1][8]에서 1을 더한 값이다. for (int i = ..

문제https://www.acmicpc.net/problem/14335 풀이문자열 S에 대해 순서를 고려한 서로 다른 부분 수열의 수를 구하는 문제다.문자열의 길이가 최대 1,000으로 모든 부분 수열들을 구하고 중복을 제거한다면 시간 초과가 발생한다.순서를 고려하므로 중복되는 문자에 대한 부분 수열을 제거해야 한다.dp[i] : i번까지 문자들로 만들어진 서로 다른 부분 수열의 수중복을 고려하지 않고 부분 수열의 수를 기록하자. long[] dp = new long[N + 1]; dp[0] = 1; for (int i = 1; i 이제 중복되는 요소를 제거해보자.이전에 마지막으로 등장한 S[i - 1]의 위치를 j라고 하자..

문제https://www.acmicpc.net/problem/1354 풀이주어지는 N에 대해 $A_N$을 구하는 문제다.단 N은 최대 $10^{13}$이며, 중복되는 계산을 최소화 해야한다.범위가 넓기 때문에 Map을 사용해서 중간 계산을 기록하면 된다. private static long getA(long i) { if (i 소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/01354.java