오늘은! 여유롭게 쉬면서 힐링할 생각이다. 빡세게 백준 문제 풀면서 스트레스 받은 나에 대한 보상이라고 할까나. 이러면서 또 문제 풀겠지? 방중에는 요리와 운동을 꾸준히 할까도 생각 중이다. 운동은 거의 매일 하고, 요리도 중간중간 배울듯? 7월 목표를 수정할 예정이다. 원래는 2주차에 DP -> 3주차 그래프 탐색 순으로 가려 했는데, 생각보다 DP가 어렵기도 하고, 재귀와 완전 탐색이 알고리즘에서 기본이라는 생각도 많이 들었고, 무엇보다 요즘들어 손에 문제가 잘 안잡히기도 해서... 그래서 7월 중으로는 알고리즘 기본인 완전 탐색과 재귀에 시간을 많이 들여야겠다는 생각이 들었다. 사실 그래프 탐색도 잘 보면 완전탐색이랑 접근법이 거의 유사하다. 같은 문제라도, 완전 탐색으로도 풀 수 있고 그래프 탐색..

DP 쉬운 계단 수 (실 1) : https://www.acmicpc.net/problem/10844 이친수 (실 3) : https://www.acmicpc.net/problem/2193 가장 긴 증가하는 부분 수열 (실 2) : https://www.acmicpc.net/problem/11053 완료! 자바의 신 3, 4, 5장 읽기 비가 안오다가도 오는 하루. 집중도 되다가도 안되는 하루. 종일 방에서 DP 문제를 풀었다. 집중되면 또 문제를 풀고, 안되면 안되는 대로 놀고. 날씨가 우중충해서 그런지, 오늘따라 마음도 그렇다. 머리와 마음은 다르다. 이성적으로 이해가고, 머리로 수십번 납득하지만, 마음은 아니라고 한다면 어쩌겠어. 이럴 경우 나에 대한 최대한의 배려는, 기다려주는 것이다. 비워진 것..

1. 종만북 : ~ 경우의 수와 확률 앞까지 2. DP 문제 카드 구매하기 (실 1) : https://www.acmicpc.net/problem/11052 카드 구매하기2 (실 1) : https://www.acmicpc.net/problem/16194 쉬운 계단 수 (실 1) : https://www.acmicpc.net/problem/10844 3. 자바의 신 ~3단원까지 4. DP 문제 푼거 블로그에 올리기

1. 종만북 DP, DP 테크닉 부분 읽기(8장, 9장) 2. 백준 DP 문제 풀기 맞춰봐 (골드 3) : https://www.acmicpc.net/problem/1248 (완전 탐색) 1로 만들기 (실 3) : https://www.acmicpc.net/problem/1463 2 X n 타일링 (실 3) : https://www.acmicpc.net/problem/11726 카드 구매하기 (실 1) : https://www.acmicpc.net/problem/11052 카드 구매하기2 (실 1) : https://www.acmicpc.net/problem/16194 쉬운 계단 수 (실 1) : https://www.acmicpc.net/problem/10844 이친수 (실 3) : https://ww..

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. 순열/조합 유형 - ..