Hyun's_Devlog

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

유니온 파인드로 접근했다.

풀이

원수를 담는 배열 enemy 2차원 배열을 생성하여 원수 관계가 들어오면 양방향으로 추가.

친구 관계가 입력되면 유니온을 통해 컴포넌트를 합친다.

모든 입력이 들어오고 나면 enemy 배열을 탐색하면서 원수의 원수를 찾아 서로 연결해 주면 된다.

남아있는 컴포넌트의 개수를 출력하면 정답이다.

정답 코드

유니온 파인드로 접근하였다.

풀이

문제의 핵심은 가중치가 주어지는 간선은 오로지 한 개라는 것. 즉 가중치가 있는 간선을 거쳐가는 경로의 개수를 찾는 문제다. 가중치가 없는 간선들을 먼저 연결해 준 뒤 마지막으로 가중치가 존재하는 간선을 연결할 때, 연결하려는 두 컴포넌트의 개수를 서로 곱해주면 해당 간선을 거쳐가는 간선의 개수를 구할 수 있게 된다. 예제를 기준으로 그림으로 설명하면 다음과 같다.

2번 정점과 3번 정점을 연결할 때, 1-3, 1-4, 1-5, 2-3, 2-4, 2-5의 경로에서 2-3 간선을 이용해야만 한다. 즉 2번 정점이 속한 컴포넌트의 정점개수와 3번 정점이 속한 컴포넌트의 정점 개수를 서로 곱해주면 정답이다.

단, 예제입력 2와 같이 가중치가 존재하는 간선을 연결할 때 이미 두 정점이 같은 컴포넌트인 경우 비용 0인 간선으로 우회가 가능하기에 이때는 정답이 0이다.

따라서 유니온 파인드 알고리즘을 통해 각 컴포넌트의 개수를 핸들링하여 정답을 출력해 주면 된다.

정답 코드

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

기본적인 MST 문제다. 

풀이

두 가지 방법으로 풀었다. 첫 번째로 접근했던 방법은 시간이 조금 빠르지만 코드가 조금 더 길어진다. 

간선의 가중치가 작은 순서로 두 정점 U, V를 연결할 때, 조건을 추가했다. 

두 정점에 워프를 설치하는 비용 > 두 정점을 연결하는 간선 비용 + min( U정점에 워프 설치 비용, V정점에 워프 설치 비용)

두 정점에 탈출구 워프를 설치하는 비용이 더 저렴하다면 두 정점은 연결하지 않는다. 반대로 두 정점에 탈출구 워프 설치 비용이 더 비싸다면 간선을 연결하고 워프를 설치비용이 더 저렴한 쪽이 루트가 되어 연결하면 된다.

이후 각 컴포넌트의 루트 정점에 워프설치 비용을 더해주면 가장 작은( 간선 + 워프 설치 ) 비용이 나오는데, 마지막으로 한번 더 모든 정점에 워프 설치비용과 비교하여 더 작은 쪽을 출력하였다.

두 번째 방법은 탈출구를 0번 정점으로 취급하여 간선정보를 정렬한 뒤 MST를 수행하면 간단하게 구할 수 있다.

정답 코드-1

정답 코드 - 2

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

MST 알고리즘의 기본문제다. 크루스칼 알고리즘을 통해 해결했다.

유니온 함수의 구현에서 사소한 실수를 해서 WA를 받아 당황했지만 실수를 금방 발견했다.

풀이

주어지는 간선은 양방향 간선이므로 u (0 ..< N), v (u+1 ..< N) 탐색을 통해 중복되는 정보는 배제하고 탐색하였다.

간선이 음수면 이미 연결된 고속도로 이므로 절댓값을 totalCost에 더한 뒤, 두 정점을 연결한다. 주의할 점은 이미 부모가 같은 정점끼리의 간선이 음수로 주어질 수도 있으므로 있으므로 예외처리를 해주어야 한다.

나머지의 경우는 edges 배열에 담아낸 뒤 비용이 적은 간선부터 유니온 함수를 수행한다. 이때 연결된 간선은 배열에 따로 정보를 담아주었다가 출력해 주면 된다.

정답 코드

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

배열에 관련된 구현문제다.

풀이

일반적인 풀이 방법은 문제에 주어진 대로 2차원 배열을 탐색하여 반시계방향으로 요소를 옮겨주면 된다.

각 그룹이 R번 회전해야 하므로 이 방법으로 구현하게 된다면 O(N*M*R)에 해결할 수 있다.

하지만 swift의 경우 다른 언어에 비해 느려서 해당 방법으로는 시간초과를 받는다.

R번 회전한다는 것은 결국 원점으로 돌아올 수 있다는 것이고 이는 곧 회전 수를 줄일 수 있는 요인이라 생각했다. 문제는 회전해야 하는 그룹의 크기가 전부 달라서 이를 어떻게 해결할까 고민하였다.

https://www.acmicpc.net/board/view/86800

질문 탭을 보니 2차원 배열을 1차원으로 접근해 보라는 힌트를 발견. 해당 힌트를 통해 문제를 해결할 수 있었다.

입력예제 1을 기준으로 설명하면 다음과 같다.

회전시켜야 할 그룹을 파악한 후 1차원 배열로 생성.

(R % 각 배열의 크기) 부분에서 분리하여 순서를 바꾼 배열을 만든다.

이어서 다시 회전시켜야 할 그룹의 자리에 1차원 배열의 요소를 담아주면 O(2*N*M)만에 결과를 얻을 수 있다.

정답 코드

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

스택을 활용한 문제다. 

풀이

입력되는 모든 키를 비교하게 되면 당연하게도 시간초과가 일어난다. 풀이를 찾아보니 스택을 사용한다면 O(N) 만에 탐색이 가능했다.

우선 주어지는 현재 키를 순서대로 스택에 담아낼 것이다. 

(키 높이, 인원)를 담는 비열을 생성하여 현재 주어진 키와 스택의 top과 비교하여 쌍을 계산하면 된다. 

스택이 비어있다면 당연하게도( 현재 키 높이: 인원(1) )을 담고 다음 정보를 입력받는다.

크게 두 가지 경우로 나뉜다.

1. top의 키높이가 현재 키높이와 같은 경우  -> top의 인원수만큼 쌍으로 추가

2. top의 키높이보다 현재 키높이가 큰 경우 -> 인접한 경우이므로 쌍으로 추가

위 두 가지 경우는 top의 키높이가 현재 키높이보다 클 때까지 혹은 스택이 빈상태가 될 때까지 pop 연산을 수행한다.

pop 연산을 수행한 이후에 스택이 비어있지 않다면 top에 해당하는 키와 현재 키와는 인접한 경우이므로 쌍으로 추가할 수 있다.

키높이가 같은 경우를 거쳤다면 (현재 키높이 : 추가했던 인원수+1) 형태로 스택에 추가.

그렇지 않았다면 (현재 키높이 : 인원수 1) 형태로 스택에 추가하면 된다.

즉 스택이 top으로 갈수록 내림차순을 유지하면 서로 바라볼 수 있는 쌍을 알아낼 수 있다.

정답 코드

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

구현문제다. 입력되는 경사로의 정보를 어떻게 탐색할지 고민했다.

풀이

입력되는 경사로의 정보를 ( 높이(숫자), 길이(연속되는 갯수) ) 형태의 튜플을 담는 배열로 정리하여 탐색을 수행한다.

다음과 같은 조건을 확인하여 갯수를 추가하였다.

• 현재 위치와 다음 위치와의 높이 차이가 1 이어야 한다.
• 다음 경사로의 높이가 더 높은 경우라면 현재 위치의 길이를 확인한다.
• 현재 경사로의 높이가 더 높은 경우라면 다음 위치의 길이를 확인한다.
• 만약 경사로를 놓아야 하는 위치에 처음 경사로가 설치되는 경우라면 해당 위치의 길이가 L 이상인지 확인한다.
• 만약 경사로를 놓아야 하는 위치에 경사로가 이미 설치된 경우라면 해당 위치의 길이가 2*L 이상인지 확인한다.

정답 코드

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

구현 문제다. 특정 알고리즘보단 문제에 어떻게 접근해야 할지 고민해 보게 되는 유형이다.

풀이

입력된 벽의 높이를 좌에서 우로 탐색한다. (탐색값 중 가장 높은 높이 - 현재높이) 값을 임시 변수에 누적. 가장 높은 높이가 갱신되면 여태 구한 임시 변수의 값을 최종 정답에 반영. 새로 바뀐 최대 높이를 기준으로 다시 빗물을 계산한다. 

탐색이 끝나고 임시 값을 최종 정답에 반영하지 못했다면, W-1번부터 마지막으로 갱신된 가장 높은 높이의 벽까지 역탐색하며 빗물을 계산하면 된다.

정답 코드