동적 계획법

문제설명입력 & 출력나의 풀이문제 접근 방법 7 3 8 8 1 0 2 7 4 44 5 2 6 5 "백준 - 정수 삼각형"문제는 위와 같은 정수 삼각형에서 맨 위층에서 시작해서, 아래에 있는 수를 선택하여 마지막 레벨까지 도착했을 때 최대 합을 구하는 문제입니다. 이 때 아래에 있는 수는 왼쪽 대각선 또는 오른쪽 대각선만 선택할 수 있습니다. 이 문제를 해결하기 위한 핵심은 동적 계획법 (DP)을 사용하는 것입니다. 삼각형에서 각 정점마다 그 위치까지 올 수 있는 최대 합을 계산하여, 결국 맨 아래까지 내려오면서 최대 합을 구하는 방식입니다.  [Algorithm] 동적 계획법(Dynamic Programming, DP, Java) 알아보기동..

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 가장 긴 증가하는 부분 수열"문제가 처음에는 쉽게 이해가 되지 않았지만 알고보면 크게 어렵지 않은 문제입니다. 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하는 문제입니다. 문제에서 나와있듯이 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4입니다. 가장 긴 증가하는 부분 수열이라는 말은 주어진 수열에서 순서대로 (즉, 원래 수열의 순서를 유지하면서) 증가하는 수들 중에서 가장 긴 부분 수열을 찾는 문제입니다.  이때 "가장 긴"은 부분 수열의 길이를 의미하며, 반드시 연속된 원소일 필요는 없습니다. 즉, 예..

문제설명입력 & 출력나의 풀이접근 방법먼저 이번 "백준 - 계단 오르기" 문제는 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임입니다. 문제를 하나씩 살펴보면 문제는 규칙이 있고 이 규칙을 유지한채 각 계단의 최댓값을 구하면 되는 문제입니다.계단은 1 칸과 2칸 만 오를 수 있다.계단을 연속해서 3계단을 밟으면 안된다.마지막 계단은 반드시 밟아야 한다.따라서, 연속해서 3개의 계단을 밟을 수 없다는 제약을 고려하여, 각 계단을 오를 때 이전에 1칸을 올라왔는지, 아니면 2칸을 올라왔는지에 따라 최댓값을 구하는 방식으로 접근할 수 있습니다. 위와 같은 예제를 기준으로 각 계단이 갖는 최댓값을 구하면 다음과 같습니다. 1020 1525 10201 Jump1030355065..

문제설명입력 & 출력문제 이해하기이번 "백준 - 다리 놓기"문제는 조합론을 활용하여 해결할 수 있는 문제입니다. 문제 자체는 어렵지 않으나 이항 계수의 공식이나 개념을 모른다면 쉽지 않은 문제입니다. 이 문제는 주어진 두 개의 사이트에서 최대한 많은 다리를 놓을 수 있는 방법을 구하는 문제로, 이항계수를 기반으로 풀 수 있습니다. 이항계수 : "n개 중에서 k개를 고르는 경우의 수"를 나타내며, 조합이라고도 불립니다.  문제를 해결하는 방법은 크게 두 가지로 나눌 수 있습니다. 첫 번째 : 이항계수를 직접 계산하는 방법으로, 팩토리얼을 활용하여 조합을 계산하는 방식입니다. [백준, 11050번] 이항 계수 1 (수학, 구현, 조합론, Java)문제설명입력 & 출력나의 풀이이번 문제는 "이항 계수 1" 문..