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/12015

dp를 통해서 풀게 되면 수열의 크기 때문에 시간 초과가 일어난다. 문제의 힌트에 이분 탐색을 이용하라고 되어있어 어느 부분에 이분 탐색을 적용할 수 있는지 고민해보았지만 다른 풀이를 확인하고 나서 알았다.

풀이

최장 증가수열을 담을 배열 arr을 생성 후 입력받은 수열을 순서대로 탐색하면서 해당 숫자가 배열의 마지막 숫자보다 큰 경우, 배열에 추가해주고 작은 경우, 이분 탐색을 통해 수열의 숫자보다 작은 숫자를 찾으면 해당 위치로 들어가면 된다.

주의할 점은 해당 배열은 정답 배열과 크기만 같지 원소는 다르므로 최장 증가수열을 반환하는 문제에는 오답처리를 받게 된다.

정답 코드

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가지 배열 모두 해당 인덱스에 퀸이 없을 경우에만 퀸을 배치하고 다음 열로 넘어가게 된다.

정답 코드