Hyun's_Devlog

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

기하학이 한 방울 들어간 유니온 파인드 문제. 이전에 풀다가 포기했던 문제다. 거리 계산 부분에서 아무 생각 없이 2차원 배열로서의 거리로 접근했는데, 옳은 방법이 아니었다. 2차원 배열 없이 풀 수 있는 문제.

풀이

입력되는 좌표와 범위를 입력받을 때마다, 모아놓은 나머지 지점들과의 거리를 계산, 범위가 겹치는 경우 유니온을 수행하여 마지막에 그룹의 개수를 출력하면 된다.
이번에는 그룹의 노드 개수를 파악하는 문제는 아니므로, 합병 수행 시 루트의 값은 바꾸지 않고 자식으로 들어갈 노드의 번호만 루트의 번호로 바꾸어 주면 된다.
두 지점의 범위 판정은 간단하다. 두 원점 사이의 거리가 두 지점의 범위의 총합보다 같거나 짧은 경우, 범위가 겹치는 것으로 판단하면 된다.

정답 코드

iOS 개발자라면 가장 근본적으로 알아야 할 App life Cycle에 관련된 질문이다. 질문에 대해 단답식으로 대답하자면 아래와 같이 대답할 수 있다.

"UIApplication 객체가 생성됩니다."

사용자가 앱 아이콘을 눌러 앱을 실행하게 되면 대략 사진과 같은 형태의 생명주기를 통해 메모리에 할당되었다가 소멸된다. 여기서 이번 글에 눈여겨볼 부분은 바로 UIApplicationMain() 호출 부분이다. swift이전에 obj-c로 작성되었던 앱은 c언어 기반이었기에 앱이 실행되면 운영체제가 가장 먼저 main.m 파일 안에 main() 함수를 호출하여 앱이 시작되었다고 한다.

swift가 c언어 기반은 아니지만 obj-c와 함께 사용되기 위한 언어여서인지, 동일하게 main() 함수를 호출을 해야하는데, 우선 xcode로 생성한 iOS 개발 템플릿에는 main.swift 파일은 보이지 않는다. 이유는 UIKit 프레임워크 안에 main() 함수를 숨겨놓았다고 한다. 따라서 앱이 실행되면 가장 먼저 운영체제가 개발자는 찾아볼 수 없는 main() 함수를 호출하고, main() 함수는 뒤이어 UIApplicationMain() 함수를 호출하여 UIApplication 객체가 생성이 되는 것이다. 그렇다면 UIApplication은 무엇일까?

UIApplication

The centralized point of control and coordination for apps running in iOS.

문서에 따르면 iOS에서 실행중인 앱의 제어와 조정을 담당하는 중앙지점이라고 적혀있다. 즉 여기서부터 실직적인 앱이라고 부를 수 있고, 해당 객체가 생성되고 나서야 개발자가 작성한 코드대로 이벤트 처리 등 앱의 동작을 제어할 수 있는 것이다.

모든 iOS앱은 단 하나의 UIApplication 인스턴스를 가지며, 개발자가 원한다면 UIApplication의 shared 프로퍼티를 통해 객체에 접근할 수 있다고 한다. 사실 무슨 말인지는 정확하게 와닿지 않아서 이 부분에 대해서는 나중에 시간을 들여 더 깊이 알아봐야겠다.

참고 문서 및 블로그

https://atelier-chez-moi.tistory.com/29

https://zeddios.tistory.com/538

https://blog.naver.com/soojin_2604/222423840595

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

유니온 파인드 문제다. 바로 이전 풀이 [11816] 로봇 조립 문제와 같은 방법으로 접근하면 풀 수 있다.

풀이

지난번 문제와의 차이점은 은하에 속한 행성의 개수가 처음부터 주어진다는 점이다. 배열 galaxy의 초기값을 0으로 설정하고 행성의 개수가 입력될 때 해당 값만큼 빼주고 시작하면 된다.

은하가 연결될 때마다 연결된 은하의 행성 수를 출력해야 하므로 유니온 함수에 결합 동작 이후 배열의 루트에 해당하는 값을 절댓값으로 출력하면 된다.

정답 코드

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

기본적인 유니온 파인드 문제다. 대신 문제에서 요구하는 것은 부품이 속한 컴포넌트의 크기이다. 

풀이

부품의 번호가 1부터 1,000,000이기에 입력 인덱스를 바로 핸들링 하기 위해 1,000,001 개의 배열을 생성. 초기값을 -1로 둔다. 여기서 -1은 루트라는 것을 표시함과 동시에 컴포넌트의 개수를 음수로 표현하는 역할도 하게 된다.

파인드에 해당하는 root() 함수를 통해 배열의 값을 탐색, 값이 0보다 작으면 루트인 것으로 판정, 0보다 큰 값이면 해당 부품의 부모인 것으로 판정하고 부모의 루트를 재귀 호출하여 컴포넌트의 루트를 탐색한다.

유니온에 해당하는 union() 함수는 둘의 루트를 확인 후, 서로 다른 컴포넌트라면 합치는 과정을 수행하는데, 루트가 될 노드에 추가될 노드의 값을 더해주는 것으로 컴포넌트의 크기를 갱신하게 되고, 다른 컴포넌트로 편입하게 될 루트에는 해당 루트의 번호를 대입해주는 것으로 편입을 마치면 된다. 

마지막으로 출력해야 할 경우에는 해당 부품의 루트를 찾고, 루트를 인덱스로 배열의 음수 값을 절댓값으로 출력해주면 된다.

정답 코드

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

문제에 주어진대로 구현하면 되는 구현 문제다. 시간 흐름에 따른 뱀의 방향 전환을 어떻게 구현할지 고민했다.

풀이

2차원 배열에 뱀은 "S", 사과는 "A"로 표시하여 구분을 지었다. 뱀이 지도에서 어느 좌표 위에 있는지를 또 다른 배열에 담아 두고, 뱀의 머리가 "S"또는 지도의 범위를 빠져나간다면 게임을 종료시키는 것으로 구현하였다. 

방향 이동의 경우 4가지 방향을 정해놓은 x배열 y배열을 생성한 뒤, 최대 시간이 10,000이기에 시간을 표현하는 10,000 크기 배열을 생성하여 입력받은 시간 인덱스에 각 회전을 하기 위한 방향 정보를 담아두어 매 반복문(시간)마다 방향을 정해주었다.

뱀의 이동은 문제에 주어진대로 앞이 빈 공간이라면 뱀의 새로운 머리 좌표를 배열의 맨 앞에 추가한 뒤, 배열의 마지막인 꼬리 좌표를 removelast()를 통해 이동을 처리하였다. 사과를 만났다면 꼬리 좌표는 그대로 두면 된다.

정답 코드

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

백트래킹 문제다.

풀이

실제로 스도쿠를 풀듯이 각 칸에 대한 숫자 대입 여부를 확인하면 된다. 그걸 어떻게 구현하느냐가 문제의 핵심. 결국 생각이 나지 않아 다른 분의 풀이에서 힌트를 얻고 문제를 풀었다.

스도쿠 판의 각 열, 행, 사각형에 1부터 9를 대입할 수 있는 2차원 배열을 생성한다. 입력받은 스도쿠 탐색 시 0을 마주하였을 경우 앞에서 생성한 3개의 배열에 대입하려는 숫자에 해당하는 인덱스가 모두 false인 경우, 숫자를 현재 좌표에 대입 후 재귀 호출, 해당 숫자가 답이 아닐 수 있으므로 0으로 복구시킨 후 다음 탐색을 수행한다.

마지막 좌표에 도달하면 스도쿠를 출력하면 된다.

정답 코드

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

그래프 탐색 문제다. 너비 우선 탐색을 통해 4회 이상의 탐색이 이루어졌다면 연쇄 횟수를 증가시키고 연쇄가 일어난 곳은 다음 원소로 메꾸는 방식으로 접근했다.

풀이

문제에서는 연쇄가 일어난 이후 상단에서 하단방향으로 원소를 매꾸어 주어야 하기에, 다루기 편하게 12 x 6 배열이 아닌 6 x 12 크기의 배열로 구현하여 탐색을 진행했다. 

문제에서 요구하는 것은 연쇄가 몇번 일어났는지가 아닌, 연쇄 사이클이 몇 번 이루어졌는지 이기 때문에, while문과 flag를 통해 사이클 횟수를 세고, 연쇄가 일어나지 않는다면 반복문을 빠져나가는 것으로 코드를 작성했다. 

탐색 수행시, 본 배열을 임시 배열에 담은 후 임시 배열을 탐색하였다. 탐색한 곳은 "#" 문자열로 변경, 4번 이상의 변경이 이루어지면 해당 배열을 본래 배열에 반영해주는 방법으로 너비 우선 탐색을 진행했다.

한 사이클의 탐색이 끝나면 또다시 임시 배열을 생성하여 빈 공간과 문자열을 분리하여 담아낸 뒤 [문자열] + [빈 공간] 배열을 붙여 본 배열에 반영해주었다.

정답 코드

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

그래프 탐색으로 접근한 문제다. 

풀이

파이프의 앞쪽을 head, 뒤쪽을 tail로 설정하여 tail과 head의 x, y좌표를 비교하여 수평 이동해야 할지, 수직 이동해야 할지, 대각선 이동을 해야 할지 비교한 후 탐색을 통해 해결하였다. 

파이프가 수평으로 놓인 경우

head의 x좌표와 tail의 y좌표가 맞는지 확인하면 된다. 동일하다면 파이프가 수평으로 놓인상태, 이경우에는 수평이동, 대각선 이동이 가능하다.

파이프가 수직으로 놓인 경우

head의 x좌표와 tail의 x좌표가 다르고 y좌표가 서로 다르다면 수직으로 놓인 경우다. 이경우에는 수직이동, 대각선이동이 가능하다.

파이프가 대각선으로 놓인 경우

당연하게도 head와 tail의 x좌표 y좌표가 모두 다른경우다. 이경우에는 3가지 이동을 모두 수행하면 된다.

이동을 수행할 때에는 이동할 좌표가 유효한 범위인지, 그리고 벽이 아닌 빈 공간인지를 확인하고 탐색 큐에 담아주었다.

정답 코드