제곱수의 합 (실 3) : https://www.acmicpc.net/problem/1699 주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 문제. 난이도는 실버 3인데 골드5인 합분해보다 어려웠고, 헤맸다. 1. 문제 분석 및 접근 최적화문제. 최적 부분 구조를 가지고 있다. 왜냐하면 이전 선택과 현재 선택은 독립적이며, 이전 선택에 관계없이 현재 선택에서 선택의 최솟값만을 도출해내면 되기 때문이다. 또한 그리디하게, 매번 가장 큰 제곱수를 선택하는 방법을 생각했는데, 바로 반례가 나오더라. 예로 들어 n = 32인 경우, 그리디한 접근 : 25 + 4 + 1 + 1 + 1 = 5개 정답 : 16 + 16 = 2개 따라서, 만들어질 수 있는 모든 경우의 수를 살펴 보..

합분해(골 5) : https://www.acmicpc.net/problem/2225 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제. 즉, n = 3, k = 2가 주어지면, (0, 3) (1, 2) (2, 1) (3, 0)의 네 가지 경우의 수를 구할 수 있음. 1. 문제 분석 경우의 수를 모두 구하는 문제니, 최적화 문제는 아님. for문 돌면서 k가 1씩 감소하면서 재귀 호출을 하면 될 것 같음! 2. 완전 탐색 구현 #include using namespace std; int disassemble(int n, int k) { if (k == 0) { if (n) return 0; return 1; } int cnt = 0; for (int num = 0; n + ..

최적화 문제 : ~의 최댓값을 반환하시오, ~의 최소는 무엇인가 등, 최대/최소/최단거리 등을 도출하는 모든 문제. DP는 태생적으로 최적화 문제를 효율적으로 해결하기 위해 태어남. 주의 : 문제가 최적 부분 구조일때 사용하세요!!!! 최적 부분 구조 (optimal substructure) : 지금까지의 선택과 상관 없이, 각 부분 문제를 최적으로 풀었을 시 전체 문제의 최적해를 도출할 수 있는 구조. ex) 서울에서 부산까지 가는 최단 경로. 최단 경로는 항상 대전을 지남. => 부산 ~ 대전까지의 최단경로 (부분문제 최적해) + 대전 ~ 서울까지 최단경로 (부분문제 최적해) = 부산 ~ 서울까지 최단경로 (전체 최적해) 1. 최적해를 찾는 완전 탐색 알고리즘 설계. 2. 함수 반환 값의 정의 변환 ..

https://www.acmicpc.net/problem/1463 1. 문제 분석 연산을 사용하는 횟수의 최솟값을 출력. 즉 최적화 문제. 계속 3 또는 2로 나누면서 숫자를 더 많이 줄여나가면서 끝에 값을 도출하는 그리디한 접근은 불가능함. 문제에서 주어진 10의 예에서 볼 수 있듯이, 만약 그리디한 방식으로 접근할 경우 10 -> 5 -> 4 -> 2-> 1 의 총 네 번이 필요하지만, 최솟값의 경우 10 -> 9 -> 3 -> 1 로 세 번만에 만들 수 있음. 따라서, 모든 경우의 수를 살펴보는 완전 탐색을 채택. 2. 접근 아이디어 연산을 사용하여 최솟값을 도출하는 함수를 oper()라고 했을 때, 다음과 같이 수식화 할 수 있음. oper(n) = min(oper(n / 3), oper(n / ..

1. 기저 사례를 가장 먼저 처리. 입력 범위 벗어난 경우(nx N 등) 포함 2. cache[]를 전부 -1로 초기화. 3. ret는 cache[a][b]의 참조 변수. 즉 ret의 값이 바뀌면, cache[a][b]의 값도 바뀜. 4. memset()을 이용해 cache를 초기화. 하지만, 굉장히 제한적인 경우에만 쓸것! 레시피의 예. #include // memset을 쓰기 위해 include(백준 등에서 쓰기 위함). int cache[2500][2500]; // 2. 전부 -1로 초기화 해둔다. int dpFunction(int a, int b) { if (...) return ...; // 1. 기저 사례를 가장 먼저 처리. int& ret = cache[a][b]; //..

https://www.acmicpc.net/problem/11726 타일 채우기 문제. 타일 채우기 문제들은, DP를 연습할 때 가장 많이 접하는 유형이기도 하다. 1. 문제 분석 가. 문제 분류 타일의 채우는 전체의 경우의 수를 구해야하므로, 완전 탐색 문제. 최적화 문제는 아님. 단순히 전체 경우의 수를 구해 반환하면 됨. 나. 접근 아이디어 2 x n 크기의 직사각형을 채울 경우의 수는 다음과 같이 생각해 볼 수 있음. 2 x n 크기를 채울 경우의 수 = (세로 직사각형 하나 + 2 x n - 1 크기를 채울 경우의 수) + (가로 직사각형 두개 + 2 x n - 2 크기를 채울 경우의 수) 즉, 2 x n 크기를 채울 경우의 수를 리턴하는 함수를 fill(n)이라 했을 시, f(n) = f(n ..

쉬운 문제를 어렵게 풀지 말자. 문제를 접했을 시, 노가다가 가능한지 항상 우선적으로 생각하자. 완전 탐색(exhaustive search, 철저한 검색이라는 뜻.)은 말 그대로 경우의 수를 모조리 찾아보는 탐색법이다. 브루트 포스(한국말로 노가다)라고도 한다. 1. 순열/조합 유형 2. 재귀 함수를 사용하는 유형. (feat 완전 탐색 레시피 : https://sanghoonly.tistory.com/25) 3. 재귀 함수를 사용하지 않는 유형. + 최적화 문제 또한 완전 탐색으로 접근할 수 있다. 사실, 완전 탐색은 최적화 문제를 풀기위한 가장 기초적이고 직관적인 방법인데, 그냥 전부 답을 생성한 다음 그중에서 제일 좋은 것을 골라내면 되기 때문이다. (ex. 외판원 문제) 1. 순열/조합 유형 - ..

1. 완전 탐색 가능 여부 확인 : 주어진 시간안에 모든 경우의 수 확인이 가능한지 체크. 2. 조각 내기 : 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눔. (각 선택은 답의 후보를 만드는 과정의 한 조각.) 3. 부분 문제 해결 : 이 선택 중 한 조각을 선택해 답의 일부를 만들고, 나머지를 재귀 호출을 통해 완성. 4. 기저 사례 작성 : 조각이 하나 또는 하나도 남지 않은 경우를 기저 사례로 선택해 처리. ex) 보글 게임 문제 (https://algospot.com/judge/problem/read/BOGGLE) 1. 주어진 시간안에 모든 경우의 수 탐색 가능한가? 2. 조각 내기 & 답만들기, 재귀 호출 : 각 글자를 하나의 조각으로 만들기. 즉, 현재 글자 == 단어의 글자 ? 재..