1. 문제 14495번: 피보나치 비스무리한 수열 피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다. 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ... 자연수 n을 입력받아 n번째 피보 www.acmicpc.net 2. 코드 n = int(input()) def fib(n): fibs = [0, 1, 1, 1] if n == 1 or n== 2 or n==3: print(1) exit() else: for i in range(4,n+1): fibs.append((fibs[i-1])+fibs[i-3]) # print('fibs :',fibs) return fibs[-1]..
Koala - 11기/코딩테스트 준비 스터디
문제 출처 : https://www.acmicpc.net/problem/13699 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t..
문제 https://www.acmicpc.net/problem/9625 알고리즘 분류 - 다이나믹 프로그래밍 코드 K = int(input()) dp = [[0 for _ in range(2)] for _ in range(K+1)] dp[0] = [1, 0] dp[1] = [0, 1] for i in range(2, K+1): dp[i][0] = dp[i-1][0] + dp[i-2][0] dp[i][1] = dp[i-1][1] + dp[i-2][1] print(dp[K][0], dp[K][1]) 풀이 직접 써서 계산해보면 1번째: b 2번째: ba 3번째: bab => ba + b 4번째: babba => bab + ba 로 n-1번째와 n-2번째를 더한 것이 n번째임을 알 수 있다 때문에 b와 a의 개..
문제 풀이 3*N의 2차원 배열을 선언하였고, 각각의 행은 R, G, B를 나타낸다. i번째의 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다는 조건은 결국 연속한 세 집의 색이 같으면 안된다는 조건과 같다. dp[0][i] 행을 예시로 설명하면, i번째에 들어갈 최솟값은 [현재 집을 빨간색으로 칠하는 비용 + (이전 집을 초록색으로 칠하는데까지 필요한 비용, 이전 집을 파란색으로 칠하는데까지 필요한 비용, 이전 집을 빨간색으로 칠하는데까지 필요한 비용 중 최솟값)] 이다. 그런데 이전 집을 빨간색으로 칠하는데까지 필요한 비용엔 연속한 두 집을 빨간색으로 칠하는게 포함되어 연속한 세 집을 빨간색으로 칠하게 되버리니, 수정이 필요하였다. 전전 집을 빨간색으로 칠하는데까지 필요한 비용 + (이전 ..
풀이 dp배열 초기화한다. 2번 집부터 N번 집까지 순서대로 각 집을 빨강, 초록, 파랑으로 칠하는데 드는 최솟값을 계산하여 DP 배열에 저장한다. 각 집을 칠할 때, 이전 집과 색이 겹치지 않도록 하며 최솟값을 선택한다. 모든 집을 칠하는 비용의 최솟값은 DP 배열의 마지막 행에서 가장 작은 값이다. 코드 #include #include #include using namespace std; int main() { int N; cin >> N; vector cost(N, vector(3)); for (int i = 0; i > cost[i][0] >> cost[i][1] >> cost[i][2]; } vector dp(N, vector(3)); // 초기값 설정 dp[0][..
https://www.acmicpc.net/problem/13301 13301번: 타일 장식물 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개 www.acmicpc.net # 문제 설명 - 타일 장식물에서, {1,1,2,3,5,8...}과 같이 정사각형 타일 한 변의 길이를 구할 수 있다. - 타일의 개수 N(1 n; dp[1] = 1; dp[2] = 1; for (int i = 3; i
https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 문제 분석 난이도 골드 3 분류 LCS, DP 들어가기 전에 앞서 LCS 문제들을 풀고오지 않았다면 더 어려울 수 있다. 문제 문제 풀이 풀이 기존 LCS코드에(2중 for문)에 한 줄을 더 늘려주면 된다. 그렇게 되면 3개가 같을 경우 +1이 되므로 사실 2개일 때랑 별 차이가 없는 문제이다. (4개라면 4중, 5개라면 5중으로 굴려주면 될 것이다. 시간복잡도가 N^5인 것만 감안하면..!) 소스코드 def ..
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 다이나믹 프로그래밍 문제이며, 이 유형의 문제를 해결하기 위해선 점화식을 잘 세워야 한다. 이 문제에서는 항상 세로의 길이가 2로 고정되어 있으므로, 가로의 길이가 1씩 늘어남에 따른 경우의 수의 증가에 주목하면 된다. 각 경우마다 가능한 타일링의 수를 직접 구하다 보니 규칙이 보였다. dp[2]=2, dp[3]=3, dp[4]=5, dp[5]=8... 블록은 가로로만 증가하기 때문에 n개의 타일링은 n보다 작은 부분..
https://www.acmicpc.net/problem/15624 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net 1. 문제풀이 피보나치 수열은 다음과 같이 수식으로 표현하면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일 때까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 주어진 문제에서 n의 범위는 0 ≤ n ≤ 1,000,000이다. n의 범위가 크므로, n번째 피보나치 수를 구하기 위하여 재귀함수가 아닌 다이나믹 프로그래밍으로 접근하였다. n번째 피보나치 수를 1,00..
문제 https://www.acmicpc.net/problem/14430 14430번: 자원 캐기 인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. www.acmicpc.net 풀이 다이나믹 프로그래밍으로 풀이 편하게 작성하기 위해 N+1행 M+1열인 0으로 이루어진 2차원 리스트 생성한다. 이중 반복문을 통해 1,1부터 N,M까지 dp에 값(해당 위치까지의 최댓값)을 넣어준다. (NXM을 입력받았으므로 [i-1][j-1]에 해당하는 값에 dp로 구한 위쪽[i-1][j]과 왼쪽[i][j-1] 중 큰 값을 더한다.) 최댓값인 오른쪽 아래의 값을 ..
문제링크 https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 코드 t,w = map(int,input().split()) data = [0] + [int(input()) for _ in range(t)] dp = [[0 for _ in range(w+1)] for _ in range(t+1)] for i in range(1,t+1): if data[i]==1: dp[i][0] = dp[i-1][0]+1 else:dp[i][0] = dp[i-1][0] for..
문제링크 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 코드 from bisect import bisect_left def lis(arr): if not arr:return 0 dp = [arr[0]] for i in range(len(arr)): if dp[-1]
