#11659 구간 합 구하기4 #11660 구간 합 구하기5 #11659 구간합4 Idea 구간 합 구하기 문제의 핵심은 누적합을 Memoization 기법을 사용하여 해결하는 것이다 N과 M이 최대 100,000이기 때문에 그냥 for문을 돌려서 찾을 경우 최악의

\[처음 칸에서 상하좌우 이웃한 곳을 탐색해서 제일 아래 칸으로 내려간다는 점에서 dfs를 이용해 풀어야 한다는 것을 알 수 있다처음에 dfs만을 이용해 풀었다가 시간 초과가 났다. map의 크기가 최대 500\*500이므로 완전탐색 dfs 방법으로 풀면 최악의 경우

K원을 만드는데 필요한 동전 개수의 최솟값을 만들기 위해서는 동전의 가치가 큰 동전부터 사용해야 한다동전의 가치가 큰 동전부터 사용하다가 K원에서 현재 동전을 뺐을 때, 0보다 작아진다면 다음으로 가치가 큰 동전을 사용한다using namespace std;int N,

\[참고n가지 종류의 동전을 사용하여 k원을 만드는 경우의 수를 구하는 문제 (순서만 다른 경우는 같은 경우이다)dp\[a]=b일 때, a원을 만드는 방법은 b개이다 라고 정했을 때우선 dp\[0]=1이다. 0원을 만드는 방법은 하나도 선택하지 않는 경우로, 이 경우를

\[\[마지막 계단/포도주를 골라야 한다는 조건 빼고는 본질적으로 동일한 문제다이 문제를 정확하게 이해하는데 이틀이 걸렸다..계단 오르기를 예시로 들면dp\[i]=i번째 계단을 밟았을 때 얻을 수 있는 최대 점수로 두고 점화식을 도출해본다(각 계단에 적혀있는 점수는 s

\[참고1 참고2문제를 보자마자 이건 dp로 풀어야겠다.. 는 알겠는데 그 이후 풀지를 못한다.. dp문제를 많이 풀었는데 아직도 잘 못하냐.. 그냥 열심히 더 풀어보는 수밖에 ㅠㅠN일 동안 매일 상담에 필요한 시간과 수익이 하나씩 주어진다예를 들어 1일에 잡혀있는 상

\[풀이 1먼저 보고 바로 dp로 풀어야겠다고 생각했고dp\[i]\[j]=a\[i] 부터 a\[j] 까지의 합으로 설정했다.(자꾸 dp, bfs, dfs문제 들을 풀다보니 이런 문제도 그런 알고리즘으로 풀어야겠다고 생각한다 ㅠㅠ)e.g. n=10 m=5 a={1,2,3

\[참고dp\[x]\[y] =file\[x]에서 file\[y]까지 합치는데 드는 최소비용마지막에 구해야 하는 것은 dp\[1]\[K]가 된다sum\[x]은 file\[1]부터 file\[x] 까지의 부분합이다.sum\[x]=sum\[x-1]+file\[x] 이다.예를

\[Palindrome회문(回文) 또는 팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다.(참고: 위키피디아)이

dp에서 이런 비슷한 유형의 문제를 풀어본 기억이 있어서 dp로 풀어야 겠다고 생각했다. 일단 int dp\[]에서 dp\[i]가 의미하는 것은 jump\[i]에서 가장 오른쪽 끝으로 갈 수 있을 때까지 해야하는 최소 jump의 개수다. 그렇다면 마지막에 구해야 할 값

\[각 정점에서 최대로 가져올 수 있는 사탕의 개수를 구해서 (n,m)까지 이르렀을 때 저장된 최댓값을 return 하면 된다. 사탕의 개수는 (1,1)부터 (n,m)까지 저장되어 있기 때문에 위에서 부터 top-down 방식으로 memoization 기법을 사용한다.

\[문제는 1,2,3 을 이용하여 정수 n을 만드는 방법을 나타내는 개수를 구하는 것이다.주의할 점은 4를 만들 때, 2+1+1, 1+2+1, 1+1+2 는 모두 같은 것으로 취급한다. 여기서 한가지 생각해야 할 점은 이 순서를 오름차순이나 내림차순으만 나타낸다.여기에

문제는 N과 number가 주어질 때 N과 사칙 연산만 사용해서 표현할 수 있는 방법 중 N 사용횟수의 최솟값을 구하는 문제이다. e.g. N=5, number=12인 경우12=5+5+(5/5)+(5/5) ->6개12=55/5+5/5 ->5개12=(55+5)/5 ->4

구하고자 하는 것은 세로 단조 폴리오미노이다. 세로 단조 폴리오미노가 되려면 각 가로줄에 포함된 정사각형은 항상 일렬로 연속해 있다. 첫 줄에 i개의 정사각형이 속한 폴리오미노의 개수는 나머지 n-i개로 구성된 정사각형들로 폴리오미노를 만든 뒤, 이들을 적절히 맨 윗

먼저 비대칭 타일링 문제를 풀기 위해서는 앞에서 공부했던 타일링 방법의 수 세는 알고리즘을 복습할 필요가 있다.2xn 사각형을 채우는 방법들은 맨 오른 쪽이 어떻게 채워져 있느냐로 나눌 수 있다. a는 마지막 타일의 가로길이가 1인 경우, b와 c는 마지막 타일의 가로

확률과 경우의 수는 밀접한 관련이 있기 때문에 많은 경우 확률을 계산하는 문제에도 동적 계획법을 써먹을 수 있다. 먼저 책의 예제에서 각 날짜에 비가 올 확률이 정확히 50%라고 가정할 때, m일 안에 달팽이가 우물 끝까지 올라갈 확률을 먼저 본다. m일 간 비가

먼저 삼각형 위의 최대 경로 갯수를 세기 위해서는 최대 경로를 푸는 알고리즘을 먼저 짜야한다. (y,x) 의 위치에서 바로 아래 숫자 혹은 오른쪽 아래 숫자로 내려갈 수 있기 때문에 (y+1, x)와 (y+1, x+1) 중에 큰 숫자를 찾아 더해서 내려가면 된다.

밑에 그림처럼 n x n 크기의 격자에 1부터 9까지 정수를 쓴 게임판이 있다. 이 게임의 목적은 게임판의 왼쪽 위 칸에서 시작해 게임파의 맨 오른쪽 아래 칸에 도착하는 것이다. 각 칸에 적혀 있는 숫자만큼 아래쪽이나 오른쪽으로 이동할 수 있다.코드 8.4기저사례: 게

앞에서 LIS 문제는 많이 다뤘다. 하지만 이번에 다룰 내용은 더 심화된 JLIS 문제이다. 근데 책에서는 난이도가 하 라고 되어있다..하하..예를 들어 '1 3 4 7 9'은 '1 9 4'와 '3 4 7'의 JLIS이다. 문제는 정수 수열 A, B가 주어질 때 JLI

이 문제는 앞에서 풀었던 RGB문제와 흡사하게 풀 수 있다.먼저 동물원의 크기가 가로2 세로1인 경우를 생각해본다.사자를 한 마리도 배치하지 않는 경우 + 왼쪽 우리에 배치하는 경우 + 오른쪽 우리에 배치하는 경우= 총 3가지가 있다.다음 동물원의 크기가 가로2 세로2