나만의 개발블로그

이친수 문제의 경우엔 하나씩 작성해보면서 풀어보니 쉽게 규칙을 찾아 빠르게 풀게 되었음. a와 b에 누적 합을 활용한 풀이 방법 n = int(input()) a, b = 1, 1 for _ in range(2, n): a, b = b, a+b print(b) 배열로 누적 합을 활용한 풀이 방법 n = int(input()) dp = [0]*(n+1) dp[0:3] = [0, 1, 1] if n < 3: print(dp[n]) else: for i in range(3, n+1): dp[i] = dp[i-1]+dp[i-2] print(dp[-1])

DP를 활용한 누적 값을 이용해 푼 풀이 처음에 공식을 찾기 위해 2*4를 진행했을 때는 8개라고 생각해서 dp[n-2] + dp[n-1] 로 생각해 a,b = b, a+b 라고 생각했는데 위의 코드로 진행해보니 n=8의 경우 터무니도 없는 값이 나와 어떻게 해야하나 생각했다가 다시 조사해보니 2*4가 11개가 되어 dp[n-2]*2 + dp[n-1]로 진행해보니 원하는 값이 나왔다. 여기서 주의할 점은 조건문을 사용하지 않고 출력을 하게 되면 n이 1,2가 나올 경우의 값을 출력하지 못하기에 조건 분기를 아래와 같이는 아니더라도 해줘야할듯! n = int(input()) a, b = 1, 3 if n == 1: print(1) elif n == 2: print(3) else: for _ in range..

역시 수학 공식을 좀 알고 있어야 편하게 알고리즘을 풀 수 있다는 것을 조금 느꼈다... 처음 접한 방법으로는 당연히 조합으로 생각해서 combinations로 구한 다음 길이를 조회해야겠다라고 했지만 시간을 보니 0.5초이기도 하고 해당 방법은 너무 오래 걸릴 것이라는 것을 인지해서 다른 방법이 있을까 하고 짱구를 굴렸지만... 쉽지 않았고 조합 공식을 찾아보니 첫 번째 코드를 구현할 수 있었다. 우선 nCm 조합의 경우 n! / (n-m)! * m! 이 되고 현재 다리 놓기 문제에서는 m이 더 크고 n으로 된 조합의 개수를 찾기에 mCn의 경우가 되어 아래처럼 구현하게 되었음. # 공식을 활용한 풀이 import sys from math import factorial input = sys.stdin...

초기에 생각한 로직으로는 아래와 조금 차이가 있었는데 우선 가장 중요했던 dp에 추가하며 누적합을 시키는 대상 선정으로 현재가 i 라고 했을 때 li[i]+li[-2]+dp[i-3] 와 li[i]+dp[i-2] 중 가장 큰 값만을 출력하도록 했었는데 다른 반례들을 찾아보았을 때 6개 포도주가 있을 경우 1,1,0,0,1,1 의 경우에는 위의 로직으로 셈을 한다면 3이라는 결과가 나오게 된다. 그래서 li[i]+li[-2]+dp[i-4] 를 한 값과도 비교를 해서 더 넓은 범위의 조사를 할 수도 있다는 것을 이해하게 됨 또한 기존 dp의 값으로는 dp[0] = li[0] 으로만 넣고 풀었는데 위에 추가한 로직으로 인해 dp[2] 값까지 추가를 해줘야 하게 되었고 dp[3] 의 값은 내가 생각하기로 경우론 ..

단순히 문제에 나와있는 P(10)까지의 규칙을 확인해보면 해당 위치의 세 번째와 두 번째 위치 전의 값을 더한 값이 현재 위치의 값이 되기에 dp를 활용해서 풀었으며, li를 초기화하지 않고 전역에 놔두며 계속 추가함으로써 n-1번째 값이 현재 li에 있다면 바로 출력해 불필요한 시간을 줄이도록 하는 코드를 작성. li = [1, 1, 1]+[0]*97 for i in range(int(input())): n = int(input()) if li[n-1] != 0: print(li[n-1]) continue for j in range(3, n): li[j] = li[j-3]+li[j-2] print(li[j])

DP를 계속 풀면서 느낀 점으로 더 큰 값을 누적하며 dp를 쌓아 올려갈 때 비교해야 하는 대상 선정이 가장 중요한 것 같다. 처음 해당 문제를 접했을 때 li[i]+dp[i-1] 과 비교할 대상으로 dp[i-1]를 선택했는데 이유는 지금까지 누적한 값의 가장 큰 값 + 현재 값과 현재 값을 더하지 않은 누적 값을 비교해야 하는 거 아닐까? 라는 생각으로 접근했을 때 접근 방법에 대한 문제가 있다고 판단. 그래서 지금까지 누적한 값 + 현재 값과 현재 값부터 다시 시작하기 위한 현재 값만을 비교 후 더 큰 값을 현재 dp 값에 저장하여 문제를 해결 위의 로직을 기반으로 계속해서 각각의 위치에서 시작했을 때 가장 큰 값과 비교가 가능한게 아닐까라는 생각을 함. import sys input = sys.st..

DP를 사용해 이전의 값 중 가장 큰 값을 누적하며 더해가는 풀이 import sys input = sys.stdin.readline n = int(input()) li = [list(map(int,input().split())) for _ in range(n)] dp = [[0]*(i+1) for i in range(n)] dp[0] = li[0] for i in range(1,n): for j in range(i+1): if j == 0: dp[i][j] = dp[i-1][j] + li[i][j] elif j == i: dp[i][j] = dp[i-1][j-1] + li[i][j] else: dp[i][j] = max(dp[i-1][j] + li[i][j], dp[i-1][j-1] + li[i][j]..

문제로는 재귀로 푸는 횟수랑 DP로 푸는 횟수를 말했지만 제출해보니 사실상 둘 다 DP로 푸는 방법이고 재귀로 푸는 DP와 반복문을 통해 중첩해가는 DP로 문제가 구성되어 있다. def fib(n): if dp[n]: return dp[n] else: x = fib(n-1)+ fib(n-2) dp[n] = x return x n = int(input()) dp = [0]*(n+1) dp[1] = dp[2] = 1 fib(n) print(dp[n], n-2) 문제 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍으로 구하는 알고리즘을 배웠다. 재귀호출에 비해 동적 프로그래밍이..

생각하는 핵심 dp를 사용해서 현재 위치엔 조건에 만족하면서 지금까지 계산한 것들 중 가장 큰 값을 가질 수 있게 해야 함. 구현하기 어렵다고 생각한 부분 30, 10, 20, 10, 20, 60, 20, 10, 30, 50 과 같은 숫자로 구성되어 있을 경우 현재 위치가 60일 일때 1번째 위치에 있는 10과 그 다음에 있는 20일 때 총 카운팅이 2가 될 텐데 이때 다음에 있는 3번째에 있는 10과 그 다음에 있는 20의 경우에 다시 초기화를 시켜야 하나? 아니면 state를 따로 두고 비교 후 변경하면서 현재 값을 조회하면서, 가장 작은 값일 때를 생각해야하나? 라고 생각했었음. 아래의 코드처럼 풀게 된다면 위에처럼 복잡하게 생각할 필요없이 간단하게 풀 수 있다. 우선 현재 값 전까지 현재의 값과 ..

생각하는 핵심 DP로 접근할 때는 항상 최댓값을 끝까지 올려준다는 생각을 해줘야 할 듯. 물론 규칙을 적용한 상태로! 해당 문제의 규칙으로는 연달아서 3 칸의 계단을 접근하지 못한다는 것. 최대 2 칸만 건너뛸 수 있다는 점. 아래 문제에서 계속 혼동스러웠던 점 dp에 넣어주는 값이 위의 규칙을 잘 지켜가며 올라가는 것인지에 대한 점. 이유는 해당 계단에서 두 칸을 모두 밟으며 올라간 값이 최댓값이어서 dp에 넣고 그 다음 계단에서도 두 칸을 모두 밟으며 올라간 값이 최댓값이어서 dp에 넣게 된다면 연속해서 계속 계단을 밟아가는 것이 아닐까? 라는 생각으로 엄청 혼동스러웠음... 그래서 stairs와 dp를 구분해서 생각을 해본다면 조금은 이해가 갈 것이라고 생각한다. 단순히 더해지는 stairs의 값과..