haejun IT

정수삼각형 풀이 문제의 규칙을 하나하나 따져봤을 때, 다음의 규칙을 알 수 있다. i 횟수 예시 1 1 7 2 2 (7+3), (7+8) 3 4 (7+3+1), (7+8+1), (7+8+0) i 가 증가함에 따라 2^(n-1)번의 횟수가 적용된다는 것을 알 수 있다. 문제에서 주어진 입력의 크기가 1

백준 파도반 수열 풀이 백준 사이트 특성상 알고리즘의 분류가 되어 있어 DP 문제라는 것을 알 수 있지만 실전같은 경우는 어떻게 DP 문제라는 것을 유추할 수 있을까? 위의 문제에서 제시한 예시를 보면 이 전의 연산 결과에 따라서 다음의 연산 결과를 저장한다. 고로 작은 것을 통해 큰 것의 최적해를 찾는 것이기 때문에 DP를 사용하면 된다는 것을 유추할 수 있다. 또한 입력 N의 범위가 1

문제 백준 1로 만들기 풀이 과정 그리디 알고리즘과 구분하기. 그리디 알고리즘은 각 단계에서 최적의 해를 보장해야하지만, 이 문제는 무엇으로 나눌지에 따라서 최적의 해가 달라지기 때문에 DP로 풀어야한다. 또한 입력 갯수와 시간 제한이 빡빡하기 때문에 이를 보고 유추했을 때, DP를 떠올릴 수 있다. 각 단계별로 네가지의 연산이 가능하기때문에 이 중에서 최솟값을 구해주면 된다. 따라서 이 문제의 점화식은 다음과 같다. min(ai-1, ai/2, ai/3 ai/5). 나머지를 구하는 연산은 각 조건에 해당할 때만 수행할 수 있어야 한다. (a의 i-1번째, a의 i를 2로 나눔, a의 i를 3으로 나눔, a의 i를 5로 나눔의 의미) 이를 코드로 구현하면 다음과 같이 구현할 수 있다. +1을 해주는 것은..

다이나믹 프로그래밍 (DP) 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(Top-down, Bottom-up)으로 구성된다. 동적 계획법이라고도 부른다. 일반적으로 프로그래밍 분야에서 동적(Dynamic)이란 어떤 의미를 가질까? 자료구조에서 동적 할당(Dynamic Allocation)은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법을 의미한다. 반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어이다. 다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있다. 최적 ..