공부 기록

✏️ 문제 문제 파악n이 1, 2, 3, 4, 5일 때 각각 dp[n]의 값을 구하면 쉽게 점화식을 구할 수 있다. 그림을 그려보면 다음과 같다.num 배열은 dp 배열 앞뒤 값의 차이를 담은 배열이다.그림을 보면 다음과 같은 점화식이 나오는 것을 알 수 있다.num[n] = dp[n-1]dp[n] = dp[n-1] + num[n-1] 나중에 보니 dp 배열 자체가 피보나치 수열와 같았음... = 이 말은 즉 num 배열 필요 X..  알고리즘다이나믹 프로그래밍  코드n = int(input())num = [0, 1, 1]dp = [1, 1, 2]for i in range(3, n): num.append(dp[i-1]) dp.append(dp[i-1] + num[i-1])print(dp[n-1])

✏️ 문제 문제 파악n이 1, 2, 3, 4일 때 각각 dp[n]의 값을 구하면 쉽게 점화식을 구할 수 있다. 그림을 그려보면 다음과 같다.하지만 이 문제는 메모리가 적고 시간이 매우 짧다는 점..!고민해보니 3개짜리 배열만 사용하면 되는 거 같아서 인덱스로 들어올 값을 %3 해 인덱스로 써서 풀었다. 그리고 이 문제는 답에 15746으로 나눈 값을 구하고 있다.처음엔 마지막 print에서 % 15746 했었는데 시간 초과가 떠서 애초에 배열에 값을 넣을 때 % 15746을 하니 풀렸다!  알고리즘다이나믹 프로그래밍  코드n = int(input())dp = [1, 2, 3]for i in range(3, n+1): dp[(i-1) % 3] = (dp[i % 3] + dp[(i+1) % 3]) % 1..

✏️ 문제문제 파악dp 배열을 주어진 배열의 누적 합을 담는 배열로 정의한 후 각 배열에 대해 그림으로 작성하면 다음과 같이 나온다.코드에 대해서 너무 헷갈려서 IndexError가 계속 났다..ary 배열은 0부터, dp 배열은 1부터 시작하는 것을 잊지 말자... 두 개가 각각 index 0, 1부터 시작하지 않으면 코드가 매~우 길어져요...  알고리즘다이나믹 프로그래밍 누적 합 코드시간 초과 코드처음엔 그냥 단순하게 풀어봤지만 틀렸다. 당연함. 실버 1문제임.n, m = map(int, input().split())ary = [list(map(int, input().split())) for _ in range(n)]for _ in range(m): x1, y1, x2, y2 = map(int, ..

✏️ 문제 문제 파악처음에는 시작점을 기준으로 잡아서 풀려고 했는데 경우의 수가 너무 많았다...!  뭔가 2156번 포도주 문제랑 2579번 계단 오르기 문제랑 비슷할 것 같아서 시간을 좀 썼는데 결국 못풀었다 ㅠ.. 아쉽 이 문제의 포인트는 시작점이 아닌 "끝점"을 기준으로 푸는 것이 포인트이다!끝점부터 시작점까지 내려오는데 해당 위치에 있을 때 n일 때 상담한다.n일 때 상담하지 않는다.이 두 가지 경우로 나누어서 둘 중에 더 큰 값을 dp[n]에 대입해야 한다.n일 때 상담하지 않는 경우를 왜 고려하냐면 n일 때 상담하지 않고 n-1일 때 상담했을 때 (n-1일 때 t[n-1]이 2 이상일 경우) 더 이득일 경우도 있기 때문이다.무조건 n일 때 꼭 상담하라는 말이 없기 때문이다.그림으로 작성하면 ..

✏️ 문제 문제 파악2579번 계단 오르기 와 유사한 문제이다!저 문제와의 차이점은 계단 오르기는 꼭 마지막 계단을 밟아야 하는데 이 문제는 꼭 마셔야 하는 포도주가 없다는 것이다. 그러면 경우의 수를 나누면 다음과 같이 나온다.n번째 포도주를 마신다.n-2번째 포도주를 마셨다.n-3번째 포도주와 n-1번째 포도주를 마셨다.n번째 포도주를 마시지 않는다.n-2번째 포도주와 n-1번째 포도주를 마셨다.나는 다른 풀이들이 다 해당 포도주를 마시지 않는다는 조건을 두길래 왜 최대를 구하는데 마시지 않는 조건을 고려하는 거지? 라고 생각했는데 이유를 생각해보니 다음과 같았다. 해당 포도주를 마시지 않는다는 조건을 두는 이유는n번째 포도주를 마시지 않고 n-2번째 포도주와 n-1번째 포도주를 마셨을 때 최대일..

✏️ 문제 문제 파악처음에 이중 반복문 써서 풀고 있다가.. 시간 초과나서 찾아보니 최대 부분합을 푸는 방법 중 카데인 알고리즘을 써야 풀리는 문제였다.간단하게 설명하자면 시작 원소를 기준으로 부분 배열을 구하는 게 아니라 끝 원소를 기준으로 모든 부분 배열을 구하는 알고리즘이다.   알고리즘다이나믹 프로그래밍   코드시간 초과 코드import sysinput = sys.stdin.readlinen = int(input())ary = list(map(int, input().split())) value = -1000for i in range(n): temp = ary[i] for j in range(i+1, n): value = max(value, temp) temp += ary[j]pri..

✏️ 문제 문제 파악입력으로 주는 배열을 기준으로 합을 담은 dp 배열의 값을 구하면 다음과 같이 나온다.중요한 것은 그림의 빨간 부분과 같이 중간에 겹치는 부분이 생기는데 이때문에 경우를 나눠서 구해야 한다.dp[n][0]dp[n][1] ~ dp[n][n-1] : 어짜피 최대값을 구하므로 max 값만 두면 된다.dp[n][n]  알고리즘다이나믹 프로그래밍   코드n = int(input())ary = [list(map(int, input().split())) for _ in range(n)] dp = [[0] * (n+1) for _ in range(n)]dp[0][0] = ary[0][0]for i in range(1, n): for j in range(i + 1): if j == 0: ..

✏️ 문제 문제 파악첨에 반복되는 게 있는 지 찾는데 안보였다..고민하다가 문제에서 P(1)부터 P(10)까지 주는 이유가 있을 것 같아서 찾아보니 다음과 같은 반복이 보였다!이를 토대로 점화식은 P(n) = P(n-1) + P(n-5) 이 나왔다.  알고리즘다이나믹 프로그래밍   코드for _ in range(int(input())): p = [0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9] n = int(input()) for i in range(len(p), n+1): p.append(p[i-1] + p[i-5]) print(p[n])

✏️ 문제 문제 파악11726번 2xn 타일 의 업그레이드(?)된 문제이다. 11726번 문제와 같이 점화식을 찾는 것이 중요한데 시간 좀 걸렸다... 그래도 풀었으니..!직접 n이 1, 2, 3, 4 일 때 dp(n)의 값을 찾았을 때 1, 3, 5, 11이 나왔다.n = 3일 때 dp(n) = 5인데 이는 dp(n-1) + dp(n-2) + dp(n-2) 의 값과 같은 것을 알 수 있다. 이를 토대로 점화식은 dp(n) = dp(n-1) + (dp(n-2) * 2) 이다.  알고리즘다이나믹 프로그래밍   코드n = int(input())dp = [0, 1, 3, 5, 11]for i in range(len(dp), n+1): dp.append(dp[i-1] + dp[i-2]*2)print(dp[n]..

✏️ 문제 문제 파악이 문제는 출발점을 기준으로 다음을 계산하는 거 보다 도착점을 기준으로 계산하는 게 더 편하게 풀 수 있다.도착점을 기준으로 계산하기 위해 도착점으로 오는 경우는 생각하면 다음과 같다.직전 칸에서 온 경우 (직전 칸을 밟은 경우 필히 3칸 전 칸을 꼭 밟음)stair[n] + stair[n-1] + dp[n-3]전전 칸에서 온 경우stair[n] + dp[n-2]이 두 경우 중 최대가 되는 값을 선택하면 된다.이때 0 도 생각해야 한다. 아니면 IndexError가 발생한다. (내 얘기) 알고리즘다이나믹 프로그래밍   코드n = int(input())stair = [0]for _ in range(1, n+1): stair.append(int(input()))if n == 1: pr..