Hyun's_Devlog

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

투 포인터 문제다. 예전에 런타임 에러를 마주하고 해결하지 못해 포기했다가 최근에 다시 봐서 해결한 문제. 

풀이

입력된 레고를 길이 순으로 정렬한 뒤 처음과 끝에서 탐색하면서 범위를 좁히면 된다. 탐색 도중 조건이 맞으면 바로 결과를 출력. 대신 테스트 케이스의 제한이 안 적혀있어 결과물을 모아서 한 번에 출력했다. 스위프트의 print() 메서드가 다른 언어에 비해 속도가 느리기 때문에 출력 양이 많은 경우에는 이런 식으로 해결하는 경우가 많다.

정답 코드

주석처리 부분이 런타임에러 코드의 수정 전 부분이다. 무한 입력을 받기 위해 while let 문을 사용했는데, 마지막 입력없이 끝나는 부분에서 공백 문자열에 대해 정수형 변환이 일어나 런타임 에러가 일어나지 않았나 생각해본다. xcode에서는 아무 문제없이 빌드되길래 다른 케이스에서 인덱스 오류인 줄 알고 여러 번 삽질했다..

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

다익스트라 알고리즘을 통해 풀 수 있다.

풀이

출발 노선 지점에서 각 지점으로의 최소비용을 담을 dist:[Int]() 배열을 생성한다. 이후 입력되는 노선의 정보를 저장한 후 너비 우선 탐색을 통해 다음 노선까지의 비용이 더 저렴하다면 dist 원소 값을 경신한 후 값이 경신된 해당 지점을 큐에 담아 다음 탐색 경로에 추가해주면서 탐색을 수행하면 된다.

참고해야 할 점은 입력받은 노선 정보를 비용 기준 오름차순 정렬해주어야 한다는 점이다. 다익스트라 알고리즘의 조건인 최소비용부터 탐색한다는 조건을 생각하지 못해 정렬하지 않은 채로 제출했었는데 시간 초과가 일어났었다. 곰곰이 생각해보니 A -> B로 가는 노선이 여러 개일 경우 정렬을 하지 않은 채로 탐색을 수행한다면 큐에 중복된 경로를 추가하게 되어 불필요한 탐색을 수행하게 된다.

정답 코드

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

그리디 문제다. 숫자가 아닌 문자열로 접근해서 풀었다. 숫자로 접근하게 된다면 최대 범위가 0 ~ 2,000,000,000 이므로 분명 시간 초과가 일어날 것이다. 따라서 8이 나올 수 있는가에 대한 조건만 생각해서 접근해야 한다.

우선 자릿수의 변동이 일어나면 8이 나올 수 없다. 즉 L과 R의 자릿수를 먼저 체크해야 하고, 이후 자릿수가 같다면 어느 자리까지 제한하였는지를 확인해야 한다. 각 자릿수의 숫자가 같을 경우에만 8의 개수를 세고 각 자릿수가 달라지는 시점이 온다면 해당 숫자는 8이 아닌 수로 바꿀 수 있다는 뜻으로 접근하면 된다.

풀이

자릿수가 다르다면 8이 없는 구간이 생길 수밖에 없으니 0을 출력하면 된다.

자릿수가 같다면 가장 큰 자릿수부터 숫자를 비교하여 8의 개수를 세면 되는데, 서로의 숫자가 다르다면 더 이상 숫자를 셀 필요 없다.

정답 코드

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

기하학에 관련된 문제다. 다각형의 면적을 계산하는 방법만 안다면 쉽게 풀 수 있는 문제다.

풀이

https://ko.wikipedia.org/wiki/신발끈_공식

신발끈 공식을 이용하여 풀었다. 다각형을 이루는 모든 꼭지점의 좌표를 알면 좌표를 이용해 다각형을 여러 개의 삼각형으로 쪼개 넓이를 구하는 공식이다.

다각형의 넓이 = ABS(sum1 - sum2) / 2

꼭지점이 시계방향 혹은 반시계 반향으로 순차적으로 주어지게 될 경우, 다음과 같이 순환하는 형태로 줄지어 격자 형태로 곱해서 나온 누적합 sum1, sum2의 차를 2로 나누면 다각형의 넓이를 구할 수 있다. 다행히도 문제에 다각형을 이루는 꼭짓점의 순서대로 입력이 되기에 입력되는 순서 그대로 배열에 담아내면 손쉽게 답을 구할 수 있다.

swift에서는 자릿수 반올림 함수가 제공되지 않으므로 원하는 자릿수에서 반올림 하기위해 직전 자릿수까지 10을 곱해준 뒤 반올림 함수 round()를 이용하였고 다시 자릿수만큼 나누어 주었다.

정답 코드

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

그래프 탐색 문제다. 너비 우선 탐색으로 풀었다. 상어의 움직임에 대해 오래 고민했던 문제다.

풀이

상, 좌, 우, 하 순서로 너비 우선 탐색을 수행한다. 빈 곳이거나 같은 사이즈의 물고기를 만난다면 큐에 담아 이동을 수행, 자신보다 작은 사이즈의 물고기를 만나면 해당 좌표를 다른 배열에 저장하였다.

탐색이 끝난 뒤 문제의 조건에 맞게 먹을 수 있는 물고기가 담긴 배열을 시간, x좌표, y좌표 순으로 정렬한 뒤 가장 가까운 좌표로 이동하여 해당 물고기를 먹으면 된다. 처음에는 이러한 정렬 없이 먹을 수 있는 물고기를 만나면 바로 먹어버리고 탐색을 종료했는데, 같은 거리에 있는 먹을 수 있는 물고기에 대한 조건이 안 맞아 오답이 나왔다.

탐색 함수는 상어가 이동한 좌표와 걸린 시간을 반환하게 하였다. 상어의 좌표에 이동이 없는 경우 먹을 수 있는 물고기가 없는 것으로 판단하여 반목문을 빠져나오는 것으로 코드를 작성했다.

정답 코드

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

그래프 탐색 문제다. 너비 우선 탐색으로 해결했다.

풀이

0부터 9999에 해당하는 움직임을 담는 문자열 배열을 생성한 뒤, 입력되는 A부터 시작하여 너비 우선 탐색을 수행한다. D, S, L, R 연산에 해당하는 숫자를 만들고 해당 인덱스의 배열에 현재까지의 움직임에 해당 움직임 문자열을 더하여 탐색을 수행한 뒤 탐색이 끝나면 B인덱스의 배열 값을 출력하면 된다.

정답 코드

시간초과를 마주하여 조금 더 동작을 빠르게 해결하기 위해 27번 라인에 B번째 배열의 값이 갱신되면 탐색을 곧바로 종료하는 조건을 추가하였다.

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

백트래킹 대표 유형 문제다. 예전에 시도했던 문제지만 시간제한에 걸려 풀지 못했던 문제다. 결국 다른 분의 풀이를 확인하고 풀 수 있었다.

풀이

해당 문제는 같은 행과 열, 그리고 우측에서 좌측으로 내려오는 대각선과 좌측에서 우측으로 내려오는 대각선이 겹치는지 확인하여 N번의 조건을 백트래킹을 통해 풀어야 한다. 단순하게 매 횟수마다 2차원 배열의 true false를 통해 조건을 탐색하게 된다면 시간 초과가 일어나게 된다.

이번 풀이는 열, 좌측 하행 대각선, 우측 하행 대각선을 담당하는 Bool 타입 1차원 배열을 각각 따로 생성하여 조건을 확인하는 방법이다. 행에 대한 배열이 없는 이유는 한 행에 하나의 퀸만 놓을 수 있기에 따로 퀸을 놓게 되면 바로 다음 행으로 넘어가기 때문이다.

N = 4일 경우의 각 배열의 양상이다. 2차원 보드판 위치의 기준으로 각 배열에 확인해야 하는 인덱스를 넣어 놓았다. 3가지 배열 모두 해당 인덱스에 퀸이 없을 경우에만 퀸을 배치하고 다음 열로 넘어가게 된다.

정답 코드

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

그래프 탐색을 통해 해결할 수 있는 문제다. 너비 우선 탐색으로 진행했다.

풀이

지도를 탐색하면서 인접 배열과의 인구수를 비교, 조건에 맞다면 큐에 담아낸 뒤 마지막에 큐에 담겨있는 좌표를 확인하면서 값을 갱신한다. 문제에서는 몇 차례의 변동이 일어났는지 횟수를 요구하기 때문에 반복문으로 수행한 뒤 Bool 타입의 flag 변수를 사용하여 종료 여부를 확인하였다.

정답 코드