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

 

algospot.com :: TPATH

여행 경로 정하기 문제 정보 문제 당신은 철도망을 이용해 한 도시에서 다른 도시까지 여행을 하고 싶다. 철도망은 여러 개의 역들과 그들을 잇는 노선으로 구성되어 있다. 각 구간별로 철도의

algospot.com

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

 

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

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

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

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

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

 

 

 

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

 

GitHub - sbl133/JongmanBook

Contribute to sbl133/JongmanBook development by creating an account on GitHub.

github.com

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

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

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

 

algospot.com :: LAN

근거리 네트워크 문제 정보 문제 근거리 네트워크(LAN, Local Area Network)는 가정, 학교, 혹은 회사 등의 제한된 공간 내의 컴퓨터들을 연결하는 네트워크입니다. 알고스팟 대학교에서는 캠퍼스의 일

algospot.com

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

 

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

 

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

 

GitHub - sbl133/JongmanBook

Contribute to sbl133/JongmanBook development by creating an account on GitHub.

github.com

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

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

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

 

algospot.com :: PROMISES

선거 공약 문제 정보 문제 경제가 침체기에 빠졌을 때 정치인들이 흔히 내거는 공약으로 대규모 토목 공사를 통한 경기 부양책이 있습니다. 이번에 집권당에서는 향후 N 년간 1년에 하나씩 전국

algospot.com

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

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

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

 

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

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

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

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

 

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

 

GitHub - sbl133/JongmanBook

Contribute to sbl133/JongmanBook development by creating an account on GitHub.

github.com

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

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

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

 

algospot.com :: DRUNKEN

Drunken Driving 문제 정보 문제 As the holiday season approaches, the number of incidents caused by Driving While Intoxicated (known as DWI) increases rapidly. To prevent this, the city of Seoul has proclaimed a war against drunken driving. Every day,

algospot.com

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

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

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

 

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

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

 

GitHub - sbl133/JongmanBook

Contribute to sbl133/JongmanBook development by creating an account on GitHub.

github.com

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

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

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

 

algospot.com :: TIMETRIP

시간여행 문제 정보 문제 서기 4096년, 시공간을 넘어 은하계들을 서로 연결하는 웜홀들의 존재가 발견되었습니다. 웜홀은 빛의 속도로도 수백만 년이 걸릴 만큼 떨어져 있는 두 은하계 사이를

algospot.com

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

 

GitHub - sbl133/JongmanBook

Contribute to sbl133/JongmanBook development by creating an account on GitHub.

github.com

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

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

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

 

algospot.com :: NTHLON

철인 N종 경기 문제 정보 문제 두 나라 A국과 B국은 항상 사이가 좋지 않은데, 국민들 간에 쌓인 감정을 털어버리기 위해 양국의 대표 선수들이 한 명씩 나와 친선 스포츠 경기를 하기로 했다. 채

algospot.com

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

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

 

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

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

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

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

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

 

GitHub - sbl133/JongmanBook

Contribute to sbl133/JongmanBook development by creating an account on GitHub.

github.com

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

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

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

 

algospot.com :: FIRETRUCKS

소방차 문제 정보 문제 한겨울 날씨가 추워지면 각종 난방 기구 때문에 화재가 발생하기 쉽습니다. 어느 추운 겨울날 서울 시내 n개의 지역에 동시에 화재가 발생했습니다. 피해를 최소화하기

algospot.com

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

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

 

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

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

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

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

 

 

 

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

 

GitHub - sbl133/JongmanBook

Contribute to sbl133/JongmanBook development by creating an account on GitHub.

github.com

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

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

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

 

algospot.com :: MEETINGROOM

회의실 배정 문제 정보 문제 회사가 빠르게 성장하면서 사람들이 늘어나면 가장 먼저 부족해지는 것이 화장실과 회의실입니다. 빠르게 확장하고 있는 치선이네 회사에서는 최근 회의실이 문제

algospot.com

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

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

 

 

해당 문제는 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

 

GitHub - sbl133/JongmanBook

Contribute to sbl133/JongmanBook development by creating an account on GitHub.

github.com

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

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

+ Recent posts