https://www.acmicpc.net/problem/6086 주어진 파이프를 이용해 A -> Z 로의 최대 유량을 계산하는 문제입니다. 주의할 점 : 소문자도 된다. 병렬로 연결도 가능하다. 양방향 연결이다. Edmonds Karp 알고리즘을 이용해 최대 유량을 계산하면 되지만, 양방향성과 병렬 가능에 주의를 해야 합니다. 기본적으로는 가상의 역방향 엣지를 추가하고, cap은 0으로 유지하여 Edmonds-Karp 알고리즘을 수행하지만, 양방향이므로, 역방향 엣지와 cap을 동일하게 잡아줍니다. 그리고 병렬처리가 가능하므로 cap을 누적하여 추가해줍니다. 불필요한 bfs 탐색을 방지하기 위해 vector에 누적해서 동일한 node를 추가하는 것 대신, set으로 연결된 노드를 관리하였습니다. ..
https://www.acmicpc.net/problem/1219(SPFA 연습을 위해 벨만 포드로 풀 수 있는 문제 중 선택을 해보았다.) 민식이는 특정 시작점에서 도착점까지 가는 경로마다 비용이 있고, 노드에 도착하면 돈을 법니다. 문제를 다음과 같이 치환할 수 있습니다. a node -> b node 비용 cost, b node 도착 시 버는 돈 earn : a -> b 갔을 때 버는 금액 = earn - cost도착 지점에 도달했을 때 버는 최종 금액을 최대로 하도록 하여라. 시작점에서도 버는 금액이 포함되는 건지가 햇갈렸는데 test case 5번을 보면 포함됨을 알 수 있습니다. (7만큼 0번에서 번다, 0번에서 0번으로 갈 때는 10의 cost가 든다. => 답 7 => 처음 0번 시작할..
https://www.acmicpc.net/problem/11657(SPFA 공부하고 적용해봤는데 타입 잘 못 잡기 + INF 케이스 오버플로우 방지 안함에 의해 수없이 틀려버렸다....) SPFA 알고리즘은 벨만-포드 알고리즘의 응용으로 벨만-포드 알고리즘이 모든 정점에 대해서 거리를 업데이트하는 것 대신, 거리 업데이트되는 노드를 대상으로만 알고리즘을 진행하는 방식이다. 알고리즘을 진행할 노드를 큐로 관리하며, 큐에 해당 노드가 존재하는 지 체크하는 배열을 별도로 두어 중복 계산을 방지한다. 벨만-포드 알고리즘이 복잡도가 O(VE) 이지만, SPFA는 dense 그래프가 아니면 O(V+E) 수준이므로, 벨만 포드보다 빠르게 음수가 있는 가중치에서도 최단 거리 계산에 접목할 수 있다.그리고 큐에 전체..
https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 자동완성 기능이 있는 사전을 이용해 주어진 문자열들을 만들기 위해서는 몇 개의 알파벳을 입력하여야 하는가의 문제입니다. ex) hello, hell -> h 입력 시 hell 까지 자동 완성, hello, hell, he -> h 입력 시 he 까지 자동완성, l 입력 시 hell 까지 자동완성 트라이를 이용하여 다음과 같이 풀 수 있습니다. 1) 입력으로 주어진 문자열의 마지막에 . 을 추가한다. (..
https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net (회사에서 프로그래밍 시험을 보는데 C/C++, Java 만 있어서 C++로 다시 연습 중이다.) (처음에는 자식 노드한테 번호를 순차 부여해서 - ex. (1, 2), (1, 3), 연결 시, 1 -> "1", 2 -> "10" , 3 -> "11", (2, 4), (2,5) 연결 시, 4 -> "100", 5 -> "101", .... prefix 일치 여부로 풀려고 했으나 끝없는 메..