백준 - 순열 사이클(Swift) 문제 설명 https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 나의 풀이 처음 문제를 봤을때는 왜 3 2 7 8 1 4 5 6의 순열이 오른쪽처럼되는건지 이해를 하지 못했다. 이는 결국 1부터의 인덱스와 이 숫자들간에 간선이있음을 나타내는 것임을 알았고 사이클이 몇개 존재하면되는지를 확인하면 되기 때문에 재귀방법으로 문제를 해결했다. 하지만 ..

백준 - 기차가 어둠을 헤치고 은하수를(Swift) 문제 설명 https://www.acmicpc.net/problem/15787 15787번: 기차가 어둠을 헤치고 은하수를 입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. www.acmicpc.net 나의 풀이 입력으로 100,000이 들어오지만 기차에서 좌석을 한 칸씩 당기거나 미는 정도의 행위만 하기 때문에 O(n)으로 처리할 수 있는 문제다. 그렇기 때문에 요구사항대로 구현만 잘 해주면 문제는 쉽게 풀린다. import Foundation struct Train: Hashable { var seats: [Int] ..

백준 - 아기 상어(Swift) 문제 설명 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 나의 풀이 다른 분의 블로그를 참고했지만 이제 이런 문제는 풀 줄 알아야한다. 아기상어의 위치에서 최소의 위치를 찾는 것은 BFS이며 2차원 배열을 기존의 배열, 근접한 물고기들의 배열을 선언함으로써 문제를 풀었다. 그리고 자신보다 큰 물고기의 경우에는 아예 어떠한 로직도 거치지 않음으로써 무시하고 지나갈 수 있게 만들었다. 마지막으로 방문표시를 ..

백준 - 감시(Swift) 문제 설명 https://www.acmicpc.net/problem/15683 나의 풀이 철저한 구현문제이고 이 분의 블로그를 많이 참고했다. https://0urtrees.tistory.com/227 swift DFS 완전탐색, 백준 15683 감시 문제풀이 백준 15683번, 감시 문제설명 오늘은 백준 15683, 감시 문제를 풀어보겠습니다. 감시 문제는 solved.ac기준, 골드5로 코딩테스트 기준 중후반에 나올 수 있는 수준의 문제입니다. 시간 제한은 1초, 메모 0urtrees.tistory.com 하나의 좌표에서 옆으로 퍼지는 재귀는 써봤지만 이렇게 각각의 좌표에 있는 것들에 대해 재귀를 하는 것은 처음이었다. 우선 cctv의 좌표를 cctv배열에 넣고 DFS를 돌..

백준 - 드래곤 커브(Swift) 문제 설명 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 나의 풀이 처음 문제를 봤을때는 잘 이해하지 못했다. 오른쪽 방향에 대해 시계방향으로 전환하면 아래쪽 방향이 되고 그것을 끝 점에 붙이면 아래에 가는 게 아닌가? 생각이 들었는데 그냥 현재의 드래곤 커브를 시계방향으로 90도 돌리는 것만 집중하면 되는 것이었다. 그래서 1세대, 2세대, 3세대를 그려보면서 규칙을 찾았는데 위로..

백준 - 미세먼지 안녕!(Swift) 문제 설명 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 나의 풀이 크게 어렵지않은 문제였지만 시계방향 혹은 반시계방향으로 돌때 마지막 요소는 0으로 해야하는 것을 놓치고 조금 시간이 걸렸다. 이제 네 방향으로 탐색하는 문제는 조금 익숙해진 것 같다. import Foundation let input = readLine()!.components(separatedBy:" ").map{Int($0)!} le..