지금은마라톤중

하루를 마무리하며 하나 풀어봅니다. 접근법- DP- 점화식 : dp[i] = dp[i-2] + dp[i-1] 실패 코드 - 입력값의 범위를 모두 충족하지 못했습니다. - n = 1일때 dp[2]에서 index out of range 에러 발생n = int(input())dp = [0 for _ in range(n+1)]dp[1], dp[2] = 1,2for i in range(3,n+1): dp[i] = dp[i-1] + dp[i-2]print(dp[n]%10007) 정답 코드n = int(input())dp = [0 for _ in range(n+1)]if n

제곱수의 합들을 구해보면 다음과 같습니다.1 : 12: 1 + 13: 1 + 1 + 14: 45: 4 + 16: 4 + 1 + 17: 4 + 1 + 1 + 18: 4 + 49 : 910: 9 + 111: 9 + 1 + 112: 4 + 4 + 4 시도 : 실패- 재귀함수 사용- N보다 작거나 같은 제곱수를 빼면서 카운팅- 반례 존재 : 12( 9+1+1+1)로 나오지만 최소개수는 3개(4+4+4)- 시도방법은 최소개수가 아닌 단순히 제곱수들의 합으로 나타내기만 한 것import syssys.setrecursionlimit(100000)def cal_func(n, cnt): num = int(n**0.5) rest = n - (num**2) cnt +=1 if rest == 0 : ..

DP 문제가 익숙해질 때까지 난이도를 올려가면 문제를 풀어보려고 합니다.해당 문제는 규칙성을 찾았다고 생각했는데 올바른 접근법이 아니여서 시간이 걸렸습니다. 시도- 안 되는 경우의 수를 찾기- 전체 경우의 수 - 안되는 경우의 수→ 안 되는 경우의 수가 1,2,3,6,10..... 나름의 규칙성을 가졌다고 생각해서 접근법을 가졌다고 생각했으나 틀렸다.  올바른 접근법- 각 자리에 대한 경우를 쪼개서 생각- 자리수가 늘어날때마다 각 숫자의 경우의 수를 생각하여 합하여 값 산출- 일반적 경우 : 2~8은 다음 자리에 올 수 있는 경우가 2가지(이전 자리의 단계수의 경우의 수)- 특수한 경우 : 0,9는 연속된 숫자가 1개임으로 각각 1가지 경우만 존재- dp를 2차원 배열로 만든다( n자리수, n 자리에 올..

해당 문제는 DP 문제입니다. 접근법- 규칙성 찾기- 점화식 형태 구현- 조건을 만족하려면 100, 101 형태를 지켜야함. 1 : 12: 103 : 100, 1014 : 1000, 1001, 10105 : 10000, 10001, 10010, 10100, 10101→ 점화식 : dp[i] = dp[i-1] + dp[i-2]  n = int(input())dp = [0] *(n+1)dp[1] = 1for i in range(2,n+1): dp[i] = dp[i-1] + dp[i-2] print(dp[n])

해당 문제는 DP 문제 입니다. 접근법- 작은 문제로 나눴을 때 이번 값을 중복해서 사용할 수 있음- 메모리제이션 활용- 이전 dp를 활용하여 값 계산- 3과 2로 나누어 떨어질 경우 : 최솟값 계산      1) 이전 dp 활용      2) 3과 2로 나누어지는 dp 활용 연산 조건를 한번 더 생각해 볼 필요가 있었습니다.연산 조건의 우선순위를 다시 생각해봤으면 좀 더 빠른 풀이가 가능했을 것 같습니다. x = int(input())dp = [0] * (x+1)def func_dp(n): for i in range(2,n+1): dp[i] = dp[i-1] + 1 if i % 3 ==0: dp[i] = min(dp[i], dp[i//3]..

사실 이 문제를 계기로 DP를 먼저 공부하기로 마음 먹었던 것입니다. 풀다가 6개 실패했습니다..알고보니 DP 알고리즘으로 푸는 문제였습니다. ㅎㅎ 그래서 지난 포스팅에서 DP를 푸는 이론을 먼저 공부하고 다시 도전하게 되었습니다. 접근법 - DP - 최댓값을 가지게 하는 방법 - 1,2번 계산을 무조건 밟는다 - 3번 계산부터 마지막 계산까지는 1칸 or 2칸을 이동 - i 번째 칸 일때 가능한 경우는 1) i-2칸에서 오는 경우와 2) i-3칸에서 i-1로 이동하여 오는 경우 *3칸을 연속해서 이동하지 못하는 점 고려 n = int(input()) scores = [0] scores += [int(input()) for _ in range(n)] dp = [0 for _ in range(n+1)] d..

이 문제는 2가지 풀이법으로 해결했습니다. 1. 조합 2. DP 1. 조합 문제를 봤을 때 가장 직관적으로 생각났습니다. # 조합으로 풀기 def fac(a): num = 1 for i in range(1,a+1): num *= i return num t = int(input()) for _ in range(t): n,m = map(int,input().split()) res = fac(m)//(fac(n)*fac(m-n)) print(res) 2. DP DP 문제를 풀어보려고 DP 문제 목록에서 골랐기 때문에 DP인걸 알 수 있었습니다. 하지만 문제만 보고 DP라는걸 알아차리는 것이 쉽지 않은 것 같습니다..ㅎㅎ 위 그림처럼 경우의 수가 규칙성을 가졌습니다. 그래서 작은문제로 쪼개어 해결할 수 있었습니..

이번에는 DP(Dynamic Programming, 동적 계획법)에 대해 공부해봤습니다. 원래 BFS와 DFS를 했으니 다른 그래프 이론들을 공부하려다가 코테에 잘 나오는거 먼저 하자!! 해서 순서가 좀 바뀌었습니다 ㅎㅎ DP(Dynamic Programming, 동적 계획법) : 복잡한 문제를 효율적으로 해결하기 위한 알고리즘 설계 기법 중 하나입니다. 이 방법은 주로 최적화 문제를 해결하는 데 사용되며, 큰 문제를 작은 부분 문제로 나누어 해결한 후, 그 결과를 저장해두고 필요할 때 다시 사용(메모이제이션)함으로써 계산의 중복을 피하는 것이 핵심 전략입니다. 동적 계획법은 문제를 분할하여 각각의 작은 문제들을 한 번씩만 풀어 큰 문제의 해답을 구하는 방식으로, 불필요한 계산을 줄이고 효율성을 높입니다..