KEEP GOING!

프로그래머스 3xn 타일링의 문제 설명은 여기서 볼 수 있고 풀어볼 수도 있다. 이전에 2xn 타일링 문제를 풀어봤기 때문에 3n 타일링 문제에 도전해보았다. 원리는 비슷하고 조금 응용하면 되겠지.. 하고 쉽게 생각했지만 생각보다 그 응용이 쉽지 않았다.. 3xn 타일링도 2xn 타일링과 마찬가지로 DP로 풀 수 있는 문제였다. 문제 풀이를 시작하면, n이 홀수일 경우에는 크기가 2인 타일을 채울 수 없기 때문에 n이 짝수인 경우만 생각한다. 먼저 n=2인 경우 3가지 경우의 타일 모양이 나오고, 그 다음 단계로 진행할 때마다 아래와 같이 매번 2개씩 새로운 모양의 타일이 생긴다. f(n) = 가로의 길이가 n인 타일을 채울 수 있는 경우의 수 라고 하자. n = 4일 때는 이전 단계(n=2)에서 2칸이..

프로그래머스 카드게임은 DP로 분류된 문제로, 설명은 여기서 볼 수 있고 풀어볼 수도 있다. DP를 풀어본지 오래 돼서 풀어보려고 했으나 아이디어가 떠오르지 않아서 정답을 올려놓은 블로그 글을 참고했다. 그랬더니 DP를 푸는 방법에 대해 설명하는걸 보고 다시 DP에 공부했던 기억이 새록새록 떠올랐다. 다시 알게 된 김에 아래 3가지 방법 모두 구현해 보았다. Top-Down: 큰 문제들을 풀 때 작은 문제가 아직 풀리지 않았다면 작은 문제를 먼저 푸는 방식 ex) 재귀함수, Memoization Bottom-Up: 작은 문제부터 차근차근 풀어나가는 방식 이 문제의 기본 아이디어는 다음과 같다. i) 왼쪽 카드가 오른쪽 카드보다 크면, 오른쪽 카드를 버리고 점수를 높인다. ii) 그렇지 않으면, 왼쪽만 버..