알고리즘3 다이나믹 프로그래밍 DP 다이나믹 프로그래밍 = 동적 계획법 = DP -메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 -이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. -다이나믹 프로그래밍의 구현은 일반적으로 탑다운, 바텀업 방식으로 구성된다. (일반적인 프로그래밍에서의 동적: 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당). 여기서는 다른 의미로 쓰인다. 조건 1.최적 부분 구조 (optimal substructure) -큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답이 모이면 큰 문제를 해결할 수있다. 2.중복되는 부분 문제(Overlapping subproblem) -동일한 작은 문제를 반복적으로 해결 예시 *점화식 : 인접한 항들 사이의 .. 2020. 11. 1. 백준 1541번 파이썬 풀이 | 잃어버린 괄호 | 그리디(Greedy) 알고리즘 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 이 문제의 핵심은 '-' 부호를 split 하여서 괄호로 묶어주면 된다. 예를 들어서 55 - 50 +40 -10 +5 의 최소값은 55 - (50 + 40) - (10 +5) = -50 이다. String으로 받아주기 때문에 '-'로 나누고 '-'에 있는 것들을 '+'로 나눠서 더해준다. 2020. 6. 29. 01. 그리디(Greedy) 알고리즘 그리디(Greedy) 알고리즘은 탐욕적인 문제 해결 방법으로 '문제를 해결하려는 상황에서 그 순간순간마다 최적의 상황을 쫓는 알고리즘'입니다. Greedy 방법은 최적의 해 근사값을 빠르게 찾아 줍니다. (단, 항상 최적의 결과를 도출하지는 않습니다.) 탐욕적이라고 불리는 이유는 미래를 생각하지 않고 지금 당장 보이는 것에서 최선의 방법을 선택하기 때문입니다. 그리디 알고리즘의 대표적인 예시는 거스름 돈 문제, 시간이 주어졌을때 한 사람이 최대한 많이 할 수 있는 수(활동 선택 문제), 배낭 문제에서 사용됩니다. 동전의 예시를 들자면, 740원을 거슬러 주어야 할때 500원 짜리 1개 , 100원짜리 2개 , 10원짜리 4개로 거슬러 주는 과정에서 "큰 화폐부터 거슬러 준다" 라는 알고리즘을 통해 최적의.. 2020. 6. 28. 이전 1 다음
