버러범의 개발이야기

알고스팟 문제 링크: https://algospot.com/judge/problem/read/TPATH

각 도시들을 잇는 철도망이 주어질 때, 0번 도시에서 출발해서 V-1번 도시에 도착하는 경로들 중 최대 운행 속도와 최소 운행 속도의 차를 최소화하는 경로를 찾는 문제이다.

0번 도시와 V-1번 도시가 연결될 때까지 하한을 높여가며 다음과 같은 동작을 반복한다.

하한을 두고 kruscal알고리즘을 이용하여 하한이상의 가중치를 가진 철도부터 가중치 순서대로 그래프에 추가한다.

이때 kruscal의 시간복잡도를 지배하는 것은 edges를 가중치의 오름차순으로 정렬하는 작업이다.

문제에서 철도의 가중치가 변하지는 않으므로 edges를 정렬하는 작업을 선행처리한 후 나머지 부분만 하한을 높여가며

반복하면 기존의 kruscal알고리즘을 edges.size번 반복하는 것보다 빠르게 문제를 해결 할 수 있다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/31.%20MST/TPATH.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/LAN

건물들의 위치가 2차원 좌표로 주어지고 현재 연결된 케이블들이 주어졌을때, 모든건물들을 연결하기 위한 최소 케이블 길이를 구하는 문제이다.

현재 연결되어있는 간선들의 길이가 0이라 하고 kruscal알고리즘을 이용하여 문제를 풀 수 있다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/31.%20MST/LAN.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/PROMISES

도시를 연결하는 고속도로들이 있다. 추가적인 고속도로 건설 계획에서 입력순서대로 고속도로를 건설한다 했을때

고속도로 건설의 정당성은 기존에 고속도로를 통해 오갈 수 없던 두 도시가 새로 연결되거나, 두 도시를 오가는 데 걸리는 시간이 단축되는것, 둘 중 하나라도 만족해야 한다.

이때 정당성이 없는 고속도록 건설 계획의 개수를 구하는것이 문제이다.

경유할 수 있는 정점의 목록을 늘려가는 기존의 플로이드 알고리즘을 간선의 목록을 늘려가는 방식으로 변형하면 문제를 해결할 수 있다.

먼저 기존의 플로이드 알고리즘을 이용하여 이미 존재하는 고속도로들만을 이용한 최단경로를 계산한다.

그 후 입력 순서대로 건설 예정인 고속도로를 추가하는 앞에서 언급한 변형된 플로이드 알고리즘을 사용하여 최단거리 갱신 유무를 확인한 후 갱신 가능하다면 최단거리를 갱신한다.

이때 주의할점은 어느 방향으로 간선을 타고 갈 것인가를 정해야하기 때문에 정점을 추가할때와는 달리 경우의 수가 3개로 늘어난다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/30.%20ShortestPath/PROMISES.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/DRUNKEN

각 장소마다 음주운전을 할때의 소요시간이 있고 장소에서 다른 장소로 옮길때에도 소요시간이 있다.

시작 장소에서 약속 장소로 이동하는 경로 중, 최악의 예상 시간이 가장 작은 경로를 찾는것이 문제이다.

여기서 최악의 예상시간이란 경로중에 단속시간이 제일 긴 장소에서 음주단속이 걸렸을때를 말한다.

단속시간이 작은 장소를 우선적으로 경유하게끔 플로이드 알고리즘을 변형시켜 사용하면 문제를 해결할 수 있다.

Ck(u, v)를 k 혹은 그보다 단속 시간이 적게 걸리는 정점들만을 경유해서 u에서 v로 가는 최단거리라 했을때

최악의 예상시간은 min(Cw(u, w) + Cw(w, v) + E[w]) 라고 할 수 있다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/30.%20ShortestPath/DRUNKEN.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크 : https://algospot.com/judge/problem/read/TIMETRIP

V개의 은하가 있고 은하들은 웜홀로 연결되있다. 웜홀을 이용하면 시간이 미래(+) 또는 과거(-)로 이동한다.

지구(0번째 은하)에서 안드로메다(1번째 은하)까지 웜홀을 통해 간다고 했을때 최대 미래, 과거로 이동할때의 시간이 얼마나 바뀌는지 구하는 문제이다.

벨만-포드 알고리즘을 이용하면 음수간선을 포함한 그래프에 대해 각 정점간의 최단거리를 계산할 수 있다.

문제는 음수 사이클이 발견되었을때와 지구에서 안드로메다로 가는 경로가 없을때의 예외처리이다.

우선 음수 사이클이 발견되었을때 해당 음수사이클이 지구에서 안드로메다까지의 경로에 존재하냐를 판단한다.

경로상에 존재한다면 무한히 과거 혹은 미래로 갈 수 있기 때문에 INFINITY처리를 해준다.

만약 경로상에 존재하지 않는다면 무시하고 지구에서 안드로메다까지의 최단경로만 계산한 결과를 출력해주면 된다.

경로상에 존재하는지의 판단을 위해 플로이드 알고리즘을 이용하여 reachable[][]를 선행적으로 계산한다.

다음으로 지구에서 안드로메다로 가는 경로가 없을경우 UNREACHABLE처리를 해주어야 한다.

이 경우 bellman의 리턴값이 INF라고 생각하고 예외처리를 구현하면 실패할 수 있다.

지구에서 안드로메다까지의 경로는 없더라도 upper[target]이 완화되지 않고 계속 INF일 거란 보장은 없기 때문에 이 경우 역시 reachable[0][1]를 이용하여 처리한다.

코드 원본 : https://github.com/sbl133/JongmanBook/blob/main/30.%20ShortestPath/TIMETRIP.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/NTHLON

입력으로 두 선수의 종목당 걸리는 시간이 주어질때 두 선수를 비기도록 코스를 설계하는것이 가능한지 판단한다.

만약 비기도록 코스를 설계 가능하다면 그 중 제일 짧은 코스는 몇분걸리는지 계산하는 문제이다.

해당 문제를 그래프로 표현하여 해결가능하다.

우선 두 선수의 시간차를 번호로하는 정점을 만들고 걸리는 두 선수중 한 선수를 정해 해당 선수가 걸리는 시간을 가중치로 삼는다.

맨 처음 정점도 계산을 위해 0번이어야 하고, 마지막 정점도 0번이어야 하므로 두 0번 정점을 구분하기 위해 시작점을 따로 둔다.

또한 차이의 합이 200이 넘어가는 코스는 순서를 바꿔 200이 안넘어가게 설계가능하므로 -200부터 +200범위안을 표현하는 정점들로만 계산 가능하다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/30.%20ShortestPath/NTHLON.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/FIRETRUCKS

여러개의 지역들이 그래프 형태로 입력으로 주어지고 그중 불난곳과 소방서가 있는곳을 지정해준다.

이때 불난곳과 가장가까운 소방서에서 소방차가 출발한다 했을때 불난곳 각각에 대해 소방차가 도착할 때까지 걸리는 시간의 합을 구하는 문제이다.

다익스트라를 이용하면 문제를 쉽게 풀 수 있겠다고 생각할 수 있다.

하지만 불난곳 각각에 대해 모두 다익스트라를 실행하기엔 제한된 시간안에 계산를 완료하기 불가능하다.

다른 방법으로 가상의 지역으로하는 정점을 하나 만들고 해당 정점에서 소방서까지의 거리를 0으로 하는 간선을 연결시킨다.

이제 가상의 정점에서 출발하는 다익스트라를 이용하면 한번의 다익스트라 계산으로 각 소방서에서 각각의 불난곳까지의 최소거리들을 알 수 있게된다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/30.%20ShortestPath/FIRETRUCKS.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/MEETINGROOM

각 팀마다 두개의 회의가 있고 각 회의마다 시작시간과 종료시간이 입력으로 주어진다.

각 팀들이 다른 팀들과 시간이 안겹치게 회의를 딱 하나씩만 할 수 있는지, 할 수 있다면 각 팀의 회의 시간을 출력하는 문제이다.

해당 문제는 SCC(강 결합 컴포넌트)를 이용한 2-SAT문제로 해결 할 수 있다.

먼저 각 회의마다 참인 경우와 거짓인 경우 각각 두 개의 정점으로 표현하여 각 팀에 두 회의 관계를 그래프로 나타낸다.

팀은 두 회의 중 반드시 하나의 회의만 해야한다. 이를 표현식으로 나타내면 다음과 같다.

~i => j 앞에 회의를 안했다면 뒤에 회의를 꼭 해야한다.

~j => i 뒤에 회의를 안했다면 앞에 회의를 꼭 해야한다.

i => ~j 앞에 회의를 했다면 뒤에 회의는 꼭 하지 말아야 한다.

j => ~i 뒤에 회의를 했다면 앞에 회의는 꼭 하지 말아야 한다.

그리고 각 회의마다 겹치는 시간에 대한 관계 또한 그래프로 나타낸다.

두 회의가 시간이 겹칠 경우 최대 한개의 회의만 할 수 있다. 이를 표현식으로 나타내면 다음과 같다.

i => ~j 시간이 겹치는 두 회의 중 한개를 했다면 다른 한개는 하지 말아야 한다.

j => ~i 시간이 겹치는 두 회의 중 한개를 했다면 다른 한개는 하지 말아야 한다.

이러한 관계를 적절히 그래프로 표현한 다음 SCC를 이용하여 참 컴포넌트와 거짓 컴포넌트를 구분한 후 위상정렬하여,

첫 컴포넌트를 거짓이라 가정하고 차례로 컴포넌트에 속한 정점들의 참 거짓값을 채워 나가면 된다.

코드 원본 : https://github.com/sbl133/JongmanBook/blob/main/28.%20DFS/MEETINGROOM.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2