가장 긴 증가하는 부분 수열 (실 2) : https://www.acmicpc.net/problem/11053 가장 긴 증가하는 부분 수열 4 (골 4) :https://www.acmicpc.net/problem/14002 DP에 관하여 워낙 유명한 문제. 여기서는 LIS를 실제로 출력하는 코드를 위주로 살펴본다. 1. (일반적인) 최대 증가 부분 수열의 길이 반환 #include #include #include using namespace std; int N, A[1001], cache[1001]; int lis(int start) { int &ret = cache[start + 1]; if (ret != -1) return ret; ret = 1; for (int i = start + 1; N > i..

1. 재귀 호출의 각 단계에서 최적해를 만들었던 선택을, 별도의 배열에다 저장. 2. 별도의 재귀 함수를 구현해 이 선택을 따라가며 각 선택지를 저장하거나 출력. 예) LIS에서 LIS 복원하기 : https://sanghoonly.tistory.com/45 -> 1. 최적 선택을 기록하는 choices 배열 생성 후, 2. reconstruct 함수로 choices함수의 값을 이용해 lis 복원.

제곱수의 합 (실 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 + ..

1. 자바 1권 완독 2. 종만북 9장까지 완독 3. (금요일부터 주말까지) 구글 maps api 정리 4. DP문제 계속해서 풀기 크게 추가된 건 없고, 저번주의 연장선이다. 자바는 꼭!! 해야 한다. 다른 건 조금 늦춰져도 큰 타격이 없지만, 자바 1,2 권은 7월 내로 무조건 완독을 해야한다. 홧팅홧팅!!

오늘은! 해야 할게 좀 있네. 1. lis 문제 마무리 (이젠 끝낼 때가 되었다!) 2. 자바 3 ~ 5 (무조건 해야됨) 3. 종만북 경우의 수와 확률 자바 할 때가 되었다!!!!!!!!!! 홧팅홧팅~!! 1. lis 문제 => 좀만 더 홧팅...!!! 거의 다 풀었음 2. 자바 3 ~ 5 => 완료 3. 종만북 경우의 수와 확률 => 내일부터 고고고 lis문제 잡고 있느라 못봄 오늘은 상민이랑 동성로 가서 쇼핑하고 맛있는 거 먹고 재밌게 시간을 보냈다. 수도권은 확진자때매 난리인데, 그에 반해 대구는 아주아주 평화로웠다. 오늘 대구 확진자 22명이었나...?? 이것도 평소보다는 많아진 거라 하더라. 그래서 동성로는 북적북적했다. 오늘은 인형뽑기 성공!!!! 상민이가 큰 인형 두 개 뽑았다. 마 좀 뽑..

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

오늘은! 문제 하나 풀고, 일주일간 DP 학습한 내용 정리해서 저녁에 모각쓰할 때 정리해서 올릴 예정이다. 1. 가장 긴 증가하는 부분 수열 4 (골 4) :https://www.acmicpc.net/problem/14002 요 문제! 도전!! 설거지 5인분을 3번에 걸쳐 하니까 빡세다. 4인분까지는 괜찮았는데, 5인분은 확실히 빡세더라...ㅋㅋㅋㅋㅋ 진짜 약간 일하는 느낌? 일찍 일어나 카페와 집을 왔다갔다하며 문제와 씨름한 하루. 쉬다 오니까 집중이 좀 되는 구만. 밤에는 모각쓰 때 최적화 DP 레시피를 정리해서 올렸다. 가장 긴 증가 부분 수열 문제는, 접근하는 방식이 어렵다. 재귀함수 파라미터에 벡터를 넣어주자니 너무 복잡해 질 것 같고, 아예 이차원 벡터를 만들어야 하나라는 생각도 들었고... ..