HwangHub

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 이 문제는 지난번에 풀었던 "사각형 채우기"와 같은 유형의 문제로써, 점화식을 세울 때 조금 더 생각을 해줘야 하는 문제이다. 기본적으로 n번째 자리까지 타일을 까는 경우의 수는 n-1, n-2 번째까지의 타일을 까는 경우의 수 들을 이용하여 도출해낼 수 있다는 아이디어가 DP의 기본 흐름이다.(큰 문제는 작은 문제로 쪼개어 생각한다.) 이렇게 볼 때, 1칸짜리 그리고 2칸짜리를 이용하여 f(n) = 2 * f(n-1) + 3 * f(n-2) 까지는 쉽게 구해질 것이다. 이게 만약 안보인다면 ..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 1. n층 높이의 계단을 오르는 경우의 수를 구하는 문제이다. -> 여기까지만 보면 아직은 어떤 알고리즘을 쓸지 확신하기 어렵다. 2. 2개 또는 3개 계단 단위로만 오를 수 있다고 한다. -> 일정 패턴으로만 진행되는 것을 알 수 있다. 이렇게 정형화된 패턴을 배치하는 경우의 수를 구하는 문제는 다이나믹 프로그래밍의 가장 대표적인 유형이다. 문제에서 요구하는 답은 n개의 계단을 오르는 경우의 수 이므로 f(n) = n번째 계단을 오르는 경우의 수 일 것이다. n번째 계단은 n-2번째 계단 또..