#include #include constexpr int BLACK = 0;constexpr int BLUE = 1;constexpr int GREEN = 2;constexpr int CYAN = 3;constexpr int RED = 4;constexpr int MAGENTA = 5;constexpr int YELLOW = 6;constexpr int LIGHT_GRAY = 7;constexpr int DARK_GRAY = 8;constexpr int LIGHT_BLUE = 9;constexpr int LIGHT_GREEN = 10;constexpr int LIGHT_CYAN = 11;constexpr int LIGHT_RED = 12;constexpr int LIGHT_MAGENTA = 13;cons..

문제 링크: https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 플로이드-워셜 알고리즘 nxt[i][j] : i에서 j로의 최단 경로를 따라 i에서 가장 먼저 방문해야 하는 정점 이와 같은 2차원 배열 nxt를 추가로 정의하여 플로이드 알고리즘을 수행합니다. i에서 j로 이동하는 경로에서 새로운 최단 거리를 갱신하는 장점 k를 찾게 되면, nxt[i][j] = nxt[i][k]로 nxt 배열을 갱신합니다. 이는 i에서 k로의 최단 경로를 따라 이동한 후, ..

문제 링크: https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 트라이(trie) 트라이를 사용하여 전화번호를 삽입합니다. 삽입할 때마다, 트라이 내에 전화번호의 접두사가 이미 존재하는지 확인해야 합니다. 이를 구현하기 위해서는 find 함수에서 각 노드의 자식 노드의 존재 여부와 전화번호의 끝을 체크해야 합니다. #include #include using namespace std; class Trie { public: st..

문제 링크: https://www.acmicpc.net/problem/14426 14426번: 접두사 찾기 문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다. 총 N개의 문자 www.acmicpc.net 트라이(Trie) 트라이를 사용해서 문자열 삽입, 검색 #include #include #include using namespace std; class Trie { public: static const int MX = 10000 * 500; static const int ROOT = 1; int un..

문제 링크: https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세에 www.acmicpc.net 다익스트라, DP 알고리즘 j의 비용을 사용해서 i번 정점까지의 최단 거리를 저장할 2차원 DP[i][j] 배열을 만들고 다익스트라 알고리즘을 사용하면 됩니다. 최단 거리를 구할 때 2가지 최적화 방법을 적용할 수 있습니다. 1. 정점 u를 비용 c로 방문하여 최단 거리를 갱신할 때, 비용 c보다 큰 비용으로 정점 u를 방문하는 경우는 고려하지 ..

문제 링크: https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 그래프 탐색, 위상 정렬 도착 도시에 가장 마지막에 도착하는 시간은 해당 도시로 들어오는 모든 출발 도시들이 도착한 시점입니다. 이를 모든 도시에 대해 순차적으로 고려하면 DAG이기 때문에 위상 정렬로 답을 구할 수 있습니다. 도로를 지나는 횟수를 계산하기 위해 역방향 간선을 추가로 입력 받아 도착 도시에서 BFS를 수행합니다. 만약 u에서 v로 이동하는데 ..

문제 링크: https://www.acmicpc.net/problem/24042 24042번: 횡단보도 당신은 집으로 가는 도중 복잡한 교차로를 만났다! 이 교차로에는 사람이 지나갈 수 있는 $N$ 개의 지역이 있고 그 지역 사이를 잇는 몇 개의 횡단보도가 있다. 모든 지역은 횡단보도를 통해 직, www.acmicpc.net 다익스트라 알고리즘 횡단보도를 건너기 위해 파란불이 켜지기를 기다려야 합니다. 이 대기 시간을 '가중치'라고 생각할 수 있습니다. 또한 횡단보도의 파란불은 주기를 가지고 있기 때문에, 이 문제에서는 각 간선이 여러 개의 가중치를 가질 수 있습니다. A - B 간의 가중치는 i, M + i, 2M + i, 3M + i,... 와 같은 값을 가질 수 있습니다. 문제를 해결하기 위해, 다..

문제 링크: https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 플로이드-워셜 알고리즘 플로이드-워셜 알고리즘을 사용하여 각 정점에서 다른 모든 정점까지의 최단거리를 구하고, 탐색 범위 내에 존재하는 아이템들을 선택하면 됩니다. #include #include #include using namespace std; const int MAX_N = 100; int items[MAX_N + 1]; int d[MAX_N + 1][MAX_N + 1]; int m..