[백준] 2747번 - 피보나치 수, 2748번 - 피보나치 수 2 (한줄평) 다이나믹 프로그래밍으로 해결할 수 있었던 문제! 2가지 문제는 n번째 피보나치수를 구하는 문제로 두 문제의 차이는 n의 범위다. 2747번은 n의 범위가 45이하 자연수이고 2748번은 n의 범위가 90이하 자연수이다. 일단 두 문제 모두 일반 재귀로 피보나치 수를 구하려면 시간복잡도가 (2**n)으로 45이면 2**45(약 10**12), 90이면 2**90(약 10**27)으로 시간 초과가 나올 것이다. 그러므로 dp로 풀어야한다! (풀이1) 반복문 이용 풀이 시간: 5분 이내 1) 문제 해결 아이디어 2) 소스코드 n = int(input()) # 1. 45이하 자연수, 2. 90이하 자연수 d = [0] * (n + 1..
t = int(input()) # 테스트 케이스 수 for _ in range(t): n = int(input()) # 정수 d = [0] * 11 # 11보다 작은 양수 d[1], d[2], d[3] = 1, 2, 4 for i in range(4, n + 1): d[i] = d[i - 3] + d[i - 2] + d[i - 1] print(d[n]) [백준] 9095번 - 1, 2, 3 더하기 (한줄평) 아이디어만 떠올린다면 쉽게 풀 수 있는 문제! 풀이 시간: 20분 이내 1) 문제 해결 아이디어 11보다 작은 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제다. DP문제는 보통 아이디어만 잘 떠올리고 점화식을 세운다면 코드 자체는 간결하게 해결할 수 있는 문제..
[백준] 9184번 - 신나는 함수 실행 (한줄평) 재귀함수 그대로 구현하면 되지만 오류를 스스로 해결하지 못했던 문제..! 꼭 복습이 필요하다~ 풀이 시간: 60분 이내 1) 문제 해결 아이디어 이 문제는 a, b, c가 주어졌을 때 w(a, b, c)를 구하는 문제다. 이 문제는 아래의 재귀함수 그대로 구현을 하면 되지만 이렇게만 구현하게 되면 동일한 작업을 계속 반복하게 되어 그 값을 구하는데 매우 오랜 시간이 걸리게 되는 문제가 발생한다. 그래서 다이나믹 프로그래밍으로 해결해야하는데 다이나믹 프로그래밍의 핵심은 반복되는 계산을 피하기 위해서 dp테이블에 계산한 값을 저장해두고 나중에 그 값이 필요하다면 바로 그 값을 가져다 쓰는 것이다. if a 20, then w(a, b, c) returns:..
[백준] 1003번 - 피보나치 함수 (한줄평) 피보나치 수를 구하는 문제에서 약간 변형된 문제로 피보나치 수열 문제 풀 때 한번쯤 다시 풀어보면 좋을 것 같은 문제! 40이하의 자연수/0 이 n으로 주어질 때, fibo(n)이 호출되었을 때 fibo(0)과 fibo(1)이 호출되는 횟수를 구하는 문제다. 재귀 혹은 반복문을 이용하여 풀 수있고 두 방식 모두 메모리나 시간 측면에서는 동일하니 편한 방식으로 풀면 될 것 같다. (풀이1) 재귀 이용(내 풀이) 풀이 시간: 20분 이내 1) 문제 해결 아이디어 재귀를 이용한 풀이 방식이다. n번째 피보나치 수를 저장하는 dp 테이블(d)에 기존에는 피보나치 수 1개 값만 저장했다면 이 문제에서는 [피보나치 수, 0 호출 횟수, 1 호출 횟수] 3개 값을 저장..
[이코테] 문제6 - 병사 배치하기(59:50) (한줄평) 아이디어를 떠올리기 어려웠던 문제로 답을 봤음에도 이해하는데 어려움이 있어서 꼭 복습이 필요!! 풀이 시간: 1) 문제 해결 아이디어 예를 들어 수열 array = {4, 2, 5, 8, 4, 11, 15} 라면 가장 긴 증가하는 부분 수열은 {4, 5, 8, 11, 15} 이다. 이 문제는 가장 긴 감소하는 부분 수열을 찾는 문제로 LIS 알고리즘을 조금 수정하여 정답을 도출할 수 있다! 가장 먼저 입력받은 병사 정보의 순서를 뒤집고 최장 증가 부분 수열(LIS) 알고리즘을 수행하여 정답을 도출한다! 병사 정보의 순서를 뒤집는 이유는 LIS는 가장 긴 오름차순 수열을 찾는 것이지만 실제로 우리는 가장 긴 내림차순 수열을 찾아야 한다. 그러므로 ..
[이코테] 문제5 - 금광(52:30) (한줄평) 혼자서 푸는데는 성공했지만 책 코드와 약간 다른 부분이 있어 복습이 필요한 문제!! (풀이1) 내 풀이 틀린 코드(1차원 리스트) 풀이 시간: 50분 이내 1) 문제 해결 아이디어 문제 자체는 2차원 리스트이지만 입력을 1차원 리스트로 받았기 때문에 금의 최대 크기를 담은 dp테이블도 1차원 리스트로 생성하여 풀었다. 2) 소스코드 t = int(input()) # 테스트 케이스 수 for _ in range(t): n, m = map(int, input().split()) # 세로, 가로 graph = list(map(int, input().split())) # n * m 개의 금 개수 d = [0] * (n * m) # 금의 최대 크기 for i in..
[이코테] 문제4 - 효율적인 화폐 구성(226p) (한줄평) 점화식은 잘 세웠으나 책의 풀이가 더 간결하고 좋았던 문제로 한번쯤 복습이 필요한 문제! 풀이 시간: 40분 이내 1) 문제 해결 아이디어 이 문제는 그리디 거스름돈 문제와 거의 동일하지만 화폐단위의 큰 단위가 작은 단위의 배수가 아니기 때문에 무조건 큰 단위부터 거슬러주면 안된다!! 금액 1부터 m까지 만들수 있는 최소한의 화폐 개수를 찾아 d에 입력하면 된다. 아래의 점화식을 n개의 화폐 단위에 대하여 차례로 적용하면 된다. 각 금액을 만들 수 있는 최소 화폐 개수를 담는 리스트(d)를 (m + 1)의 크기로 10001로 초기화하여 생성한다. Q. dp테이블을 10001로 초기화하는 이유는? 화폐의 가치는 10,000보다 작은 자연수이고 ..
[이코테] 문제3 - 바닥 공사(223p) (한줄평) 코드는 짧으나 점화식을 떠올리기가 쉽지 않았던 문제로 복습이 꼭 필요!! 풀이 시간: 30분 이내 1) 문제 해결 아이디어 가로 길이: n, 세로 길이: 2 인 직사각형 바닥을 1*2, 2*1, 2*2 3가지 타일로 채울 수 있는 경우의 수를 구하는 문제다. 이 문제 또한 다이나믹 프로그래밍의 기초 예제에서 빠질 수 없는 타일링 문제 유형이다. 왼쪽부터 타일을 채운다고 했을 때 아래와 같이 2가지 경우로 나눠볼 수 있다. 1. i - 1까지 이미 채워져있다면, i번째를 채우기 위해 사용할 수 있는 타일은 (2 * 1) 1가지 경우다. 2. i - 2까지 이미 채워져있다면, i - 1 ~ i 번째를 채우기 위해 사용할 수 있는 타일은 (1*2) 2개, ..
