코딩 테스트/do it! 알고리즘 코딩테스트100 094 행렬 곱셈 순서 (미해결) 첫번째 코드 점화식 작성이 잘 이해가 되지 않았다.그래서 책의 내용대로 DP의 개념을 다시 생각하면서 과정을 거쳤다. 코드는 책을 참고하여 작성하였지만, 시간초과가 나타나 해당 부분을 해결하지 못했다. import sys input = sys.stdin.readline n = int(input()) D = [[-1 for _ in range(n+1)] for _ in range(n+1)] m = [] m.append((0, 0)) for _ in range(n): x, y = map(int, input().split()) m.append((x, y)) def execute(s, e): result = sys.maxsize if D[s][e] != -1: retu.. 2024. 9. 10. 093 Dance Dance Revolution (미해결) 첫번째 코드 이해가 되지 않은 부분이 있어 이해 후에 코드를 다시 작성할 예정이다.링크 2024. 9. 10. 092 고층 빌딩 첫번째 코드 점화식 세우는게 너무 어려운 문제....코드는 책을 참고했는데..내가 이해를 하고 쓴건지 모르고 일단 쓴건지... import sys input = sys.stdin.readline mod = 1000000007 n, l, r = map(int, input().split()) dp= [[[0 for _ in range(101)] for _ in range(101)] for _ in range(101)] dp[1][1][1] = 1 for i in range(2, n+1): for j in range(1, l+1): for k in range(1, r+1): dp[i][j][k] = (dp[i-1][j][k] * (i-2) + (dp[i-1][j][k.. 2024. 9. 5. 091 가장 큰 정사각형 첫번째 코드 dp를 대표하는 문제 종류 중 하나라고 한다.2차원 matrix의 경우에도 점화식에 유의하여 작성하며 방법에 대해 공부하자! 코드는 책을 참고하였다. import sys input = sys.stdin.readline n, m = map(int, input().split()) dp = [[0 for _ in range(1001)] for _ in range(1001)] max = 0 for i in range(n): numbers = list(input()) for j in range(m): dp[i][j] = int(numbers[j]) if dp[i][j] == 1 and j > 0 and i > 0: dp[i][j] = m.. 2024. 9. 5. 090 LCS 2 첫번째 코드 우울해하지 말고!!점화식을 만드는 방법이 이렇게 있구나~ 하면서 배워가기! 코드는 책을 참고했다! import sys input = sys.stdin.readline sys.setrecursionlimit(10000) a = list(input()) a.pop() b = list(input()) b.pop() dp = [[0 for _ in range(len(b) + 1)] for _ in range(len(a) + 1)] path = [] for i in range(1, len(a) + 1): for j in range(1, len(b) + 1): if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] + 1 .. 2024. 9. 3. 089 연속합 2 첫번쨰 코드 오른쪽부터 시작한 합과 왼쪽부터 시작한 합을 모두 고려해야 하는 문제이다.나도 처음에 단순하게 점화식을 작성했는데, 책에서 명확하게 이렇게 세우면 안된다는 예시였다 ㅎㅎ; 하여 점화식 아이디어와 코드는 책을 참고하였다. import sys input = sys.stdin.readline n = int(input()) a = list(map(int, input().split())) left = [0] * n left[0] = a[0] result = left[0] for i in range(1, n): left = max(a[i], left[i-1] + a[i]) result = max(result, left[i]) right = [0] * n right[n-1] = a[n-1].. 2024. 9. 3. 이전 1 2 3 4 5 ··· 17 다음 728x90