본문 바로가기

코딩테스트10

[백준] 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.
[백준] 2437(저울) 파이썬 문제 문제 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다. 무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오. 예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 입력 첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나.. 2021. 1. 27.