🥕 [ 백준 2294 ] 동전 2 문제 링크 url : https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 🍒 문제 분석 n 가지 종류의 동전이 있다. 이 동전들을 적당히 사용해 가치의 합이 k원이 되도록 만들고 싶다. 그러면서 동전의 갯수를 최소로 하고 싶다. 이때 사용하는 최소의 동전 갯수를 구하여라. 🥑 코드 def sol(k): d = [10001]*10001 for coin in coin_list: for i..
알고리즘
🥕 [ 백준 2293 ] 동전 1 문제 링크 url : https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 🍒 문제 분석 동전의 종류 n과 이를 이용해 만들어야하는 k원이 주어진다. 그리고 각 동전의 단위가 몇인지 알려준다. 이를 통해 k원을 만드는 경우의 수를 구해야한다. 가령 n = 3, k = 5 , 동전의 종류가 [1, 2, 5] 라면 1원 짜리 5개 1원 짜리 3개, 2원 짜리 1개 1원 짜리 1개, 2원 짜리 2개 5원 짜리 1개 하여 4..
[1로 만들기] 정수 X를 입력해, 5 로 나누거나, 3으로 나누거나, 2 로 나누거나, 1을 빼는 연산을 반복하여 1을 갖겠끔 하는 최단 연산의 갯수를 구하시오 도식화를 해보고 느낀 점은 1부터 해서 바텀 업 연산을 해야겠다. 1부터 X값 까지 최단 연산의 갯수를 다 구하면 되지 않을까? 근데 어떻게 연산 갯수 세는걸 어떻게 구현해야할지 모르겠어서 책을 봤다. ( 졸면서 5시간 고민 했는데 점화식이라는 개념이 미쳐 떠오르지 않았다. ) 점화식을 구해서 : 점화식을 토대로 소스 코드를 작성한다. def sol(X): # df 테이블 초기화, d[1] = 0 d = [0]*(X+1) for i in range(1,X..
저희 스터디에서 학습 진도에 관해 제가 발표할 차례가 되어 발표 자료를 다음과 같이 만들었는데 그걸 가지고서 다이나믹 프로그래밍을 정리해보고자 합니다. [피보나치 수열을 통한 개념 설명] 효율적인 알고리즘! 이라고 간단히 표현할 수 있겠다. 예시) def fibo(x): if x=1 or x=2: return 1 return fibo(x-1) + fibo(x-2) fibo(6)을 호출해 봅시다. 중복되어 사용되는 코드가 보이시나요? 바로 이러한 중복된 코드 등을 줄임으로써 코드를 효율적으로 만드는걸 DP이라고 합니다. [다이나믹 프로그래밍] 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답이, 그것을 포함하는 큰 문제에서 구한 작은 문제에 대한 정답과 같다. 위 두 조건을 만족할..
