'알고리즘/다이나믹 프로그래밍' 카테고리의 글 목록 (3 Page)

integer partition 문제 3 - 서로 다른 자연수를 사용해서 특정한 자연수 n을 만드는 방법의 수는 홀수만을 사용해서 만드는 방법의 수와 같다(count number of partition of n)

1. 문제 9764번: 서로 다른 자연수의 합 (acmicpc.net) 9764번: 서로 다른 자연수의 합 첫째 줄에, 테스트 케이스의 개수 T (1 ≤ T ≤ 20)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. www.acmicpc.net 2. 풀이 dp[j][i]를 1부터 i까지의 자연수 중에서 최대 하나씩만 사용해서 j를 만드는 방법의 수라고 정의하자. 여기서 구성이 같은데 순서가 달라도 같은 방법으로 취급한다 https://deepdata.tistory.com/951 합이 k가 되는 경우의 수 구하는 다이나믹 프로그래밍 익히기(구성이 같은데 순서가 다르면 같은 1. 문제 9095번: 1, 2, 3 더하기 (acmicpc.net) 9095번: 1, 2, 3 더하기 각 테..

integer partition 문제 2 - m개 이하의 수만 사용해서 합이 k가 되도록 만드는 경우의 수 구하는 다이나믹 프로그래밍

1. 문제 15992번: 1, 2, 3 더하기 7 (acmicpc.net) 15992번: 1, 2, 3 더하기 7 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 단, 사용한 수의 개수는 m개 이어야 한다. www.acmicpc.net 2. 풀이 저번엔 사용 개수의 제한 없이 합을 n으로 만드는 방법을 배웠다면.. https://deepdata.tistory.com/951 합이 k가 되는 경우의 수 구하는 다이나믹 프로그래밍 익히기(구성이 같은데 순서가 다르면 같은 1. 문제 9095번: 1, 2, 3 더하기 (acmicpc.net) 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 ..

integer partition 문제1 - 합이 k가 되는 경우의 수 구하는 다이나믹 프로그래밍 익히기(구성이 같은데 순서가 다르면 같은 경우로 세는 방법, 다른 경우로 세는 방법)

1. 문제 9095번: 1, 2, 3 더하기 (acmicpc.net) 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 2. 풀이 정수 n을 1,2,3만 사용해서 만드는 방법의 수를 구하는 문제 1) 여기서 1,2,3은 중복해서 사용 가능하다 2) 동일하게 사용해도 순서가 다르면 다르다고 취급한다. 즉 1+1+2와 1+2+1은 다른 경우이다. dp[n]을 n을 만드는 방법의 수로 정의하고, 일단 n이 11보다 작기 때문에 dp의 크기를 11까지 잡아준다. n을 만들려면 어떻게 해야할까? 1,2,3만 사용할 수 있기 때문에 3가지 경우가 가능하다. 1) n-1에서 1을 더하면 n n-1을 만드는 방법의 수 dp..

다이나믹 프로그래밍+BFS+그리디 - 정확히 K번만에 목표에 도달할 수 있는가?

1. 문제 28069번: 김밥천국의 계단 (acmicpc.net) 28069번: 김밥천국의 계단 첫 번째 줄에 계단 개수에 해당하는 $N$, 계단을 오르는 횟수 $K$가 주어진다. $(1 \leq N, K \leq 1\,000\,000)$ www.acmicpc.net 2. 풀이1 그냥 보면 두가지 행동중 하나를 할 수 있는 전형적인 BFS문제 1) 한칸을 올라간다 2) $\left \lfloor \frac{i}{2} \right \rfloor$만큼 올라간다 0번부터 시작한다고 명시되어 있으니 BFS처럼 풀어보면.. 정확히 K번 행동해야하면서 매 행동마다 queue의 길이만큼 순회시키는데 해당 좌표 i가 i+1과 i+i//2를 이동할 수 있으면 queue에 넣어주고.. K번 행동한 후에 n이 queue에 ..

배열에 수가 추가될때마다 원소간 차이의 최댓값 구하기

1. 문제 25214번: 크림 파스타 (acmicpc.net) 25214번: 크림 파스타 각 $A_i$가 추가된 직후의 문제의 답 $N$개를 공백으로 구분하여 출력한다. www.acmicpc.net 2. 풀이 그냥 단순하게 생각해서 배열 원소의 최댓값과 최솟값을 기억해두고, n개의 원소를 처음부터 순회해서, A[i]가 최대인지 검사하고 최대라면 최댓값을 갱신한다음에, dp[i]에 최댓값 - 최솟값을 넣어주면 되는거 아녀? 새로 들어온 값이 최댓값이 아니라면, dp[i]는 이전에 구한 dp[i-1]과 같을거고 최댓값이 아닌 경우에 당연히 A[i]가 최솟값이 될 자격이 있으니까 A[i]가 최솟값인지 검사하고 A[i]가 최솟값이라면 최솟값을 갱신해준다 여기서 $i \leq j$인 i,j에 대하여 A[j..

시간 다이나믹 프로그래밍 기본 문제 틀리기 쉬운 점 복기하면서 재활

1. 문제 19947번: 투자의 귀재 배주형 (acmicpc.net) 19947번: 투자의 귀재 배주형 2020년에 학교로 복학한 주형이는 월세를 마련하기 위해서 군 적금을 깨고 복리 투자를 하려고 한다. 주형이가 하려는 투자에는 3가지 방법의 투자 방식이 있다. 1년마다 5%의 이율을 얻는 투자 ( www.acmicpc.net 2. 풀이 아주 기본적인? 다이나믹 프로그래밍.. 근데 어떻게 하는건지 잠깐 기억이 안났었다는게 함정 dp를 길이가 y+1인 배열 [0]*(y+1) 초기화할테고 dp[0] = h여서.. y년 후의 금액이 dp[y]라고 해서.. 1년,3년,5년 투자 방식중 최댓값을 골라 dp에 저장할텐데 이거 어떻게 하더라... 잠깐 정적.. ------------------------------..

통계학 세상

통계학 세상

통계학 세상

integer partition 문제 3 - 서로 다른 자연수를 사용해서 특정한 자연수 n을 만드는 방법의 수는 홀수만을 사용해서 만드는 방법의 수와 같다(count number of partition of n)

integer partition 문제 2 - m개 이하의 수만 사용해서 합이 k가 되도록 만드는 경우의 수 구하는 다이나믹 프로그래밍

integer partition 문제1 - 합이 k가 되는 경우의 수 구하는 다이나믹 프로그래밍 익히기(구성이 같은데 순서가 다르면 같은 경우로 세는 방법, 다른 경우로 세는 방법)

다이나믹 프로그래밍+BFS+그리디 - 정확히 K번만에 목표에 도달할 수 있는가?

배열에 수가 추가될때마다 원소간 차이의 최댓값 구하기

시간 다이나믹 프로그래밍 기본 문제 틀리기 쉬운 점 복기하면서 재활

카테고리

블로그메뉴

공지사항

최신글

최신댓글

글 보관함

링크

방문자수

티스토리툴바

integer partition 문제 3 - 서로 다른 자연수를 사용해서 특정한 자연수 n을 만드는 방법의 수는 홀수만을 사용해서 만드는 방법의 수와 같다(count number of partition of n)

integer partition 문제 2 - m개 이하의 수만 사용해서 합이 k가 되도록 만드는 경우의 수 구하는 다이나믹 프로그래밍

integer partition 문제1 - 합이 k가 되는 경우의 수 구하는 다이나믹 프로그래밍 익히기(구성이 같은데 순서가 다르면 같은 경우로 세는 방법, 다른 경우로 세는 방법)

다이나믹 프로그래밍+BFS+그리디 - 정확히 K번만에 목표에 도달할 수 있는가?

배열에 수가 추가될때마다 원소간 차이의 최댓값 구하기

시간 다이나믹 프로그래밍 기본 문제 틀리기 쉬운 점 복기하면서 재활

카테고리

블로그메뉴

공지사항

최신글

태그 클라우드

최신댓글

글 보관함

링크

방문자수

티스토리툴바