728x90 반응형 DP4 70. Climbing Stairs 주어진 계단을 오를 때, 각 단계마다 1단계 또는 2단계씩 올라가는 방법의 수를 계산하는 문제입니다. 문제 설명: 당신은 n개의 계단을 올라야 합니다. 한 번에 1단계 또는 2단계씩 올라갈 수 있을 때, n개의 계단을 올라갈 수 있는 방법의 수를 계산하세요. 예를 들어, n = 3인 경우, 다음과 같은 방법으로 3개의 계단을 올라갈 수 있습니다: 1단계 -> 1단계 -> 1단계 1단계 -> 2단계 2단계 -> 1단계 따라서 3개의 계단을 올라가는 방법은 총 3가지입니다. 예시: 입력: n = 2 출력: 2 설명: 2개의 계단을 올라가는 방법은 2가지입니다: 1단계 -> 1단계 또는 2단계 한 번. 입력: n = 3 출력: 3 설명: 3개의 계단을 올라가는 방법은 3가지입니다 (위의 예시 참고). 이 문제.. 2023. 11. 3. lego blocks 이 문제는 다이나믹 프로그래밍(Dynamic Programming)을 사용하여 풀 수 있는데, 공식적인 해결 방법을 제공하기보다는 알고리즘의 핵심 아이디어를 설명하겠습니다. 이 문제를 해결하려면 다음 단계를 수행해야 합니다: 각 레고 블록의 너비를 입력으로 받습니다. 각 줄마다 레고 블록을 쌓아보면서 가능한 모든 높이를 계산합니다. 가능한 모든 높이를 저장하는 배열을 만듭니다. 모든 줄에 대해 가능한 높이를 구한 후, 가능한 높이 배열을 기반으로 각 줄의 최대 높이를 계산합니다. 모든 줄의 최대 높이를 곱하여 결과를 출력합니다. 다음은 이 문제를 C#으로 구현한 코드입니다. 이 코드는 주요 아이디어를 나타내며, 실제로 동작하는 코드를 완성하려면 입력 처리 및 출력 등을 추가해야 할 것입니다. using .. 2023. 10. 5. 동전 교환(거스름돈) 알고리즘 최소 갯수로 동전 교환하는 방법 전체 금액보다 작은 동전중에서 가장 큰 동전부터 차례차례 채워 나간다. 현재의 동전만큼을 뺀 거스름돈에서 현재 동전하나를 추가하여 만드므로 그 전의 거스름돈에 1을 더하면 된다. dp[j] = min(dp[j],dp[j-coin[i]]+1); 이미 구해진 거스름돈이 더 적은 값을 가지고 있다면 현재의 값을 유지하면 된다. for i 2019. 5. 6. 최장 증가 부분 수열 최장 증가 부분 수열(LIS) 동적 계획법으로 풀 수 있는 유명한 알고리즘 문제이다. 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이 때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라고 한다. O(n^2) 방법 for (int i = 0; i arr[j]) { if (dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; } } } } 매 순간마다 자기보다 작은 구간에 최댓값을 찾는 쿼리를 날려 최댓값 +1을 업데이트하는 방식으로 처리를 한다면, N번을 확인하.. 2019. 5. 5. 이전 1 다음 728x90 반응형