Hyun's_Devlog

https://www.acmicpc.net/problem/1238

다익스트라 알고리즘으로 접근한 문제다. 힙 구현이 필요하다. 직접 구현할 역량이 안되기에, Rhyno님이 작성한 힙을 사용하였다.

풀이

간선과 가중치를 입력받은 map 배열을 통해, 다익스트라 알고리즘을 사용한다. 양방향 간선이 아닌 단방향 간선이기에 우선 파티 장소 x에서 각 마을로 되돌아가는 배열을 생성, 다익스트라 알고리즘을 통해 각 인덱스에 저장. 이후 1 ~ n번 마을에서 x로 향하는 최단거리를 한 번 더 다익스트라 알고리즘을 통해 방금 저장한 배열에 추가시켜 준다. 마지막으로 배열에 담긴 최댓값을 출력한다.

정답 코드

https://www.acmicpc.net/problem/2056

위상정렬과 동적계획법으로 접근가능한 문제다.

풀이법

처음에는 단순히 위상정렬을 통해 큐에 접근할 때마다 가장 오래 걸린 작업시간들을 더하면 될 것이라 생각했다. 하지만 해당방법은 틀린 방법이 다.

후속이 없는 작업의 경우, 다음 탐색에  영향을 끼치지 않아야 하는데, 처음생각한 방법은 이러한 부분을 제외시키지 못했다. 따라서 해당 작업을 완료하는데 걸리는 총시간을 담은 dp 배열을 생성한 뒤, 동적계획법으로 접근해야 한다. next는 다음 작업, curr는 현재작업을 의미할 때, 점화식은 다음과 같다. 여기서 time배열은 순수 작업시간을 의미한다.

dp[next] = max(dp[next], dp[curr]+time[next])

위상정렬을 통한 그래프탐색 이후, dp배열의 최댓값을 출력하면 된다.

정답 코드

https://www.acmicpc.net/problem/14567

위상정렬 문제다.

풀이

문제에서 요구하는 것은 선수과목의 순서가 아니라 각 과목을 듣기 위한 최소 학기수.

즉 위상정렬을 사용하여 큐에 몇번 접근하는지를 파악하면 된다. 

입력되는 값을 통해 각 노드의 진입차수를 저장. 진입차수가 0인 노드를 큐에 담아놓고 그래프탐색을 수행하면 된다.

그래프탐색을 통해 다른 노드로 진입시, 해당노드의 진입차수를 하나씩 차감. 0이 된다면 다음 탐색큐에 추가하면 된다.

문제의 정답을 계산하기 위해 반복문을 구분하여 탐색해야 한다. 해당 부분은 코드르 보는 게 이해하기 쉬울 것이다.

정답 코드

https://www.acmicpc.net/problem/1584

다익스트라 알고리즘으로 접근한 문제다.

풀이

출발지와 목적지가 이미 정해져 있는 문제이므로 거리정보를 담아둘 배열을 생성. 최대 비용 250000(500*500) 보다 큰 250001로 초기화시켜 둔다. 출발지 (0,0)은 이미 도착한 것이므로 비용을 0으로 시작. 너비우선탐색을 수행하여 비용이 더 적게 드는 경우 비용을 갱신하고 해당 좌표를 큐에 담아 탐색을 수행하면 된다. 탐색이 끝나면 가장 마지막 위치의 비용을 출력하면 된다.

정답 코드

https://www.acmicpc.net/problem/25587

유니온 파인드 문제다. 푸는데 시간이 좀 걸렸다.

풀이

루트여부 및 원소의 크기정보, 배수로 용량, 강수량 정보를 담은 원소 n개의 배열을 생성하여 유니온 파인드를 수행한다. 여기서 중요한 점은 쿼리입력을 받을 때, 중간마다 출력을 요구한다는 점이다.

처음에는 출력을 요구하는 2가 입력될 때마다 배열을 전부 탐색하여 루트노드를 만나면, 홍수여부를 체크한 뒤 원소의 개수만큼 개수를 계산하여 출력하였으나, 시간초과를 받았다.

보통 시간복잡도를 계산할 때 1초당 1억 연산으로 따진다. 쿼리가 전부 2라면, 배열의 최댓값*쿼리 최댓값(100000*100000)으로 시간초과는 당연한 결과였다. 

따라서 생각해낸 풀이는 처음 정보가 주어지고 나면 배열을 탐색해 홍수가 나는 지역의 개수를 전역변수로 파악. 이후 유니온이 일어날 때마다 해당 지역이 홍수가 일어나는지, 일어나지 않는지를 파악해 전역변수를 갱신하는 것으로 접근하였더니 시간초과를 피할 수 있었다.

정답 코드

언제쯤이면 고수가 될 수 있을까..

https://www.acmicpc.net/problem/2350

[2610] 회의준비와 결이 비슷한 문제다. 

풀이

유니온파인드와 그래프탐색으로 접근했다. 가중치가 큰 순으로 간선을 정렬한 뒤 순서대로 유니온을 수행, 루트가 같다면 결합하지 않는다.

이후 입력되는 출발지와 도착지를 기준으로 너비우선탐색을 수행. 그래프를 탐색하면서 가중치를 수정해나가면 된다. 

처음에는 (k횟수만큼) 그래프와 루트정보를 매번 초기화하고, 입력되는 출발지와 도착지를 기준으로 유니온을 하면서 그래프를 탐색했으나, 시간초과발생. 생각해보니 간선을 한 번만 탐색하고도 cost를 출력할 수 있게 접근이 가능했었다.

정답 코드

https://www.acmicpc.net/problem/15991

다이나믹 프로그래밍 문제다.

풀이

우선 1부터 6까지 1,2,3을 이용한 대칭 수식을 생각하면 점화식을 위한 조건이 만들어진다.

7부터는 앞서 생각한 경우의 수식에 양쪽으로 1+...+1, 2+...+2, 3+...+3의 형태로 대칭으로 늘려나가면 된다.

즉 dp[num] = dp[num-2] + dp[num-4] + dp[num-6]이라는 점화식을 세울 수 있다.

7부터 100,000까지 반복문을 돌려 정답배열을 만든후 입력값을 인덱스로 정답을 출력하면 된다.

정답 코드

점화식을 세우는건 항상 어렵다..,

https://www.acmicpc.net/problem/2232

너비우선탐색으로 접근한 문제다.

풀이

입력받은 지뢰의 충격이 큰 순서부터 터트리면서 너비우선탐색을 수행한다. 이때 터트리는 지뢰의 번호를 입력받은 뒤 오름차순으로 정렬하여 출력하면 된다.

정답 코드