코딩테스트19 [백준] 10844: 쉬운 계단 수 파이썬 리뷰 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 방법은 해당 블로그를 참조하자 dp 테이블을 각 자리수 마다 한줄 씩 2차원 배열로 설정한다. (행 : 자릿 수, 열 : 0~9) 테이블에는 해당 숫자가 맨 앞에 있을 때 가능한 경우의 수를 저장한다. 예를 들어, dp[2][1]에는 백의 자리 숫자가 1인 경우의 수가 저장돼있다. 101, 121, 123 dp[2][1]을 저장했을 때를 생각해보자, dp[1][0]과 dp[1][2]를 더한 값이 dp[2][1]에 저장된다. 맨 앞의 숫자가 1이라면 그 뒤에 올 수 있는 숫자는 당연히 0 또는 2이다. 2이 맨 앞에 있을 때 경우의 수는 dp[1][2]에 저장 돼 있다. 0.. 2021. 2. 4. [백준] 11727: 2×n 타일링 2 리뷰 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이는 해당 블로그를 참고했습니다. 1. 2x(N-1)만큼 타일링하고 2x1 타일을 붙인다. 2-1. 2x(N-2)만큼 타일링하고 1x2 타일을 두 개 붙인다. 2-2. 2x(N-2)만큼 타일링하고 2x2 타일을 한 개 붙인다. 따라서 d(i) = d(i-1) + d(i-2) * 2 그림을 보면 이해가 쉬울 듯 합니다. 점화식을 구하려다 보니 고등학생 때 수열 점화식을 구하는 것 처럼 규칙을 찾을 생각만 했었습니다. (계속 조합 생각밖에 안났었다..!) 이전 단계가 경우의 수를 포함하고 있다는.. 2021. 2. 4. [알고리즘] 동적 계획법 (Dynamic Programming) 코딩테스트 대비 정리 알고리즘 문제를 풀던 중 동적계획법 풀이 방법 정리가 필요함을 느껴 동빈나님의 이코테 강의를 보고 제 생각을 더해 정리해 보았습니다. 풀이 언어는 파이썬을 사용했습니다. 목차 동적 계획법 개념 대표 풀이 예시 : 피보나치 수열 문제 리뷰 동적 계획법(DP) 개념 동적 계획법 메모리를 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산한 것을 메모리에 저장하여 중복 계산을 막는다. 최소/최대 문제 등에서 자주 사용된다. 점화식을 구해야 하며 이 과정이 어렵지만 코드는 대체적으로 간단한 편이다. 동적 계획법의 조건 1. 최적 부분 구조 : 큰 문제를 작은 문제를 나눌 수 있어야 함 2. 중복되는 부분 문제 : 중복되는 문제를 테이블에 저장하여 다시 계산하지 않음 동적 계획법의 두 가지 방법 1.. 2021. 2. 2. [백준] 1202(보석 도둑) 파이썬 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다. 상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000) 모든 숫자는 양의 정수이다. 출력 첫째 줄에 상덕이가 훔칠 수 있는 .. 2021. 1. 27. 이전 1 2 3 4 5 다음
