1. 문제 19947번: 투자의 귀재 배주형 (acmicpc.net) 19947번: 투자의 귀재 배주형 2020년에 학교로 복학한 주형이는 월세를 마련하기 위해서 군 적금을 깨고 복리 투자를 하려고 한다. 주형이가 하려는 투자에는 3가지 방법의 투자 방식이 있다. 1년마다 5%의 이율을 얻는 투자 ( www.acmicpc.net 2. 풀이 아주 기본적인? 다이나믹 프로그래밍.. 근데 어떻게 하는건지 잠깐 기억이 안났었다는게 함정 dp를 길이가 y+1인 배열 [0]*(y+1) 초기화할테고 dp[0] = h여서.. y년 후의 금액이 dp[y]라고 해서.. 1년,3년,5년 투자 방식중 최댓값을 골라 dp에 저장할텐데 이거 어떻게 하더라... 잠깐 정적.. ------------------------------..
1. 문제1 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 나선형으로 정삼각형을 만들었을때, 정삼각형의 가장 긴 변의 길이를 구하는 방법은? 2. 풀이1 이런 문제는 그냥 몇개 나열해보면서 규칙을 찾으면 되겠다고 생각하는게 제일 편하다 이런 규칙 찾는 문제가 다이나믹 프로그래밍의 가장 기본형태라고 생각하면 된다 그래서 몇개 해보면 규칙이 나올거야 p(1)부터 p(10)까지는 1,1,1,2,2,3,4,5,7,9라고도 친절하게 나와있고 그림에서 p(1..
1. 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1이상의 정수 x가 주어질때, 1) x가 3으로 나누어 떨어지면 3으로 나눈다 2) x가 2로 나누어 떨어지면 2로 나눈다 3) x에서 1을 뺀다 3가지 연산을 적절히 사용해서 1을 만들고 싶다 연산을 사용한 횟수의 최솟값을 출력한다면? 2. 나의 풀이 다이나믹 프로그래밍 연습문제니까 다이나믹 프로그래밍을 써야겠지 기본이 바텀업이고 반복문 구현이라고 배웠으니까 이에 따라보자 작은 문제부터 구해놓고, 이들을 이용해서 반복문을 구현한다면.. 1이상이니까 dp[0] = 0, 1은 연산을 안해도 1이니까 d..
1. 동적계획법? 다이나믹 프로그래밍(dynamic programming) ‘하나의 문제는 단 1번만 풀도록 하는 알고리즘’ 2개의 가정 하에 사용할 수 있다 1-1) 큰 문제를 작은 문제로 나눌 수 있다. 1-2) 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어서 해결한 뒤에 각각을 처리한 다음 나중에 전체의 답을 구하는 것 이 과정에서 이미 계산한 결과는 배열에 따로 저장한다음 나중에 동일한 계산을 할때 저장된 값을 단순히 호출하여 반환하기만 하면 된다 2. 피보나치 수열 피보나치 수열의 점화식은 $$a_{n}=a_{n-1}+a_{n-2}$$ 특정한 위치의 숫자를 구하기 위해 바로 이전의 숫자와 두번 이전의 숫자의 합을 구함 초기..
1. 알고리즘 1 이상의 양의 정수가 리스트 내에 존재 하나의 리스트를 두개의 리스트로 분할하고자 하는데 각 리스트의 수의 합의 차이가 최소가 되도록 분할하고자 한다. 합의 차이의 최솟값을 return 가장 쉬운 방법은 itertools.combinations를 이용해서 완전 탐색을 하는 것 그러나 완전 탐색을 하면 효율성이 매우 떨어짐 먼저 초기 변수를 지정함 mmr은 주어진 전체 리스트 n은 리스트의 인덱스 지정 team1은 첫번째 리스트의 정수 총합 team2는 두번째 리스트의 정수 총합 table은 dynamic programming table def findMinAbsDiff(mmr, n, team1, team2, table): # Base case: if the list becomes empt..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
