버러범의 개발이야기

알고스팟 문제 링크: 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

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

그래프에서 인접한 노드중에 적어도 하나의 노드에 감시카메라가 설치되어있지 않으면 해당 노드에 감시카메라를 설치 해야한다.

이때 필요한 최소한의 감시카메라의 개수를 구하는 문제이다.

문제 조건에서 "미술관은 한 번 관람한 갤러리를 다시 가기 위해서는 이전에 지나왔던 복도를 반드시 한 번 지나야 하는 구조로 설계되어 있으며"가 있으므로 해당 그래프는 트리형태임을 알 수 있다.

따라서 자손 노드들의 상태를 보고 하나라도 UNWATCHED상태라면 해당 노드에 감시카메라를 설치하는 알고리즘을 사용할 수 있다.

또한 "모든 갤러리가 서로 연결되어 있지 않을 수도 있습니다."라는 조건이 있으므로 모든 노드가 방문되었는지 확인하는 절차도 필요하다.

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

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

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

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

입력으로 주어지는 특정한 문자열 패턴들이 나타나지 않게 알파벳 소문자로만 이뤄진 n자리 암호를 만들 수 있는 모든 경우의 수를 10007로 나눈 나머지를 구하는 문제이다.

bruteforce로 풀게되면 26^n의 시간복잡도를 가지게 되므로 제한시간 안에 문제를 푸는것이 불가하다.

동적계획법을 이용하면 문제를 풀 수 있는데 그 방법이 매우 어렵고 까다롭다. (종만북의 연습문제중 가장 어려웠던것 같다.) 

먼저 입력으로 주어진 문자열 패턴들을 트라이로 만들고 각 노드마다 상태를 부여한다.

앞으로 만들어야하는 글자의 갯수 length, 현재 트라이의 상태를 state라 했을때 cache[length][state]형태의 캐시를 이용한다.

하지만 이렇게 트라이를 이용한 동적계획법을 구현하기 위해서는

먼저 트라이의 각 노드들이 실패연결과 출력문자열을 가지고 있어야하고, 각 노드마다 상태 번호가 부여되야 한다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/26.%20Trie/nh.cpp

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

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

BOJ 문제 링크 : https://www.acmicpc.net/problem/1759

L개의 알파벳이 주어졌을때 L개중 C개를 다음 조건에 맞게 골라 나열하여 출력하는 문제이다.

조건은 C개의 알파벳을 나열한 문자열은 알파벳순으로 정렬되 있어야 하고 모음이 한 개 이상 자음이 두 개 이상이여야 한다.

L개의 문자들을 알파벳 순으로 정렬한후 순서대로 조합하는 방식으로 문제를 해결 할 수 있다.

이때 완성된 암호의 모음의 갯수와 자음의 갯수를 확인하는 유효성 검사가 출력전에 선행되야 한다.

코드 원본 : https://github.com/sbl133/BOJ/blob/main/%231759.cpp

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