Hyun's_Devlog

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

피보나치 문제다. 해당 문제 덕분에 피보나치수를 구하는 다양한 방법들 있다는 것을 알았다.

풀이

$$F_{m+n} = F_{m-1} F_{n} + F_{m} F_{n-1}$$

도가뉴 항등식을 이용하였다. 해당 수식을 정리하면 

$$F_{2n} = F_{n} (F_{n} + 2F_{n-1})$$

$$F_{2n+1} = F_{n}^2 + 2F_{n+1}^2$$

위와 같은 수식을 얻을 수 있다.

해당 수식을 이용하면 기존의 피보나치수를 계산하는 방법보다 훨씬 적은 수의 호출을 통해서 값을 구할 수 있다.

메모리 초과를 피하기 위해 딕셔너리를 이용하여 수를 담아내었다.

정답 코드

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

구현문제다.

풀이

문제에 주어지는 대로 먼지를 흩뿌리는 함수 spread()와 공기청정기를 가동하는 cleanClock(), cleanAntiClock() 함수를 구현하여 접근했다. spread() 함수의 경우 한 좌표의 인접좌표에 대해서 동작을 구형했고, 배열을 모두 탐색하면서 값이 0 이상이라면 함수를 수행하는 방법으로 구현했다.

공기청정기의 경우 시계/반시계 방향으로 순회하면서 값을 옮겨주는 동작을 구현하였다. 마지막으로 배열을 탐색하여 먼지의 수치를 출력하면 된다.

정답 코드

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

문자열 문제다. 쉽게 풀 수 있지만 문제 자체가 조금 번거롭기도 하고 꼼꼼히 보지 않으면 실수하기 쉽다. 

풀이

배열에 담아 각 조건을 탐색하면 된다. 1번 조건의 "dip은 jiggle을 춘 다음이나 다다음, 또는 twirl을 추기 전에 출 수 있다." 부분에서 twril이 문장 이후 아무 데나 나오면 되는 것으로 착각했다. dip 바로 뒤에 twirl이 오는지만 확인하면 된다.

다른 조건들의 경우 배열의 contain 메소드를 사용하여 풀어내면 된다. 단 출력할 때의 문장 포맷을 잘 확인하고 출력하자. 제대로 확인 안 해서 틀린 부분을 찾아내느라 시간을 낭비했다. 문제를 꼼꼼히 읽었는지를 요하는 문제다.

정답 코드

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

다익스트라 알고리즘으로 접근한 문제다.

풀이

너비우선탐색을 수행한다. 다익스트라 알고리즘의 특성상 우선순위 큐를 사용해서 풀어야 하지만, 문제의 N값이 크지 않기에 배열을 정렬하여 풀어도 시간초과는 피할 수 있다. 스위프트의 경우 우선순위큐를 직접 구현해야하기에 귀찮다.

방문여부를 저장할 2차원 visited 배열, 각 좌표에 도둑루피의 값을 담을 2차원 map 배열과 해당좌표까지의 최저 cost를 담을 2차원 cost배열을 생성한다. cost 배열은 INF로 초기화한 뒤 탐색을 수행한다. 

x, y, cost 정보를 담아낼 배열을 생성한다. 배열에서 cost가 가장 작은 좌표를 먼저 방문하여 (현재 좌표의 cost + 인접배열의 cost값)을 계산하여 인접배열의 cost를 더 작은 값으로 갱신한다. 다음 탐색에 cost가 가장 작은 값을 방문해야 하니 매 반복문의 마지막에는 큐를 정렬해 준다.

탐색이 끝나면 목적지인 cost배열의 가장 마지막 값을 출력하면 된다.

정답 코드

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

문자열, 구현 문제다.

풀이

입력받은 개미의 알파벳과 우측 좌측을 나타내는 문자열로 튜플을 생성한다. 우측으로 향하는 개미와 좌측으로 향하는 개미의 알파벳을 붙여 튜플 배열을 생성 후, T번의 반복문을 통해 우측+좌측이 붙어있는 경우를 만나면 swap을 수행하였다.

정답 코드

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

그래프 탐색과 조합론으로 접근했다.

풀이

기본적인 그래프 탐색 문제와의 차별점은 지나가면 안 되는 간선이 주어진다는 점이다. 해당 부분을 어떻게 저장하고 핸들링할지 고민해하는 것이 이번 문제의 핵심.

인접행렬은 상, 하, 좌, 우로 4방향을 따져야 하므로 map[x좌표][y좌표][넘어갈 수 있는 방향 정보] 형태의 3차원 배열을 생성하였다. 즉 N*N*4 배열을 통해 너비우선탐색을 수행하여 해당 소가 방문하지 못하는 좌표에 다른 소가 있다면 문제에서 요구하는 답으로 판정하였다.

문제에서 요구하는 것은 길을 통해 건너야만 만날 수 있는 '쌍'을 찾는 것이니 중복을 없애기 위해 K에서 2개를 뽑는 조합 반복문을 통해 그래프탐색을 수행하였다.

정답 코드

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

그리디 문제다. 

풀이

소와 닭의 이동시간을 비교해서 조건이 맞는 경우를 세는 문제다. 단, 여기서 중요한 점은 소의 이동가능시간이다. 해당 부분의 정렬 조건에 대해 생각하는 데에 오랜 시간이 걸렸다. 

닭 i가 소 A와 소 B 두 마리 모두 데려다줄 수 있는 경우, 둘 중 이동 가능 시간의 범위가 더 좁은 경우를 우선적으로 선택해야 선택받지 못한 소를 다음 순번의 닭이 데려다줄 가능성이 더 높아지게 된다. 즉 닭의 시간을 오름차순 정렬, 소의 이동시간이 짧은 순서 & 움직이기 시작한 시간이 오름차순으로 정렬이 되어야 한다는 이야기다.

소의 움직임이 완료된 시간을 기준으로 오름차순, 움직임이 완료된 시간이 같다면 움직이기 시작한 시간 기준으로 오름차순으로 정렬한 뒤, 오름차순으로 정렬된 닭의 시간을 기준으로 데려갈 수 있는 소들을 탐색하여 접근하였다.

정답 코드

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

문자열 구현 문제다.

풀이

주어지는 시간이 넉넉한 편이므로 모든 문자열들을 비교하여 개수를 세면 된다. 두 문자열을 매개변수로 받은 뒤 시계방향으로 모든 경우를 읽어 같은지 같은지 다른지 판별하는 isSame(a:String, b:Stirng) -> Bool 함수를 구현하여 정답을 구하였다.

정답 코드