예를 들어 정수 X가 10일 때, 1로 만들기 위해서는10 -> 5 -> 4 -> 2 -> 1 방법으로 4번 연산을 통해 값을 구할 수 있지만, 10 -> 9 -> 3 -> 1 과 같이 3번의 연산을 통해서 1을 만들 수 있다.이를 메모이제이션을 사용하는 동적 계획법을
다음과 같이 n=1부터 하나하나 그려가면서 규칙을 찾아나갔다.즉, 규칙은 다음과 같다.dpn = dp n-1 + dpn-2n번째 타일은 다음의 경우를 더한 경우의 수로 나타낼 수 있다.n-1번째 타일에 2x1타일 한개를 붙인 경우n-2번째 타일에 1x2타일 두개를 붙인
다음과 같이 n=1부터 하나하나 그려가면서 규칙을 찾아냈다.즉, 규칙은 다음과 같다.dpn = dpn-1 + 2\*dpn-2n번째 타일은 다음의 경우를 더한 경우의 수를 나타낼 수 있다.n-1번째 타일에 2\*1 타일을 한개를 붙인 경우n-2번째 타일에 12 타일을 두
n=1부터 n=4까지 작성해보니 다음과 같은 규칙을 찾았다.즉, 규칙은 다음과 같다.f(n) = f(n-3) + f(n-2) + f(n-1)n번째 숫자는 다음의 경우를 더한 경우의 수로 연산할 수 있다.n-3번째 연산 조합에서 3을 더한 경우n-2번째 연산 조합에서 2
n=1부터 n=3까지 작성해보니 다음과 같은 규칙을 찾았다.n=1일 경우0 1 2 3 4 5 6 7 8 9 n=2일 경우00 01 02 03 04 .. 0911 12 13 14 15 .. 19...i = n 이며, 끝자리 수가 j 일 경우, 수 n-1 에 끝자리에 j부
n = 1부터 5까지 작성해보니 다음과 같은 규칙을 찾았다.즉, 다음과 같이 규칙을 찾을 수 있다.(j == 0일 경우) dpn = dpn-1 + dpn-1(j == 1일 경우) dpn = dpn-1마지막 자리수가 0일 경우, 다음에 0또는 1이 올 수 있다.마지막 자
예를 들어 cost0에서 가는 방법에 대해 생각해보았다.cost0 = 50 에서 갈 수 있는 곳은 cost1 = 50과 cost1이다.dp0 = Math.math(dp1, dp1) + cost0 을 통해서, 둘 중 어느 곳으로 가는지 결정할 수 있다.cost0으로 가는
효주만 최댓값으로 와인을 마신다라..오늘 나도 와인이 마시고 싶은 날이었다 후. .그래도 패턴을 찾기까지 근접했다..!!
작은 문제들을 풀어서 결합하는 방식으로 반복문을 사용하는 bottom-up 방식과 재귀 방식을 사용하는 top-down방식 두가지로 나눠서 확인하였다.\- bottom-up 방식우선 i번째 dp값을 알기 위해서 0부터 i-1번째까지의 원소를 비교하였다. 다음과 같은
문제 11053 가장 긴 증가하는 부분 수열과 조건만 조금 다르고 같았다.언제나 배열을 선언하고 초기화하는 것을 잊지말고 하자.
문제에서 주어진 조건에 따라 두가지 경우를 생각할 수 있다.i번째 해당하는 수만 더하는 경우i-1번째 해당하는 수에 연이어 i번째 해당하는 수를 더하는 경우bottom-up방식을 이용하여i번째 해당하는 수만 더하는 경우와 i-1번째 해당하는 수에 연이어 i번째 해당하는
문제 ![](https://images.velog.io/images/kdmstj/post/18793b36-3032-49eb-930c-c75e5ca6e4b7/%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB
제곱수들은 주어진 자연수 N보다 작아야 하는 조건과 더불어, 현재 dp값보다 작아야 한다.N까지의 dp값을 N을 제곱근으로 가장 길게 표현할 수 있는 11 N, 즉 N으로 초기화하였다.이중 반복문을 사용하여서 i가 N까지 dp를 채우는 동안 j의 제곱근이 i를 초기화지
n-4일때까지 생각했는데,, n-6,n-8,,0이 있을줄이야ㅠㅠ그래도 나름 접근했다..!!
6번째 삼각형부터 i-1번째 삼각형의 변과 i-5번째 삼각형 변을 공유하기 시작한다.즉, 규칙은 다음과 같다.dp0 = dp1 = dp2 = 1dp3 = dp4 = 2dpi = dp i-1 + dpi-5
N = 1일 경우, 정수 K개를 더해서 N이 되는 경우의 수는 다음과 같다. k = 1 -> 1 \- dp1 = 1 k = 2 -> 0 + 1, 1 + 0 \- dp1 = 2 k = 3 -> 0 + 0 + 1, 0 + 1 + 0, 1 + 0 +
N개를 사는 경우 처음에 N개가 들어있는 카드팩을 사는 경우와 N-1개를 가장 비싼 값에 사는 경우(dpN-1)와 1개가 들어있는 카드팩을 사는 경우를 합한 값과(dpN-1 +1) 비교하여 dp값을 정한다.이후 마찬가지로 N-2개를 가장 비싼 값에 사는 경우(dpN-2
문제 문제 풀이 수를 정렬하는 알고리즘 문제는 코드
스택은 후입선출(Last In Frist Out)인 자료구조형이다.자바에서 제공하고 있는 스택 클래스는 Vector클래스를 상속받고 있으며, 메소드는 Vetor클래스와 동일하다.Vector클래스는 list인터페이스를 구현하였기 때문에 다음 문제는 ArrayList로 l
문제는 다음과 같은 경우의 수를 가질 수 있다.여는 괄호('(')가 추가되는 경우 리스트에 추가한다.닫는 괄호(')')가 추가되는 경우 \- 리스트가 비어있을 경우, VPS가 아니므로 NO를 출력한다.리스트가 비어있지 않은 경우,이전 인덱스에 해당하는 원소가 여는 괄
문제는 다음과 같은 두가지 상황이 있다.1\. 열린괄호('(')인 경우열린괄호는 닫힌 괄호와 만나야 하므로 스택에 push한다.닫힌괄호(')')인 경우닫힌 괄호는 두가지 경우를 가질 수 있다.2-1. 배열에서 바로 이전에 열린괄호가 있는 경우레이저이므로 현재 존재하는