Hello Ocean! 🌼

문제 www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 시작정점부터, 다른 모든 정점까지의 최단경로를 구하는 단순한(?) 문제이다. 풀이 다익스트라 알고리즘을 이용하였다. #include #include #include using namespace std; #define INF 987654321 int min_route[20002]; int V, E, start; vector adj[20002]; void DijkstraHeap() ..

문제 www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 유의사항 1+2 와 2+1을 다른 경우로 센다는 것. 0도 사용할 수 있다는 것. 경우의 수를 1000000000으로 나눈 나머지를 출력해야한다는 것 풀이 이 문제는 DP(동적 계획법)을 이용하면 풀 수 있다! 2차원 캐시배열을 이용한 메모이제이션을 적용해야 한다. cache[k][n] : k개의 숫자를 더해서 n을 만들 수 있는 경우의 수 그리고 cache[k][n]은 다음과 같이 구할 수 있다. (점화식) cache[k][n] = cache[k-1][0] + cache[k-1][1] + cacke[k-1][2] + ... + c..

문제 www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 처음에는, DP를 어떻게 이용해야할지 떠오르지 않아서 일단 완전탐색으로 구현해보았다. 결과는 너무 당연하게도 시간초과였다! 완전탐색으로 구현하고 나면, DP에 대한 감이 올거라고 생각했는데 전혀 오지 않았다. 결국 검색의 힘을 빌렸는데, 이 문제는 대표적인 "냅색 문제"라고 한다. 냅색 문제(knapsack problem)란? 냅색 문..

문제 www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 처음에는 DP만 이용해서, cache[i][j]에 (i,j) 위치까지 도착할 수 있는 모든 내리막길 경우의 수를 저장하려고 했다. 하지만, 상하좌우로 모두 이동이 가능했기 때문에 이 방법은 실패했다. 두 번째 생각난 방법은, 최단경로찾기 문제로 해석해서 BFS로 푸는 방법이었다. 하지만, 시간초과 때문에 이 방법은 실패했다. 최종 방법은, DFS에 DP를 접목한 방법이다. DFS로 탐색하되, DP의 메모리..

문제 출처 www.acmicpc.net/problem/1175 1175번: 배달 어제 선물을 모두 포장한 민식이는 이제 선물을 배달하려고 한다. 민식이가 선물을 배달할 곳은 이 문제를 읽는 사람들이 앉아 있는 교실이다. 교실은 직사각형모양이고, 모두 같은 크기의 정사 www.acmicpc.net 문제 어제 선물을 모두 포장한 민식이는 이제 선물을 배달하려고 한다. 민식이가 선물을 배달할 곳은 이 문제를 읽는 사람들이 앉아 있는 교실이다. 교실은 직사각형모양이고, 모두 같은 크기의 정사각형 블록으로 나누어져 있다. 입력으로 교실의 지도가 주어진다. 각각의 정사각형 블록은 다음과 같이 4가지 종류가 있다. S : 지금 민식이가 있는 곳이다. 이곳이 민식이가 배달을 시작하는 곳이다. C : 민식이가 반드시 선..

문제 도서관 영업 후에 책 정리를 할 것이다. 재훈이의 현재 위치는 0이고, 각 책들의 위치는 절댓값이 10000이하인 정수이며, 0 위치에 있는 책은 없다. 한 번에 M개의 책을 운반할 수 있다고 할 때, 책을 모두 정리하는데 필요한 최소 걸음횟수를 구해라 . (마지막 책을 정리한 후에는 다시 원점으로 돌아올 필요가 없다.) 입력 N : 책의 개수 (1