소프트웨어개발블로그 소프트웨어개발블로그

풀이 표를 그려보면 쉽게 풀 수 있다. 그러나 표의 행과 열을 어떤 수로 구성해야 할지는 약간의 고민이 필요하다. (이전 문제와는 다르다.) 문제를 보면 무조건 1 부터 시작해야하며 1 이 나오면 반드시 다음에는 0이 와야하고 0 이 나오면 다음에는 0, 1 이 모두 올 수 있다는 것을 알 수 있다. 규칙은 매우 간단하다. 여기서 바로 점화식으로 옮길 수 있다면 좋을테지만 그런 능력이 아직은 안되기 때문에 표를 그려보았다. 각각의 열은 마지막 자리가 0, 1 인 이친수의 개수를 나타낸다. 예를 들어서 살펴보면 4 자리 수의 경우 1 0 0 0 1 0 0 1 1 0 1 0 이렇게 3 개의 이친수가 존재하므로 끝자리(2^0 의 자리) 가 0 인 것은 2 개, 1 인 것은 1 개가 존재한다. 이렇게 표현해놓고..

풀이 오르막 수 문제는 이전 계단 문제와 마찬가지로 2차원 배열을 활용해서 풀어낼 수 있다. 문제를 읽어보면 각 자리수에 어떤 수 j 가 온다면 그 수의 다음에 올 수 있는 수는 j ~ 9 까지가 된다는 것을 알 수 있다. 점화식은 다음과 같다. DP[N][j] = sum ( DP[N - 1][j ...9] ); 즉, 어떤 값 N 의 특정 자리수 j 의 값은 N - 1 의 자리수의 j 값 부터 9 까지의 모든 해를 더한 것과 같다. ps.. 위 표를 보면 위 값을 전부 더하는 방식(알고리즘에 따른 방식)은 3 중 for 문을 구성해야한다. 그러나 자리값의 해가 DP[N][J] = DP[N][j - 1] - DP[N - 1][j - 1] 로도 구해진다. 따라서 2 중 for 문으로도 표현할 수 있다. 코드..

풀이 2 자리수 부터 생각해보면 다음과 같다. 1 --> 0, 22 --> 1, 33 --> 2, 4...9 --> 8 3 자리수는 다음과 같다. 0 --> 11 --> 0, 1...8 --> 7, 99 --> 8 이렇게 살펴보면, 3 자리수 부터 다음의 규칙이 적용된다는 것을 알 수 있다. 1. 0 이 나오면 다음 수는 1 이 와야한다.2. 9 가 나오면 다음 수는 8 이 와야한다.3. 1 ~ 8 의 다음 수는 각각 2개가 있다. 이 규칙을 그림으로 그려보면, 점화식을 생각해 낼 수 있을 것 이다. 위 표에서 열은 해당 자리수의 마지막 수를 나타낸다. 그리고 값의 자리는 해당 자리수의 각각의 마지막 수가 나오는 경우의 수다. 그렇다면 이제 위 표를 DP 배열로 나타내고 입력받은 N 자리수에 대한 해당 ..

개요 이 문제는 이전 타일링 문제들과 아주 유사한 방식으로 풀어낼 수 있다. 이전 두 문제의 연습결과 쉽게 풀어낼 수 있었다. 마찬가지로 유념해야할 점은 규칙을 찾아내야 한다는 것이다. 풀이 어떤 수 N 을 1, 2, 3 으로 더하는 총 개수를 구해야 한다. 이전 문제들과 유사하게 이미 구한 값을 사용한다는 개념을 보면 규칙이 보인다. 4 의 경우 1 + 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 1 + 3 2 + 1 + 1 2 + 2 3 + 1 로 총 7가지의 경우의 수가 존재하는데 이것은 다음과 같이 바꿔서 볼 수 있다. 1 + (N - 1 을 1, 2, 3 으로 나타내는 경우의 수) 2 + (N -2 를 1, 2, 3 으로 나타내는 경우의 수) 3 + (N - 3 을 1, 2, 3 으로 ..

개요 이 문제는 11726 문제 (2xn 타일링) 의 다른 버전이다. 11726 문제를 정확히 이해했다면 같은 방식으로 풀어낼 수 있다. 풀이 2 x n 타일링 문제에서는 2 x n 타일을 채우기 위해 1 x 2, 2 x 1 타일을 사용했다. 그러나 이 문제에서는 2 x 2 타일이 추가되었다. 무엇이 달라질까? (1) 2 x 1 (2) 2 x 2 2 x 1 과 2 x 2 를 위와같이 준비해놓았을 때 2 x 3 은 다음과 같이 그릴 수 있다. (3) 2 x 3 2 x 2 번 그림을 그대로 가져온 후, 오른쪽에 2 x 1 크기의 타일을 세로로 하나 넣는다. ---> 개수 변화 없음. 2 x 1 번 그림을 그대로 가져온 후, 오른쪽에 2 x 1 번 크기의 타일을 가로로 2개 넣는다. ---> 개수가 x 2 가..

개요 이 문제는 Dynamic Programming 분류에 속하는 문제이다. 앞으로 문제를 풀며 기억해야 할 점은 문제에서 언급되는 알고리즘 이외에 언어들.. 예를 들면 타일링, 직사각형, CCTV ... 등의 단어에 집착하지 말아야한다는 점이다. 가장 중요한 것은 규칙을 찾고 그 규칙에 따른 식을 만드는 것이다. 풀이 입력받는 n 에 따라 2 x n 의 타일이 생성된다. 그 생성된 타일에 2 x 1 모양, 혹은 1 x 2 모양의 직사각형을 채워나가는 방법의 수를 구하는 문제이다. 직접 그려보기로 하는데 주의해야할 점이 있다. 2 x 4 만 되더라도 그려나가는 규칙이 제대로 성립되어 있지 않으면 빼먹기 쉽고 매우 헷갈린다. 먼저 규칙을 정해야 한다. (1) 2 x 1 (2) 2 x 2 (3) 2 x 3 ..

개요 이 문제는 Dynamic Programming 의 첫번째 문제다. Dynamic Programming 은 반복되는 연산을 매번 하지않고 배열이나 힙 등의 저장 공간에 저장해두었다가 필요할때 사용하는 알고리즘이다. 이러한 특징 때문에 이광근 교수님이 지은 "컴퓨터 공학이 여는 세계" 에는 Dynamic Programming 이 "기억하며 풀기" 라고 설명되어 있다. 학교 수업에서도 Dynamic Programming 은 Dynamic 과 거리가 멀다고 배웠는데, 적절한 번역이라고 생각한다. 동적 계획법 이라고 하면 전혀 감이 오지않지만, "기억하며 풀기" 라고 한다면 한번에 이해가 되는 기분이다. 시행착오 다음을 기억하려 했다. 1. X 를 3 으로 나누는 연산2. X 를 2 로 나누는 연산3. X ..

개요 백준 알고리즘 사이트에는 여러 입출력 문제가 있다. Problem Solving 을 시작하기 전에, 입출력에 관한 아주 조금의 불편함도 없어야 한다는 생각에 여러 입출력 문제를 모두 풀어내려고 한다. 이 글은 그 과정 중에서 주목할만한 부분만을 언급한다. 문제 리스트 2557, 1000, 2558, 10950, 10951, 10952, 10953, 11021, 11022, 11718, 11719, 11720, 11721, 2741, 2742, 2739, 1924, 8393, 10818, 2438, 2439, 2440, 2441, 2442, 2445, 2522, 2446, 10991, 10992 - 출처: http://plzrun.tistory.com/56 [plzrun's algorithm] 주목할..