상상쓰

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 불금! import sys T = int(sys.stdin.readline()) dp = [[1, 0], [0, 1]] for i in range(39): dp.append([dp[-2][0] + dp[-1][0], dp[-2][1] + dp[-1][1]]) for i in range(T): N = int(sys.stdin.readline()) print(dp[N][0], end = ' ') print(dp[N][1])

https://www.acmicpc.net/problem/16500 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 www.acmicpc.net A에 포함된 문자열을 한 개 이상 붙일 수 있으므로 dp[index] 가 1이면 이미 재귀함수로 A의 문자열로 S를 만들 수 있는지 확인하고 있으므로 무시해도 된다. DFS 알고리즘으로 S = 'softwarecontest' A = ['software', 'contest'] 라면 1) index = 0 (dp[0] = 1) : softwarecontest(= S[0:]) 와 ..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net dp[i] = i 를 마지막 원소로 가지는 증가하는 부분 수열의 길이 A[i] > A[j] (단, j = 0,1,2, ..., i-1) 일 경우 dp[j] + 1 중 가장 큰 값을 dp[i] 로 설정한다. dp 의 최댓값을 반환하면 된다. import sys N = int(sys.stdin.readline()) A = ..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net P[i] 를 i+1 장 뽑았을 때의 최댓값으로 값을 재설정한다. 예를 들어 카드가 5장 뽑았을 때의 최댓값은 카드를 1장 뽑았을 때의 최댓값 + 카드를 4장 뽑았을 때의 최댓값, 카드를 2장 뽑았을 때의 최댓값 + 카들르 3장 뽑았을 때의 최댓값, 카드를 5장 뽑았을 때의 값 중 최댓값이다. import sys N = int(sys.stdin.readline()) P = list(map(int, sys...

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제를 보고 점화식을 잘 만들면 된다. P[N] = P[N-2] + P[N-3] (N >= 4) P[1] = P[2] = P[3] = 1 import sys T = int(sys.stdin.readline()) for i in range(T): N = int(sys.stdin.readline()) p = [0] * (N + 2) p[1], p[2] = 1, 1 for i in range(3, N+1):..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 동적계획법으로 역순으로 dp[i] 를 정하였다. (dp[i] = i일부터 N일까지 일했을 때의 최대 이익) 걸리는 기간을 포함한 날짜가 N일을 넘어가면 일을 할 수 없는 경우이므로 dp[i] = dp[i+1] 일을 할 수 있는 경우에는 i일에 일을 하지 않았을 때와 i일에 일을 했을 때 중 최댓값을 dp[i] 로 설정한다. i 일에 일을 하지 않았을 때 : dp[i+1] (i+1일부터 N일까지 일했을 때의 최대 이익) i 일에 일을 했을 때 : p + dp[i+t] (i일에 일을 했을 때 얻는 이익 + (i+t)일부터 N일까지 일을 ..

https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 0층일 때, dp = [1, 2, 3, 4, 5, 6, ...] 1층일 때, dp = [1, 3, 6, 10, 15, 21, ...] 2층일 때, dp = [1, 4, 10, 20, 35, 56, ...] ... 즉, 층이 올라갈 때 동적 계획법으로 구현해주면 된다. (dp[i] = dp[i-1] + dp[i]) import sys T = int(sys.stdin.readline()) for i in range(T): dp = [j fo..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 동적 계획법 문제로 dp 배열을 잘 정의해주자. dp 는 2차원 배열로 행을 물건의 개수, 열을 배낭의 무게로 잡는다. dp[i][j] 는 물건이 i 개 있을 때 j 를 수용할 수 있는 배낭에 들어갈 수 있는 가치의 합의 최댓값이라고 정의하자. 그럼, 물건이 추가됐을 때, 그 물건의 무게가 j 보다 작으면 그 물건은 수용할 수 없으..

https://programmers.co.kr/learn/courses/30/lessons/72416 코딩테스트 연습 - 매출 하락 최소화 CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는 programmers.co.kr DFS 와 동적 계획법을 이용하여 풀 수 있을 거라고는 생각했는데 dp 배열을 구현하기가 어려워서 다른 블로그를 참고하여 풀어나갔다. dp[i][0] : i 가 참석하지 않았을 때의 최솟값, dp[i][1] : i 가 참석했을 때 최솟값으로 정의하고, 기본값으로 dp[i][1] = sales[i-1], dp[i][0] = 0 으로 시작한다. 리프 노드부..

https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 조합, 파스칼의 삼각형을 이용하여 풀었다. 4를 예로 들면, 2칸을 기준으로 2칸을 뛴 적이 0번일 때 : 4C0 1번일 때 : 3C1 2번일 때 : 2C2 answer = 4C0(1) + 3C1(3) + 2C2(1) = 5 이다. 파스칼의 삼각형의 원리를 이용하여 2차원 배열에 각 조합 값을 담아(dp[..