1. 동적 계획법(DP)란? - 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 - 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산X - 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 2. DP vs 분할 정복 DP 분할 정복 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨 동일한 부분 문제가 반복적으로 계산되지 X 최적 부분 구조를 가질 때 사용 O (큰 문제를 작은 문제로 나눌 수 있고 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 상황) 3. DP의 2가지 방식 1. Top-Down(하향식) - 재귀 이용 - 메모이제이션 기법 활용 - 한 번 계산한 결과를 메모리 공간에 메모하는 기법(캐싱) - 다이나믹 프로그래밍 구현 기법(하..
[백준] 7579번 - 앱 (한줄평) 전에 풀었던 냅색 문제를 잘 이해했다면 어렵지 않게 해결핧 수 있었던 문제. 하지만 더 좋은 풀이를 생각해봐야할 문제로 다음에 다시 한번 풀어보면 좋을 것 같다. 유사 문제: 12865 https://hseungyeon.tistory.com/search/%EB%83%85%EC%83%89 공부 hseungyeon.tistory.com 앱의 개수가 N, 필요한 메모리가 M일 때, 둘째 줄의 N개의 정수는 현재 활성화 되어 있는 앱 A1, ..., AN이 사용 중인 메모리의 바이트 수인 m1, ..., mN을 의미하며, 셋째 줄의 정수는 각 앱을 비활성화 했을 경우의 비용 c1, ..., cN을 의미한다 (단, 1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000,000이며,..
[백준] 1562번 - 계단 수 (한줄평) 간단하다고 생각했지만 0부터 9까지 숫자가 모두 등장했는지 확인하기 위한 아이디어를 떠올리기 어려웠던 문제였다. 비트 마스킹을 이용한 DP 문제 유사 문제: 10844 https://hseungyeon.tistory.com/302 [다이나믹 프로그래밍] 10844번 - 쉬운 계단 수 [백준] 10844번 - 쉬운 계단 수 (한줄평) 생각보다 빨리 아이디어가 떠올라 쉽게 풀 수 있었던 문제! 2차원으로 접근해야한다는 것을 깨달으면 쉽게 풀 수 있다. 한번쯤 복습해보면 좋을 것 같은 hseungyeon.tistory.com 인접한 모든 자리의 차이가 1인 수를 계단 수라고 한다. 0으로 시작하는 수는 계단수가 아니다. 수의 길이 n이 주어질 때 0~9까지 숫자가 모..
[백준] 2293번 - 동전 1 (한줄평) 오랜만에 풀었더니 dp 문제 감을 잃었다고 느꼈다. 한 끝차이로 계속 틀린 이유을 찾지 못했던 문제.. 다음에 다시 풀어봐야할 것 같다 풀이 시간: 60분 이내 n가지 종류의 동전을 사용해서 가치의 합이 k원이 되는 경우의 수를 구하는 문제다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. (풀이1) 틀린 풀이 1) 문제 해결 아이디어 점화식을 세우기까지는 오랜시간이 걸리지 않았으나 그걸 코드로 구현하는 과정에서 잘못 생각한 부분이 있어서 어려움을 겪었다. 2) 소스코드 import sys input = sys.stdin.readline n, k = map(int, input().split()) # 동전 종류, 가치의합 graph = [int(..
[백준] 2629번 - 양팔 저울 (한줄평) 생각보다 머리가 복잡했던 문제.. 점화식을 만들기가 어려웠다.. 무조건 복습필수다 풀이 시간: 90분 이내 1) 문제 해결 아이디어 추의 개수 n(30 이하), n개의 추의 무게(500이하의 자연수)가 오름차순으로 주어지고 구슬의 개수 m(7이하), m개의 구슬의 무게(40000 이하의 자연수)가 주어진다. 양팔 저울에 추를 사용하여(올리거나 올리지 않을 수 있음) 주어진 m개의 각 구슬의 무게를 확인할 수 있는지 여부를 구하는 문제다. 각 추를 사용할 때 3가지 경우의 수가 있다. 즉, 추의 개수가 n이면 추를 이용하여 구할 수 있는 모든 경우의 수는 3**n이 된다. n의 값이 최대 30이므로 단순하게 완전 탐색을 한다면 이 문제는 시간초과로 풀 수 없게된..
[백준] 10942번 - 팰린드롬? (한줄평) 아이디어는 빨리 떠올렸지만 코드 짜는게 생각보다 오래걸렸던 문제다. 대각선 순서로 확인하는 코드 그냥 외우자.. 이상한데서 시간 낭비했다.. 풀이 시간: 75분 이내 1) 문제 해결 아이디어 크기가 n인 수열과 m개의 시작점, 끝점(s, e)가 주어질 때 각 질문에 대한 팰린드롬 여부를 구하는 문제다. 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다. (1 ≤ N ≤ 2,000, 1 ≤ N ≤ 2,000, 1
[백준] 11049번 - 행렬 곱셈 순서 (한줄평) 이전에 풀었던 문제와 풀이 방식이 비슷해서 풀 수 있었지만 다음에 다시 풀면 못 풀 것 같기도 한 문제.. 복습이 꼭 필요하다! 유사 문제: 11066 https://hseungyeon.tistory.com/313 [다이나믹 프로그래밍] ★★ 11066번 - 파일 합치기 [백준] 11066번 - 파일 합치기 (한줄평) 풀릴듯 하면서 풀리지 않아서 풀이를 보니 생각보다 더 복잡한 문제였다. 풀이를 봐도 쉽게 이해가 가지 않았기때문에 꼭 복습이 필요하다! 풀이 시간: 3 hseungyeon.tistory.com 풀이 시간: 60분 이내 1) 문제 해결 아이디어 n개의 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 구하는 문제다. 이 문제의 핵심은 대각선방향으..
[백준] 11066번 - 파일 합치기 (한줄평) 풀릴듯 하면서 풀리지 않아서 풀이를 보니 생각보다 더 복잡한 문제였다. 풀이를 봐도 쉽게 이해가 가지 않았기때문에 꼭 복습이 필요하다! 풀이 시간: 3시간 이내 1) 문제 해결 아이디어 소설을 구성하는 장의 수(k)와 k개의 파일의 크기(f)가 주어졌을 때 모든 장을 합치는데 필요한 최소 비용을 구하는 문제다. 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산해야한다...
