문제 링크: 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/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..

문제 링크: https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 최소 스패닝 트리, 크루스칼 알고리즘 크루스칼 알고리즘을 사용해서 최소 비용으로 모든 노드를 연결하면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 7..

문제 링크: https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 다익스트라 알고리즘 다익스트라 알고리즘으로 출발점에서 도착점까지 최단 경로를 구하면 됩니다. #include #include #include #include #include #include using namespace std; const int MAX_N = 125; const int dx[4] = { 0, 0, 1, -1 }; const int dy[4] = { 1..