welcome!

백준 2133 타일채우기 해설 흥미로운 문제이다. 정답을 미리 알거나 스포일링 당하는건 괴롭지만, ... 생각해나갈 때는 알쏭달쏭한 즐거운 문제였을 것이다.(구현문제보단 재밌는듯) 가로 길이 2 인 것을 만드는 경우의 수는 3가지이다. ( ||_ ),( _|| ), ( _ _ _ )이다. 임의의 길이 i를 만드는 데에는 i-2 길이를 만드는 경우의 수에 3가지 경우의 수를 조합하는 것이므로, f(i) = f(i-2)*2 이다. 그리고, 길이 4 이상부터 다음과 같은 형태를 만들 수 있다. 이러한 형태는 4, 6, 8, ... i 길이 만큼 만들 수 있고, 뒤집은 형태도 있기 때문에 각 길이마다 2가지의 경우의 수가 있다. 이를 종합하면 i를 만드는 경우의 수는 다음과 같다. f(i) = f(i-2)*2 ..

백준 14494 다이나믹이 뭐에요? 해설 n*n의 2차원 공간에서 오른쪽, 아래쪽, 우아래 대각 세 방법만 이용하여 이동한다고 하자. 이때 임의의 점 (x, y)에 도달 할 수 있는 경우의 수 f(x, y)는 f(x-1,y) + f(x, y-1) + f(x-1, y-1)이다. d배열을 1칸 크게 잡는다면 특별히 배열 range-exception 처리를 할 필요 없이 온전하게 연산에만 집중할 수 있다. #include #define MOD ((int)1e9+7) using namespace std; int d[(int)1e3+1][(int)1e3+1]; int main() { int n, m; cin >> n >> m; d[0][0] = 1; for (int i=1; i

백준 1463 1로 만들기 해설 Queue를 이용하여, 임의의 n 에서 1 까지의 이동하는 것을 구현하여서 최단경로 길이를 구할 수 있다. (BFS) 하지만 문제를 뒤집어서 생각해보면, n에서 1까지의 최단경로 길이는 다음 세개 중 하나이다. n/2 에서 1까지 가는 최단경로 길이 + 1 n/3 에서 1까지 가는 최단경로 길이 +1 n-1 에서 1까지 가는 최단경로 길이 + 1 아래는 memoization을 이용하여 문제를 해결한 소스코드이다. ````C++ #include #include #include using namespace std; int d[(int)1e6+1]; int go(int cur) { if ( cur = 0) return d[cur]; d[cur] = 1e9; if ( cur%2 ..

문제보러가기https://www.acmicpc.net/problem/15483 문제 정의문자열 A와 B가 있다.A를 어떠한 동작을 통해 B와 같게 만들려고 한다. 이 때 최소한의 동작 횟수를 구하시오. 각 순간마다 세가지의 선택을 할 수 있다.- 1 삽입- 2 삭제- 3 교체 이 문제를 어떻게 해결할 수 있을까? 이 문제의 접근법은 모든 가능성을 탐색하는 것이다.재귀를 이용하여 두 문자열의 다름 정도의 비교를 할 수 있다. String S1 의 i 인덱스, S2 의 j 인덱스를 다름을 비교하여, 만약 같다면 다음 비교 스테이지인 S1의 i+1, S2의 j+1로 넘어간다. 만약 다르다면, S1에게 3가지 동작을 수행할 수 있다.삭제, 더하기, 교체 이다.만약 삭제하는 경우 다음 비교 스테이지인 S1의 i+..

백준 15991 1, 2, 3 더하기 - 6문제 보러가기 https://www.acmicpc.net/problem/15991 문제정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 합은 대칭을 이루어야 한다.1+1+1+11+2+12+2정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 경우의 수 문제이다. 이 문제를 푸는데 무려 2달 이나 걸렸다. 2달 전 처음 접했을 때 엄청 푸려고 노력했다. 한 4일 정도 노력을 했는데 안풀렸다. 특수한 스킬이 필요한 것이 아니라 이해력 문제였는데 못 풀었기 때문에, 그리고 또 이 문제 시리즈를 1, 2, 3, 4, 5, ... 순서대로 풀려..

난이도 6/10DP문제, 특히 난이도가 높다고 생각한다. 특히 탑 구현? 부분 즉, dp 2차원을 어떤 정보로 memoization 할것인가가 크게 걸렸다. 나는 온전하게 문제를 풀지 못하였지만, 기억을 잃지 않으려고 포스트를 써본다. 각기 높이가 다른 블록이 여러개 주어지는데, 이것들로 두탑을 만드는데 두 탑의 높이가 같게 만든다.그런데 그것이 최대가 되는 지점을 생각해야한다. 최적화이다.인공지능이라는 어려운 주제를 구현하는 방법을 모르고,쉬운 방법을 원한다면 모든 경우의 수를 다 고려하는게 좋다, 그리고 가장 큰 특성치(두 탑의 높이가 같으며 최대 높이)인 지점을 찾는것.결국은 brute force와 그 지수복잡도를 해결하기 위한 subproblem의 만남이다. 즉 dp문제. 어떤 지점에서 subpr..

백준 1, 2, 3 더하기본문보기https://www.acmicpc.net/problem/9095 이번 문제는 경우의 수 구하는 문제이다. 해당문제는 n중 for문으로도 풀 수 있고, 재귀를 이용한 dfs 탐색(트리탐색) 으로도 풀 수 있다. 하지만 또 dp풀듯이도 풀 수 있다. dp 풀듯이라는 뜻은 어쨋든 굉장히 큰 길이 또는 크기를 구하는 문제이지만 서도 낮은 숫자부터 차근차근 sub-answer들을 구해내서 귀납적으로 큰 값에 대한 답 real-answer를 구하는 것이다.이게 바로 sub-problem , overlapping 이라는 개념인데 나는 아직 이 개념에 익숙치 않아서 이 블로그를 포스팅 하는 이유이기도 하다. 이번문제에서 숫자는 어떻게 완성될까? 우선 이전 dp 문제들의 접근법을 확인해..

백준 2*n타일링 2본문보기https://www.acmicpc.net/problem/11727 dp문제. 경우의 수를 구하는 문제이다. 이 문제는 2*n 타일링 의 확장판 같은 문제이다. (브루드워?) 링크참조이번엔 약간 다른것이 있는데 2*2 타일이 있기 때문에 a[n-2]의 경우의 수가 2개가 된다.길이가 3일때를 생각해보자. 2까지 완성된 경우 세로로 길때 완성되는 경우와 1까지 완성된경우 가로로 긴 두개를 쌓아서 완성된경우, 2*2로 완성된경우 가 있다.an 이 n 까지 완성된 블록의 경우의 수라고하자. a3 은 a2+ a1+ a1 으로 표현할 수 있다.3부터 차근차근 경우의수를 기록해나가면서 다음 길이의 블록의 경우의 수를 구하려고하면 된다.낮은 상태에서 부터 높은 상태로 까지의 값을 기로고해나..

백준 2*n 타일링본문보기https://www.acmicpc.net/problem/11726 dp문제. 경우의 수 문제이며, 점화식을 구하는 문제이다. 이 문제의 형식은 다음 문제와 유사하다. n 길이의 비트스트링 문자열의 경우의 수를 구하여라. 단 0이 두개 이상 연속하면 안된다.우선 n길이의 비트스트링 문자열 경우의 수는 2^n 이다. 그런데 0이 연속되면안된단다. 확실히 2^n보다 작을것 같지만 경우의 수가 몇개인지 모른다. 여기서 접근법은 이전 문제(1로만들기)처럼 차근차근 접근하는 것이다. 문자열 3일 때의 경우의 수를 생각해보자.문자열 3일때의 경우의수는 3번째 수가 1인경우와 3번째 수가 0인경우로 표현할 수 있다. 3번째 수가 0일때에는 반드시 2번째 수는 1이 되어야한다. 그리고 물음표인..