1. 동적 계획법(DP)란? - 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 - 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산X - 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 2. DP vs 분할 정복 DP 분할 정복 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨 동일한 부분 문제가 반복적으로 계산되지 X 최적 부분 구조를 가질 때 사용 O (큰 문제를 작은 문제로 나눌 수 있고 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 상황) 3. DP의 2가지 방식 1. Top-Down(하향식) - 재귀 이용 - 메모이제이션 기법 활용 - 한 번 계산한 결과를 메모리 공간에 메모하는 기법(캐싱) - 다이나믹 프로그래밍 구현 기법(하..
[백준] 1562번 - 계단 수 (한줄평) 간단하다고 생각했지만 0부터 9까지 숫자가 모두 등장했는지 확인하기 위한 아이디어를 떠올리기 어려웠던 문제였다. 비트 마스킹을 이용한 DP 문제 유사 문제: 10844 https://hseungyeon.tistory.com/302 [다이나믹 프로그래밍] 10844번 - 쉬운 계단 수 [백준] 10844번 - 쉬운 계단 수 (한줄평) 생각보다 빨리 아이디어가 떠올라 쉽게 풀 수 있었던 문제! 2차원으로 접근해야한다는 것을 깨달으면 쉽게 풀 수 있다. 한번쯤 복습해보면 좋을 것 같은 hseungyeon.tistory.com 인접한 모든 자리의 차이가 1인 수를 계단 수라고 한다. 0으로 시작하는 수는 계단수가 아니다. 수의 길이 n이 주어질 때 0~9까지 숫자가 모..
[백준] 10942번 - 팰린드롬? (한줄평) 아이디어는 빨리 떠올렸지만 코드 짜는게 생각보다 오래걸렸던 문제다. 대각선 순서로 확인하는 코드 그냥 외우자.. 이상한데서 시간 낭비했다.. 풀이 시간: 75분 이내 1) 문제 해결 아이디어 크기가 n인 수열과 m개의 시작점, 끝점(s, e)가 주어질 때 각 질문에 대한 팰린드롬 여부를 구하는 문제다. 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다. (1 ≤ N ≤ 2,000, 1 ≤ N ≤ 2,000, 1
[백준] 1520번 - 내리막 길 (한줄평) 오랜만에 dp 문제플 풀었더니 약간 헤맸던 문제다. dp와 dfs를 한 번에 쓰는 문제는 처음이라 낯설었던 것 같기도 하다. 꼭 복습이 필요한 문제! 풀이 시간: 60분 이내 1) 문제 해결 아이디어 n * m의 지도의 높이 정보가 주어지고 지금보다 높이가 더 낮은 곳으로만 이동하여 (0, 0)에서 (n-1, m-1)까지 이동 가능한 경로의 수를 구하는 문제다. 이 문제는 DFS + DP 를 이용하여 풀 수 있는 문제다. 오로지 DFS로만 풀려고 한다면 가능한 모든 경로의 수를 다 세야하기 때문에 아마 시간초과가 날 것이다. n, m의 범위가 1이상 500이하이기 때문이다. DFS와 DP를 이용하여 풀어야한다는 것은 알았는데 점화식을 잘못세워서 헤맸다. 처음에..
[백준] 12865번 - 평범한 배낭 (한줄평) 냅색 문제인지 모르고 풀었던... 생각보다 더 어려웠던 문제로 복습이 꼭 필요하다!!! 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. N개의 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 구하는 문제다. 이 문제는 전형적인 냅색 문제다. 1. 분할가능 배낭 문제(Fractional Knapsack Problem) 담을 수 있는 물건이 나누어질 때(설탕 몇 g) - 물건의 가격을 무게로 나누어 무게 대비 가격이 비싼 순서로 물건을 정렬해서 넣으면 쉽게 해결이 가능! - 배낭이 감당할 ..
[백준] 9461번 - 파도반 수열 (한줄평) 손으로 직접 쓰면서 규칙을 알아냈던 문제! 하나씩 다 해보다보면 규칙이 보기도한다는 것을 꺠닫게 되었다! 풀이 시간: 20분 이내 1) 문제 해결 아이디어 첫 정삼각형의 변의 길이는 1이고 나선 모양으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 떄, 그 변에 길이가 k인 정삼각형을 추가한다. 이러한 행위를 반복 했을 때 나선에 있는 정삼각형의 변의 길이 p(n)을 구하는 문제다. 이 문제는 직접 하나하나 써보면서 규칙을 찾을 수 있는 문제였다. Q. dp테이블을 전연변수로 선언하고 입력을 받기전에 100까지 계산을 하는 이유는? 사실 n을 입력받고 나서 p(n)값을 계산해도 상관 없지만 테스트 케이스가 2이상일 경우에 기록된 값에 ..
[백준] 1904번 - 01타일 (한줄평) 아이디어는 쉽게 떠올렸으나 오류를 고치는데 시간이 걸렸던 문제! 나중에 다시 한 번 풀어봐야할 것 같다 (풀이1) 틀린 코드 풀이 시간: 20분 이내 1) 문제 해결 아이디어 1이상 1000000이하인 길이 n인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 구하는 문제다. 첫번째 오류. 메모리 초과 dp테이블의 크기를 n만큼 생성했는데 최대값이 1000000인 탓에 메모리 초과가 난 것 같다. 그래서 리스트를 사용하지 않고 값 2개를 저장할 수 있는 변수 2개(a, b)를 생성하여 문제를 해결했다. 두번째 오류. 시간초과 1%까지 되다가 시간초과가 났다. 15746으로 나눈 나머지를 출력시켜야 하는데 그냥 그 값을 출력시키도록해서 생긴 문제였다. 세번째..
[백준] 2749번 - 피보나치 수 3 (한줄평) 메모리 초과를 해결하지 못해 다른 사람의 풀이를 참고한 문제! 아예 생각조차 하지 못한 방식으로 해결이 가능하다... 답을 안봤으면 절대 못풀었을 문제^^; 유사 문제: 2747, 2748 https://hseungyeon.tistory.com/294 [다이나믹 프로그래밍] 2747번 - 피보나치 수, 2748번 - 피보나치 수 2 [백준] 2747번 - 피보나치 수, 2748번 - 피보나치 수 2 (한줄평) 다이나믹 프로그래밍으로 해결할 수 있었던 문제! 2가지 문제는 n번째 피보나치수를 구하는 문제로 두 문제의 차이는 n의 범위다 hseungyeon.tistory.com 이 문제는 n이 1,000,000,000,000,000,000이하의 자연수 일 때..
