Storage Gonie

스티커 문제 - https://www.acmicpc.net/problem/9465 문제요약 2xn 모양으로 놓여진 스티커가 있는데 각각의 스티커는 점수를 가지고 있다. 한장을 뗄 때마다 변을 공유하는 상하좌우의 스티커는 찢어져서 사용할 수 없게된다. 이때 떼어낸 스티커 점수들의 합의 최대값을 출력하시오. 해결 방법 무조건 큰 수부터 뜯어내면 최대합을 만들 수 있을까? 정답은 X 이다. 아래의 2x3 모양의 스티커 예시를 보자. 99 100 99 1 99 1 가장 큰 수인 100을 뜯어내면 합은 100 + 1 + 1 = 102이고, 99를 뜯어낸다고 하면 99 + 99 + 99 = 297이다. 따라서 최대합을 만들기 위해 무조건 큰 수 부터 떼네는 것은 옳지 않다. 위의 이유로 뜯는 순서가 정해져 있지 않..

오르막 수 문제 - https://www.acmicpc.net/problem/11057 문제요약 '오르막 수'는 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. ex) 2234, 3678, 1119 수의 길이 N이 주어졌을 때, '오르막 수'의 개수를 구하는 프로그램을 작성하시오. 출력은 10007로 나눈 나머지 값을 출력하시오. 해결 방법 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N] = "길이가 N인 오르막 수의 개수" 수의 각 자리에는 0 ~ 9가 올 수 있기 때문에 좀 더 세분화 할 수 있도록 2차원 배열로 다음과 같이 정의해준다. D[N][L] = "길이가 N이고 수 L으로 끝나는 오르막 수의 개수" 2. D[N]의 값을 ..

쉬운 계단 수 문제 - https://www.acmicpc.net/problem/10844 문제요약 정수 N이 주어지는데 인접한 자리의 수 차이가 모두 1인 수를 '계단 수' 라고 칭한다. ex) 45656 길이가 N인 계단 수의 개수를 구하고 1000000000로 나눈 나머지를 출력하라. 해결 방법 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N][L] = "L로 끝나는 길이가 N인 '계단 수' 의 개수" - 이전 문제에서는 0 또는 1만 왔는데, 여기는 한 자리에 0~9가 올 수 있기 때문에 1차원으로 문제를 풀 수 없다. 따라서 2차원 배열을 활용하게 된다. 2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다. - 정수 N이 주어지고, 앞에 어떤 조합이..

이친수 문제 - https://www.acmicpc.net/problem/2193 문제요약 2진수에서 다음 두 조건을 만족하면 이친수라고 한다. 1) 0으로 시작하지 않는다. 2) 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열을 갖지 않는다. 위의 조건을 만족하는 N자리 이친수를 구하는 문제 해결 방법1 (1차원 배열) * 기존에 해오던 방법과 새로운 방법이 있는데 두 번째의 새로운 방법이 더욱 와닿는 방법이라고 할 수 있다. 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N] = "N자리 이친수의 개수" 2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다. - 마지막 조합에서 아래와 같은 방법 중 1가지를 선택할 수 있다. case1) N번..

카드 구매하기 문제 - https://www.acmicpc.net/problem/11052 문제요약 카드 N개를 구매하려고 하는데, i개를 묶어서 파는 카드 묶음의 가격이 P[i]일 때, N개를 구매하며 지불할 수 있는 최대금액 구하기 해결방법 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N] = "N개를 모두 구매하며 지불할 수 있는 최대 금액" 2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다. - 정수 N이 주어지고, 앞에 어떤 조합이 존재하고 마지막 조합에서 아래와 같은 방법 중 1가지를 선택할 수 있다. N = O+O+O+...+O+A Case1) 마지막 A에서 1개가 묶어진 것을 지불하고 사는 경우 - 지불할 수 있는 최대 금액은 D[N] = D..

1, 2, 3 더하기 문제 - https://www.acmicpc.net/problem/9095 문제요약 정수 N이 주어지면 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제 해결방법 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N] = "N을 1, 2, 3의 합으로 나타내는 방법의 수" 2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다. - 정수 N이 주어지면 마지막 자리에 3가지 방법 중 1가지를 선택할 수 있다. N = O+O+O+...+O+O+A Case1) 맨 뒤 A자리에 1을 조합으로 추가하는 경우 - 1을 조합으로 추가했으므로 N-1을 1, 2, 3의 조합으로 나타내는 것을 다시 찾아내면 됨. Case2) 맨 뒤 A자리에 2을 조합으로 ..

2xn 타일링2 문제 https://www.acmicpc.net/problem/11727 문제요약 2xn 직사각형을 2x1과 2x2 타일로 채워넣는 모든 방법의 수를 구하고, 이를 10007로 나눈 나머지를 출력해라 해결방법 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N] = "2 x N 직사각형을 채우는 모든 방법의 수를 10007로 나눈 나머지" -> "2 x N 직사각형을 채우는 모든 방법의 수" 로만 일단 생각하자. 2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다. - 2 x N의 직사각형이 주어지면 마지막 위치에 3가지 방법 중 1가지를 선택할 수 있다. Case1) 세로로 1개를 놓는 경우 - 나머지 2 x (n-1) 크기의 직사각형을 채워넣..

2xn 타일링 문제 https://www.acmicpc.net/problem/11726 문제요약 2xn 크기의 직사각형을 1x2, 2x1 타일로 채워넣는 모든 방법의 수를 구하고, 이를 10007로 나눈 나머지를 출력해라 해결방법 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N] = "2 x N 직사각형을 채우는 모든 방법의 수를 10007로 나눈 나머지" -> "2 x N 직사각형을 채우는 모든 방법의 수" 로만 일단 생각하자. 2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다. - 2 x N의 직사각형이 주어지면 마지막 위치에 2가지 방법 중 1가지를 선택할 수 있다. Case1) 세로로 1개를 놓는 경우 - 나머지 2 x (n-1) 크기의 직사각형을 ..

1로 만들기 문제 https://www.acmicpc.net/problem/1463 문제요약 어떤 정수 N에 대해 다음과 같은 연산중 하나를 선택할 수 있다. 1) 3으로 나누어 떨어지면 3으로 나눈다. 2) 2로 나누어 떨어지면 2로 나눈다. 3) 1을 뺀다. 이를 반복하여 1을 만들려고 하는데 연산을 사용하는 횟수의 최소값을 출력해라. 해결방법 - 다른 문제에도 공통적으로 적용됨 1. D[N]에 어떤 값을저장할 것인지 문장으로 정의해줘야 한다. - 대부분의 다이나믹 문제는 문제에서 구하라는 값을 그대로 D[N]에 넣어주면 된다. - 따라서, D[N]= "정수 N을 1로 만드는데 필요한 연산 횟수의 최소값" 이라고 정의해 줄 수 있다. 2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다...

다이나믹 프로그래밍의 개념 # 다이나믹 프로그래밍(DP, Dynamic Programming) - 큰 문제를 작은 문제로 나눠서 푸는 알고리즘, 중복되는 작은 문제가 존재해 이에 대한 결과값을 저장해두어 계산 중복을 없애는 것. - 1940년 Richard Bellman이 단지 이름이 멋있어보여서 사용하게됨. - 한글로 '동적 계획법'이라고 불리는데, 이름은 아무의미없으니 이름에서 뜻을 찾지 말아라. # 위 알고리즘을 이용한 문제해결시 필요한 요소 - 아래의 두가지 전제조건 만족해야함 - 중간 결과값 메모(Memoization)를 위한 '배열'이 필요함 # 이 유형의 문제해결 능력 향상을 위해서 필요한 것 - 어려워 보이지만 패턴을 가지기 때문에 문제들을 많이 풀어보면서 감을 잡는 것이 중요하다. # 다..