#백준 #BOJ #BAEKJOON #알고리즘 #풀이 #Python3 BOJ백준 2293 동전1 풀이(Python) 문제 링크 n가지 종류의 동전을 이용하여 k원을 만드는 경우의 수를 구하는 문제이다.이 문제역시 Dynamic Programming을 이용하여 간단히 해결할 수 있다.개인적으로 DP문제의 핵심은 문제를 어떻게 작은 문제로 나누거나 일반화시킬 것인가이기 때문에이와 같은 관점에서 생각해본문제 풀이의 핵심 전략은 다음과 같다. A-k1원, A-k2원, A-k3원...까지 주어진 동전들로 만드는 경우를 구했다고 했을 때 A원을 만드는 경우는 다음의 경우들을 더해주면 된다. 더 자세히 서술하면 1. n가지 종류의 동전을 반복문으로 순회하면서 내부에서 반복문을 한 차례 더 돌린다.2. 이 때 내부 반복문은 동전의 가치부터 k까지 순회한다.3. 내부 반복문이 j번째를 순회한다고 했을 때 dp[j]에 dp[j-(순회중.. 2019. 2. 8. BOJ백준 1890 점프 풀이(Python) 문제는 위와 같으며 전형적인 DP(Dynamic Programming)문제이다.DP의 의의는 이전에 계산했던 값들을 이번에 구할 값을 계산할 때 응용함에 있으므로 이를 중심으로 생각해보자. 예를 들어 A와 B라는 칸에서 C로 갈 수 있다고 해보자. 그렇다면 칸C까지 갈 수 있는 경우의 수는 칸A와 칸B까지 갈 수 있는 경우의 수의 합이 될 것이다.이를 이용하며 시작점부터 차례대로 게임판을 순회하며 각 칸에서 갈 수 있는 칸에 현재 칸까지 오는 경우의 수를 더해준다. 아래는 소스코드이다.123456789101112131415161718192021222324252627282930import sysN = int(sys.stdin.readline())board = []for i in range(N): temp .. 2019. 2. 6. BOJ백준 1339 단어수학 풀이(Python) 문제는 위와 같다. 어렸을 때 많이 봤던 방식의 문제였지만 알고리즘 공부를 시작한지 얼마 안되었던 나에게는 어떻게 구현할지 약간 막막했었다.고민하다가 내가 접근한 방법은 먼저 각각의 알파벳에 곱해지게 될 숫자를 구한 후 곱해지게 되는 숫자가 큰 순으로 정렬한 뒤차례대로 알파벳 값과 곱해지게 될 숫자를 곱하며 더해주는 방식이였다. 예를 들어, GCF와 ACDEB가 있다면1. GCF = 100*G + 10*C + 1*F2. ACDEB = 10000*A + 1000*C + 100*D + 10*E + 1*B이므로 각 알파벳 별로 곱해지게 될 숫자는A : 10000B : 1C : 1010D : 100E : 10F : 1이다. 이를 Dictionary 를 이용하여 구현하였고 후에 정렬한 뒤 더해주니 답이 나왔다. .. 2019. 2. 6. 이전 1 다음
