그리디

문제 분석프로그래머스 레벨 2의 배달 문제(12978)는 마을 개수 N, 두 마을 사이의 거리 정보 road, 배달 가능한 시간(거리) K를 인자로 받아, 1번 마을에 있는 음식점이 K이하 시간에 배달할 수 있는 마을의 개수를 반환해야 한다. 마을 개수 N : 1 ≤ N ≤ 50거리 정보 : [[a, b, c], [...]]a b : 두 마을의 번호c : 두 마을의 거리(시간)배달 가능한 시간 K : 1 ≤ K ≤ 500,000 위 마을 이미지를 기준으로 1번부터 5번 마을까지 최소 배달 시간을 [번호, 시간] 배열 형태로 나타내면 아래와 같다. 만약 배달 가능한 시간 K가 3이라면 1, 2, 4, 5번 마을이 모두 3시간 이하여서 정답은 4가 된다.  이처럼 1번 마을에서 다른 모든 마을까지 소요되는 ..

동적 계획법동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 더 작은 하위 문제로 분할하고, 그 결과를 저장하면서 큰 문제를 해결하는 방법이다. 이를 통해 문제의 연산 시간을 효과적으로 줄일 수 있다. 동적 계획법을 적용하기 위해선 다음 두 가지 조건을 만족해야 한다. 피보나치 수열이 아래 두 조건을 만족하는 대표적인 예. 최적 하위 구조 Optimal Substructure작은 하위 문제의 최적 해를 조합하여 전체 문제의 최적 해를 얻을 수 있다.하위 문제 중첩 Overlapping Subproblem동일한 하위 문제가 반복적으로 발생한다. 동적 계획법은 중복 계산 방지를 위해 메모이제이션 혹은 타뷸레이션 기법을 사용한다. 메모이제이션은 재귀 호출을 사용하여 필요한 문제만 계산하..