Hyun's_Devlog

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

문자열, 구현 문제이다. 딕셔너리 자료형을 사용했으나 시간 초과를 받았다. 아마도 알파벳순으로 정렬하는 과정에서 오래 걸린 듯싶다. 이후 크기 26인 배열을 생성하여 각 알파벳 순서대로 만들기 위한 개수와 사용 횟수를 담아 처리하였다.

풀이

퍼즐의 가운데 글자가 반드시 포함되어야 하는 것이 조건이다. 즉 해당 퍼즐을 통해 만들 수 있는 단어의 개수가 최저, 최고인 글자를 판별하는 문제다.

입력되는 단어들은 크기 26의 배열로 변환한다. 배열의 각 원소는 해당 알파벳의 개수를 담는 배열이다. 이후 해당 배열을 담는 2차원 배열 dictionary를 만든다.

퍼즐을 입력받을 때에는 마찬가지로 각 알파벳이 몇 개 있는지 나타내는 크기 26의 배열과 이후 dictionary를 탐색하면서 만들 수 있는 단어라 판단되면 해당 단어를 만들기 위해 사용된 알파벳의 횟수를 담는 배열 cnt: Array(repeating: -1, count:26)를 생성한다. 중요한 점은 해당 원소의 알파벳이 사용되었는지 사용되지 않았는지를 판별하기 위해 모든 크기 26짜리 배열은 -1로 초기화 한상태로 시작해야 한다. 코드로 보면 이해하기 쉬울 것이다.

마지막으로 cnt를 탐색하면서 최저 횟수와 최고 횟수를 찾아낸 뒤 해당 알파벳들을 출력해주면 된다.

정답 코드

 퍼즐의 입력 횟수가 문제에 적혀있지 않아, 처음 시간 초과를 받았을 때는 print() 호출 횟수가 많아져 스위프트의 느린 print() 속도를 대처하기 위해 Rhyno님이 작성한 FileIO 클래스를 사용했었다. 하지만 결론적으로는 해당 사항은 원인이 아니었고 아마도 딕셔너리 구조의 sort() 메서드의 속도가 느린 것이 더 큰 요인이지 않았나 싶다. 

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

완전 탐색 문제다. 두 배열 비교를 어떤 식으로 수행하는지 고민해야 하는 문제.

풀이

두 배열 중 짧은 배열을 덱을 사용하여 원소를 하나씩 담아낸 뒤 긴 배열과 비교, 짧은 배열의 원소를 모두 담아내었다면 긴 배열의 길이만큼 1을 추가하여 비교하였다. 값 갱신은 Bool 변수를 사용하여 두 원소가 모두 2일 경우에는 갱신을 하지 않는 방법으로 탐색하였다.

스위프트에는 기본적으로 제공되는 덱 구조가 없어서 배열을 사용하여 insert(_ newElement:Int , at:Int)를 사용했다. 시간 초과가 걱정되었지만 각 입력 배열의 길이가 최대 100으로 짧은 편에 속했고, 시간도 넉넉했기에 통과할 수 있었다. 이후 더 빠른 동작이 가능한지 궁금하여 배열을 합치는 방식으로 바꾸어 보았지만 큰 차이는 없었다.

정답 코드

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

dp문제다. 완전 탐색으로 시도했지만 역시나 시간 초과. 점화식을 생각해내는 데에 시간이 걸렸던 문제다.

풀이

최소한의 정사각형을 만들 수 있는 칸부터 시작해야 한다. 2차원 배열 map에 대해서 x와 y의 값이 모두 1 이상이고 map[x][y]의 값이 0보다 커야 한다. 해당 좌표의 상, 좌, 좌대각선 칸 중 최솟값 + 1로 갱신해나가면 된다.

map[x][y] = min(min(map[x-1][y], map[x][y-1]), map[x-1][y-1]) + 1

정답 코드

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

구현 문제에 해당한다. 홍준이의 이동방향을 어떻게 구현할지 고민했던 문제다.

풀이

시작지점이 지도의 어느 부분인지 알 수 없다. 따라서 시작 지점에서 최대 이동 범위인 50칸을 상하좌우로 확장한 상태에서 시작하여 지도를 그려낸 뒤 방문했던 x, y값의 최대, 최소 좌표 영역을 출력했다. 

미로 탐색 부분의 구현은 BFS를 사용할 때 자주 사용하던 dx, dy배열을 사용하여 "L"이나 "R"이 입력되면 배열의 인덱스를 변경하는 방법으로 구현했다.

정답 코드

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

그래프 탐색문색 문제로 BFS, DFS를 사용해서 풀어도 되지만 입력되는 바닥의 크기가 작고, 시간제한이 여유로운 편이어서 그래프를 x축 탐색, y축으로 탐색하여 개수를 세도 정답을 받을 수 있다.

풀이

Bool 타입의 flag변수를 사용하여 처음 마주하는 장식의 갯수를 세면 된다. 가로축 탐색은 처음 장식을 입력받을 때 수행하고, 이후 세로축으로 한번 더 탐색을 수행하면 된다.

정답 코드

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

1달 전에 오답인 상태로 방치했다가 다시 풀어본 문제다. 문제에 제시된 조건대로 구현만 하면 풀리는 문제다. 근데 집중해서 보지 않았는지 실수를 여러 번 남발해서 여러 번 시도했던 문제다. 처음엔 8가지 경우의 입력에 대해 switch 문으로 풀려했으나 코드가 너무 길어지기도 하고 코드가 길어지니 실수한 부분을 바로 찾기가 힘들었다. 설명문이 문제 자체를 이해하는 데에 실수를 유발하기 쉬운 문맥이기도 했다. 처음엔 돌과 킹이 동시에 움직이는 문제인 줄 알고 풀었고, 처음엔 둘 중 하나라도 움직일 수 없는 경우라면 둘 다 움직이지 않는 것으로 이해했었다. 결국 집중력이 부족해서 시간이 오래 걸렸던 문제다.

풀이

우선 해당 문제는 킹이 움직이는 문제다. 단, 킹이 돌이 있는 좌표로 움직이게 될 경우 돌은 킹이 움직이는 방향으로 똑같이 움직여야 한다. 추가적으로 돌이 만약 범위 밖의 좌표로 움직여야 한다면 해당 움직임은 취소. 당연히 킹도 제자리로 돌아가 다음 입력을 받아야 한다. 킹 혼자서 움직이는 경우 마찬가지로 범위 밖의 좌표로 이동해야 한다면 해당 이동은 취소다. 이번엔 문제에 대해 제대로 이해하고 각 움직임을 배열로 담아서 처리하였다. 

아스키코드로 세로좌표를 표현했다. 여기서 실수했던 점은 좌표에 대한 조건을 작성하는데 65(A)부터 72(H)까지 범위를 잡아야 했지만, 아무 생각 없이 65(A)부터 90(Z)까지 범위로 잡는 실수를 했다. 

정답 코드

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

탐색 종료 조건 부분에서 고생했던 문제였다. 처음에는 지도를 입력받을 때 빈칸의 개수를 세어놓고 빈칸이 0이 될 때까지 플레이어 순서대로 경로탐색을 수행하는 방법으로 시도했으나, 벽으로 둘러싸인 빈 공간의 가능성을 뒤늦게 깨달았다. 

풀이

각 플레이어에게 해당하는 경로탐색용 큐 Array(repeating: [[Int]](), count: p+1)를 생성하여 앞으로 방문해야할 공간의 좌표를 담아둔다. 이후 모든 플레이어의 큐가 비어있는 상태가 될 때까지 각 플레이어 턴마다 Si번 경로탐색을 수행하면 된다. 큐의 첫 수행 좌표는 지도를 입력받을 때 큐에 담아두면 된다. 

정답 코드

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

답이 생각나지 않아 점화식을 찾아보고 코드를 적어봤는데, 풀이를 이해하고서도 예외처리를 제대로 하지 못해서 오답 판정을 받았다. 결국 코드까지 찾아보고 난 후에야 풀 수 있었던 문제. 역시나 DP문제는 다양한 시점으로 생각하는 연습이 필요한 것 같다.

풀이

암호화된 문자의 길이가 n일 경우, dp:[Int] 배열은 총 n개의 배열로 dp[i]는 0번째 숫자부터 i번째 숫자까지로 만들수 있는 암호의 갯수가 담긴 배열이다. 입력된 암호문구를 순회하면서 현재 숫자가 0보다 크다면 dp[i-1]번째 경우의 수를 이어가면 되고, 추가로 직전 숫자가 0보다 크다면 현재 숫자와 합쳐 두 자리수의 대체 가능한 알파벳을 만들수 있다면 dp[i-2]번째 경우의 수를 추가로 이어가면된다. 즉 점화식은 아래와 같다.

현재 암호가 0보다 크다면,
dp[i] += dp[i-1]
추가로 직전 암호가 0보다 커서 현재 암호와 이어 붙였을 시 10 이상 26 이하라면,
dp[i] += dp[i-2]

점화식을 알았을 때는 간단하게 풀면 되겠다 싶었는데, 문제는 중간에 나오는 0에 대한 처리 부분이었다. 처음에는 중간에 flag 변수를 만들어 분기 처리를 하였는데, 생각보다 처리해야 할 경우가 많아서 오답처리를 받았다. 다른 유형의 문제들은 많은 문제를 풀면서 패턴에 적응해가는 과정을 통해 성장해가는 게 느껴지는 반면, DP문제는 다양한 시각에서 문제를 바라봐야 한다는 점이 여러모로 어렵게 느껴진다. 풀이는 해당 블로그에서 찾았다. 이해하기 쉽게 풀이에 대한 이미지도 있다.

정답 코드