devbelly

문제 https://www.acmicpc.net/problem/1662 알고리즘 재귀 풀이 압축된 문자열이 주어졌을 때, 원래 문자열의 길이를 구하는 문제입니다. 재귀적인 시각으로 문제를 바라보면 이해하기 쉽습니다. $abcd(efg(hi))$ 와 같이 문자열이 주어졌다면 그대로 보기보다는 $abcd(*)$ 와 같이 이해를 해봅시다. 문제에서 주어진 문자열을 해결하는 함수 $solve()$가 있다면 우리는 $abc$ 길이에 $d$ X $solve(*)$ 와 같이 문제를 나눌 수 있습니다. $solve()$ 함수 내에서 또 다른 $solve()$를 호출하여 재귀적으로 해결하도록 합시다. 이 문제에서 생각해야할 부분은 괄호를 제외한 *에 해당하는 문자열을 인자로 넘겨주는 방법입니다. 올바른 괄호 문자열 문제..

문제 https://www.acmicpc.net/problem/5214 알고리즘 BFS 풀이 역들을 잇는 하이퍼튜브들이 주어질 때, $N$역으로 가기 위해 거쳐야하는 최소 역의 수를 구하는 문제입니다. 하이퍼튜브마다 일일이 역들을 연결하게 되면 메모리초과가 발생합니다. 대신에 하이퍼튜브마다 임의의 정점을 하나씩 만든 후, 각 역과 새로 만든 임의의 정점끼리 연결하여 메모리를 절약하였습니다. 위 그림은 문제에서 주어진 첫번째 예시에서 첫번째 하이퍼튜브와 두번째 하이퍼튜브를 시각화한 것입니다. 저는 튜브마다의 임의의 정점을 100005+$i$로 하였습니다. 검은 실선을 가중치 1로 설정하여 풀고난 후, 마지막에 반을 나누어 실제로 거친 역의 수를 구했습니다. 코드 #include #define rep(i, ..

문제 https://www.acmicpc.net/problem/2437 알고리즘 Greedy 풀이 $N$개의 저울이 주어졌을 때, 잴 수 없는 무게의 최솟값을 구하는 문제입니다. 기존에 잴 수 있는 구간이 [0,R] 일 때, 새로운 추 A가 새로이 등장하면 새롭게 잴 수 있는 구간은 [A,A+R] 일 것입니다. 만일 R+1>=A 라면 이 구간은 [0,A+R]로 통합되어 잴 수 있는 구간이 새로이 갱신되겠지만 아니라면 답은 R+1입니다. 즉, 추의 무게를 정렬한 후 R과 추가할 추 A의 무게를 계속해서 비교해주면 됩니다. R은 잴 수 있는 무게의 최댓값이므로 지금까지의 추의 무게의 총합입니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #defi..

문제 https://www.acmicpc.net/problem/5917 알고리즘 Dijkstra 풀이 최단거리 중 하나의 간선의 값을 두배로 하였을 때의 최댓값을 구하는 문제입니다. 다익스트라임은 최단거리임을 보고 알 수 있습니다. 문제 제한은 $N$이 100 이하, $M$은 10000 이하입니다. 단순한 접근으로는 $M$의 간선들을 하나씩 두배로 만든 후 그때마다 새로이 다익스트라를 사용하는 것입니다. 하지만 $M$제한이 10000이므로 이 방법은 무리가 있습니다. 이 방법에는 불필요한 부분이 있습니다. 바로 최단거리에 포함되지 않는 간선들 또한 두 배로 바꾸는 것입니다. 이는 아무런 의미가 없는 행동입니다. $N$개로 이루어진 노드에서 최단거리는 최대 $N-1$개의 간선을 통해 이루어져 있습니다. 즉..

문제 https://www.acmicpc.net/problem/17612 알고리즘 Priority queue 풀이 문제에서 정의한 계산 순서를 구하는 문제입니다. 우선순위 큐를 이용한 구현문제에 가깝습니다. 빈 계산대가 여러 개 있다면 번호가 작은 계산대부터 계산해야 하므로 빈 계산대를 저장하는 $counter$변수, $info$ 클래스를 정의하여 각 아이디와 계산시간 및 카운터 정보를 기록하고 해당 클래스 객체의 우선순위를 위한 $compareInfo$ 클래스를 정의합니다. 다만, 우선순위큐를 통해 카운터에서 계산될 순서를 저장하게 될 때, 가장 빠르게 계산이 끝나는 $info$ 객체를 우선순위 큐에서 뽑았다면, 나머지 우선순위 큐 안에 있는 $info$ 객체의 $time$ 변수 또한 업데이트를 모두 ..

문제 https://www.acmicpc.net/problem/10652 알고리즘 Dijkstra, BFS 풀이 Bessie와 Elsie가 돌아다닐때 드는 에너지와 Piggy Back 상태에서 드는 에너지가 주어졌을 때, $N$까지 도달하기 위한 최소에너지는 구하는 문제입니다. 3인통화 문제와 굉장히 유사합니다. 도착지도 하나의 소처럼 취급을 하여 세 마리의 소에서 각각 다익스트라를 사용하면 문제가 해결됩니다. 다만, 각 소마다 그래프를 이동할 때 드는 비용은 동일하므로 다익스트라 대신 BFS를 사용하면 더 빠르게 문제를 풀 수 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for (int i = 1; i..

문제 https://www.acmicpc.net/problem/9869 알고리즘 Greedy 풀이 소마다 우유생산량과 수명이 주어질 때, 최대 우유생산량을 구하는 문제입니다. 자주 보이는 그리디 테크닉입니다. 시간을 0부터 접근하는 대신, 가장 마지막 시간부터 0까지 역순으로 소들을 고려합니다. T에 해당하는 시간에 젖을 짤 수 있는 소들을 PQ에 넣습니다. 이렇게 하면 현재 젖을 짤 수 있는 소들이 PQ에 담기게 됩니다. 이 가운데 우유 생산량이 높은 소부터 젖을 짜나가면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i N; vector vt; rep(i, N) { int..

문제 https://www.acmicpc.net/problem/18785 알고리즘 DFS 풀이 Bessie가 트리위에 주어진 맵을 이동해가며 시계를 조정할 때, 모든 시계가 가르키는 시간이 12시가 되도록 할수 있는 방의 시작갯수를 구하는 문제입니다. 임의의 출발지에서 모든 노드가 12가 될 수 있는지를 확인하는 것이 목표입니다. $N$제한이 2500이므로 $O(N^2)$에 근접하는 알고리즘을 떠올려봅시다. 첫 번째로는 리프노드의 시간을 12시로 맞추기 위해서는 무조건 리프노드와 리프노드의 부모를 계속해서 왔다갔다 해야지만 리프노드를 원하는 숫자 12로 맞출 수 있습니다. 12로 설정된 리프노드는 우리의 관심사 밖이므로 제거되고 리프노드의 부모였던 노드는 새로운 리프노드가 됩니다. 위 시뮬레이션을 계속 ..