코딩 테스트/do it! 알고리즘 코딩테스트100 088 쉬운 계단 수 첫번째 코드 dp에서는 점화식을 세우는 방법의 아이디어를 보면서이런게 있구나~ 라는 생각을 먼저 하는 것이 중요하다!! 점화식은 오로지 하나로 구성된 것이 아니고 나누어서 생각해야 한다!코드는 책을 참고했다! import sys input = sys.stdin.readline n = int(input()) dp = [[0 for _ in range(11)] for i in range(n+1)] mod = 1000000000 for i in range(1, 10): dp[1][i] = 1 for i in range(2, n+1): dp[i][0] = dp[i-1][1] dp[i][9] = dp[i-1][8] for j in range(1, 9): dp[i][j] .. 2024. 8. 29. 087 2×n 타일링 첫번째 코드 점화식을 세울 때는 쉬운 듯 했지만 나의 점화식과 차이가 있었다.나는 단순히 D[n] = D[n-1] + 1 (n-2에서 가로로 놓은 경우)라고 생각하였다.하지만 D[n] = D[n-1] + D[n-2]이었는데, 생각해보니 마지막이 가로로 되는 경우 다른 배열들이 모두 달라지기 때문에 이게 맞는 점화식이다. 코드는 점화식을 기반으로 작성하였으나, 오류가 나서 책을 참고한 결과처음 조건들을 주지 않아 문제가 생긴 것이었다. import sys input = sys.stdin.readline n = int(input()) dp = [0] * (1001) mod = 10007 dp[1] = 1 dp[2] = 2 for i in range(3, n+1): dp[i] = (dp[i-1] + d.. 2024. 8. 29. 086 이친수 첫번째 코드 점화식을 세우는 방법에서 어려움이 있었다.도리어 책의 개념을 통해 이해하면서 나는 왜 이런 생각을 못했지... 싶었다 ㅎㅎ;책을 기반으로 코드를 작성한 후 책을 참고하여 수정하였다. import sys input = sys.stdin.readline n = int(input()) dp = [[0 for _ in range(2)] for _ in range(n+1)] dp[1][1] = 1 dp[1][0] = 0 for i in range(2, n+1): dp[i][0] = dp[i-1][1] + dp[i-1][0] dp[i][1] = dp[i-1][0] print(dp[n][0] + dp[n][1]) 통과!링크https://github.com/ornni/programmers/t.. 2024. 8. 27. 085 퇴사 첫번째 코드 아직은 하나의 리스트로 작성되어 dp 이해에 문제가 되지는 않는다..하지만 2차원이나 그 이상으로 가게 되면...어...일단 나중에 경험해보자! 코드는 책을 참고했다! import sys input = sys.stdin.readline n = int(input()) dp = [0] * (n+2) time = [0] * (n+1) price = [0] * (n+1) for i in range(1, n+1): time[i], price[i] = map(int, input().split()) for i in range(n, 0, -1): if time[i] + i > n+1: dp[i] = dp[i+1] else: dp[i] = max(dp[i+1.. 2024. 8. 27. 083 선물 전달 첫번째 코드 완전순열에 관련된 문제로 점화식을 생각하는 것이 나는 조금 어려웠다.이전 상황을 가정한다고 했는데 계속 가정의 상황이 생각이 드는 기분이랄까? 또한 예외에 대해서도 많이 생각해야 할 것이다. 코드는 책을 참고했다. import sys n = int(input()) mod = 1000000000 dp = [0] * 1000001 dp[2] = 1 for i in range(3, n+1): dp[i] = (i-1) * (dp[i-1] + dp[i-2]) % mod print(dp[n]) 통과링크https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/1947.%E2%80%85%EC%84%A0%EB%AC%BC%E2%80%.. 2024. 8. 22. 084 1로 만들기 첫번째 코드 dp를 이용한 첫번째 문제로 코드를 작성하는 방법은 보고 싶어서 책을 참고했다.개인적으로 책에는 top-down이 더 쉽다고 나와있는데,이전에 bottom-up을 경험해서 그런가... 점화식을 구하는게 더 마음이 편해서 그런가개인적으로 top-down이 더 복잡했다... 조건에 거꾸로 진행된다고 생각하면 되는 것 같다.문제 푸는 사람에 따라 푸는 방법이 다양할 것 같은 알고리즘이다. import sys input = sys.stdin.readline n = int(input()) dp = [0] * (n+1) for i in range(2, n+1): dp[i] = dp[i-1] + 1 if i % 2 == 0: dp[i] = min(dp[i], dp[i//2] .. 2024. 8. 22. 이전 1 2 3 4 5 6 ··· 17 다음 728x90