Dynamic Programming
1.[Algorithm] Dynamic Programming(동적 계획법)
표(table)을 만들어 채워가면서 답을 구하는 방법“programming”의 의미 : tabular method(표 방식)optimization problem을 해결하기 위해 쓰임최적해의 구조적 특징을 찾는다.최적해의 값을 재귀적으로 정의한다.최적해의 값을 일반적으로
2.[백준 2098] 외판원 순회 (DP, 자바스크립트)
외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가
3.[백준 1562] 계단 수 (DP, 자바스크립트)
45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지
4.[백준 2169] 로봇 조종하기 (DP, 자바스크립트)
로봇 조종하기NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 N×M 배열로 단순화 하여 생각하기로 한다.지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른
5.[백준 1256] 사전 (DP, 자바스크립트)
동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있다. 그리고
6.[백준 4485] 녹색 옷 입은 애가 젤다지? (다익스트라, 자바스크립트)
[녹색 옷 입은 애가 젤다지(https://www.acmicpc.net/problem/4485) 문제 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된
7.[백준 2228] 구간 나누기 (DP, 자바스크립트)
구간 나누기N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 한다.각 구간은 한 개 이상의 연속된
8.[백준 2213] 트리의 독립집합 (DP/DFS, 자바스크립트)
트리의 독립집합그래프 G(V, E)에서 정점의 부분 집합 S에 속한 모든 정점쌍이 서로 인접하지 않으면 (정점쌍을 잇는 간선이 없으면) S를 독립 집합(independent set)이라고 한다. 독립 집합의 크기는 정점에 가중치가 주어져 있지 않을 경우는 독립 집합에