문제 https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 www.acmicpc.net 풀이 부분집합으로 풀이가 가능한 문제 DP Knapsack으로 접근해봤던 문제임 접근법 Knapsack으로 풀어보자고 권유를 받아 DP 상향식으로 접근 세준이의 최대체력은 100으로 각 체력을 행으로 주어지는 사람을 열로 2차원 dp배열을 초기화 각 j번째 사람에 대해 hp[j]가 현재 체력 i보다 낮을 경우 이전 부분문제의 해와 비교하여 최대값을 갱신 누적값이 필요하기 때문에 체력 i보다..

문제 https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 풀이 역 인접리스트를 활용한 데이크스트라 문제 첫번째 접근법 소프티어 8차를 보고난 후 1번문제와 비슷하다 판단하여 그리디하게 접근함… 각 면접장마다 i번째 면접장소를 end로 잡고 각 정점으로부터 i번째 면접장까지의 최단거리를 구함 두번째 접근법 제일 처음 떠올렸던 접근인데 각 면접장으로부터 다른 정점들까지의 최단경로를 구함으로써 한번..

문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 DP를 활용한 완전탐색 첫번째 접근법 (BFS) 각 격자별로 BFS를 수행하면서 DP 메모이제이션을 수행. 다음 탐색좌표에 대한 최장길이 DP값이 있다면 해당 부분문제 해를 이용하여 현재 최장길이를 구하는 식으로 풀이. 두번째 접근법 (DFS) 첫번째 접근에서 메모리초과가 발생하여 DFS로 변경 로직자체는 동일 각 좌표마다 DFS를 수행하면서 다음 나아가는 좌표에 대해 메모이..

Concept 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제 Feature 배낭 문제에는 두 가지 유형이 존재 Fractional Knapsack : 물건을 쪼갤 수 있음. 무게나 가치가 소수점 단위로 나뉠 수 있는 문제. 0-1 Knapsack : 물건을 쪼갤 수 없음. 무게나 가치가 무조건 정수타입을 가지는 문제. Implement Brute-Force 가장 기본적인 풀이방법으로써 N개의 물건에 대해 가능할 수 있는 모든 조합을 만들어 보는 접근법. 시간복잡도는 O(2^N)으로 많이 느리다고 볼 수 있다. Dynamic Programming DP의 핵심은 메모이제이..