https://www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 풀이 다이나믹 프로그래밍으로 피보나치 수를 구해주었습니다. 코드 # 10826번 피보나치 수 4 n = int(input()) dp = [0, 1] for i in range(2, n+1): dp.append(dp[i-2] + dp[i-1]) print(dp[n]) 출력결과

https://www.acmicpc.net/problem/17175 17175번: 피보나치는 지겨웡~ 혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 www.acmicpc.net 풀이 피보나치의 함수가 얼마나 호출되는지에 대한 계산을 요구한다. 그래서 dp테이블을 만들어서 n이 0~2까지의 함수 호출 횟수를 넣어준 뒤 다이나믹 프로그래밍을 통해서 n이 원하는 답을 구해주었습니다. 코드 # 17175번 피보나치는 지겨웡~ n = int(input()) dp = [1,1,3] for i in range(3, n+1): dp.append((dp[i-1] + dp[i-2] + 1..

https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 배낭 알고리즘을 이용해서 풀어줄 수 있는 문제이다. solved.ac 기준으로 class5를 달성하기 위해서 거쳐가야하는 문제 중 하나이다. 참고로 배낭 알고리즘은 Dp 알고리즘이기에 이 문제를 풀기 이전에 간단한 Dp문제를 풀고 오기를 바란다. 이 문제는 새로운 B앱을 활성화하기 위해 M메모리만큼 비활성화해야하는 앱들의 집합의 cost 최솟값을 찾는 문제이다. 따라서 기존의 배낭 알고리즘 문제에서..

Knapsack 문제와 Python으로의 구현 Knapsack 문제는 최적화 문제로 알려져 있으며, 가장 잘 알려진 결정론적 알고리즘 문제 중 하나입니다. 다양한 변형이 있지만, 여기서는 가장 대표적인 0-1 knapsack 문제에 대해 설명하겠습니다. 문제 설명: 주어진 물건들과 각 물건의 가치 및 무게, 그리고 일정한 무게를 수용할 수 있는 가방이 있을 때, 가방에 넣을 수 있는 물건들의 가치의 합을 최대화하는 문제입니다. 수식으로 표현하면: n개의 물건이 있고, i번째 물건의 무게는 w[i], 가치는 v[i]라 하자. 가방의 최대 무게는 W로 한정되어 있다. dp[i][j]를 i번째 물건까지 고려하고 가방의 무게 한도가 j일 때의 최대 가치로 정의한다. 본 문제를 풀기 위한 점화식: def knap..

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 풀이 배낭 알고리즘이라 불리는 다이내믹 프로그래밍 알고리즘의 일종. 1행과 1열의 원소값들은 0값으로 고정해준다. 행은 배낭의 무게를 뜻하고, 열은 물건의 번호를 뜻한다. i번째 물건을 가방 안에 넣을 수 없는 경우 -> 이전까지 최댓값을 저장해준다. i번째 물건을 가방 안에 넣을 수 있다면 -> dp에서 i번째 물건과 같이 넣을 ..

https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 풀이 BFS 알고리즘을 사용해서 문제를 풀어주었습니다. 3차원 리스트이기에 주의해서 짜주시면 됩니다. 코드 # 6593번 상범 빌딩 import sys from collections import deque dxyzs = ((0,0,1), (0,0,-1), (1,0,0), (-1,0,0), (0,1,0), (0,-1,0)) while True: L, R, C = map(int, sys.stdin.read..

https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 풀이 두 수의 합을 이용하기에 투 포인터 알고리즘인 것을 알 수 있다. for문으로 리스트 안에 특정 숫자를 뽑아주고 뽑은 특정 숫자를 제외한 숫자들의 합으로 뽑은 특정 숫자를 표현할 수 있으면 좋다(GOOD) 개수 1 추가. 코드 # 1253번 좋다 n = int(input()) li = sorted(list(map(int, input().split()))) ans = 0 # 두 수의 합을 표현해줄 숫자를 순차적으로 뽑아준..

https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 풀이 소인수분해를 구현해주는 문제이다. 나누는 값을 1씩 추가해서 더 이상 나눌 수 없을 때까지 나눠준다. 코드 # 11653번 소인수분해 n = int(input()) ans = [] def calc(c_n): for i in range(2, c_n): if n % i == 0: c_n = c_n // i ans.append(i) break return c_n if n != 1: while True: t = calc(n) if n == t: ans.append(n) break n = t print("\n".join..