본문 바로가기
반응형

다이나믹프로그래밍4

#30 [파이썬] 프로그래머스: N으로 표현 https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 해결 과정 1~8개의 N을 사용할 수 있다. 사용 개수에 따라 가능한 모든 경우를 저장한 후, number가 있는 지 없는 지 판단한다. 사용 개수를 key, 가능한 경우를 value로 하여 dictionary를 만든다. 5, 55, 555, 5555와 같이 연산이 아닌 단순히 이어붙인 경우는 따로 미리 포함시킨다. 첫번째 for문은 1~8개를 차례대로 고려하는 것이다. (최솟값을 찾는 것이므로 작은 수 부터) 두번째 for문을 이해하기 위해서는 아래 예시를 이해해야 한다. [3개 경우] 1개 리스트 원소 (+, -, *, //) 2개 리스.. 2022. 1. 17.
[알고리즘] 다이나믹 프로그래밍이란? 다이나믹 프로그래밍은 큰 문제를 작은 문제로 쪼개어 해결하는 것을 말한다. 분할정복과 다른 점은 쪼개진 작은 문제가 여러 곳에서 중복적으로 발생한다는 점이다. 따라서 같은 문제를 중복 계산하지 않고 솔루션을 공유하여 효율화하는 것이 중요하다. Dynamic Programming 알고리즘 조건 1) problem이 sub-problem으로 나누어 질 때 2) 각 sub-problem의 solution을 통해 상위 problem의 솔루션을 구할 수 있을 때 3) sub-problem들이 중복되며, 그 문제의 솔루션이 같을 때 → memoizaion 위 세 가지 조건을 충족하는 문제는 dynamic programming으로 해결할 수 있으며, 대표적인 예시로 피보나치 수열이 있다. Top-down (재귀함수).. 2022. 1. 16.
#26 [파이썬] 백준 12865번: 평범한 배낭 https://www.acmicpc.net/ Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net import sys input = sys.stdin.readline N, K = map(int, input().split()) D = [[0]*(K+1) for _ in range(N+1)] W = [] V = [] for _ in range(N): w, v = map(int, input().split()) W.append(w) V.append(v) for i in range(1, N+1): for j in range(1, K+1): if j < W[i-1]: D[i][j] = D[i-1][j.. 2021. 6. 29.
#23 [파이썬] 프로그래머스: 정수 삼각형 https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr def solution(triangle): for i in range(1, len(triangle)): for j in range(i+1): if j == 0: triangle[i][j] += triangle[i-1][0] elif i == j: triangle[i][j] += triangle[i-1][-1] else: triangle[i][j] += max(triangle[i-1][j-1], triangl.. 2021. 6. 27.
728x90
반응형

티스토리툴바