Hyun's_Devlog

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

동적 계획법 문제다.

풀이

동적 계획법을 기본으로 그래프탐색을 통해 접근해야 한다. 부모 노드가 얼리어답터라면 자식노드는 얼리어답터 여부와 상관없이 해당 부분의 부모와 자식에게는 아이디어 전파가 가능하다. 반대로 부모가 얼리어답터가 아니라면 자식은 반드시 얼리어답터 이어야 한다. 

두 개의 자식을 가진 부모노드가 얼리어답터가 경우 아이디어가 전파되려면 그림과 같은 4개의 경우의 수가 만들어진다. 해당 부분에서의 정답은 가장 첫 번째의 경우가 최소조건임을 알 수 있다. 

하지만 반대로 부모가 얼리어답터가 아닐 경우, 자식들은 모두 얼리어답터 이어야만 조건이 맞다. 즉 우리는 부모노드가 얼리어답터인지, 일반인인지의 경우를 따져 얼리어답터의 수를 계산할 수 있게 된다.

그래프는 다음과 같이 두 개의 값을 가지는 형태로 구현한다. 0번 인덱스에는 자신이 일반인일 경우 얼리어답터의 수, 1번 인덱스에는 자신이 얼리어답터일 경우 얼리어답터의 수. 처음에는 당연히 자기 자신만 얼리어답터인 경우로 1로 초기화되어 있다.

먼저 부모가 얼리어답터가 아닐 경우부터 살펴본다. 해당경우는 자식노드가 무조건 얼리어답터이어야 하기 때문에 자식의 수만큼 더해진 값이 얼리어답터의 최소 개수다.

하지만 부모가 얼리어답터인 경우, 자식이 얼리어답터의 여부와 상관없이 최솟값을 가져오면 조건이 성립된다.

parent[0] += child_0[1] + child_1[1]...child_N[1]
parent[1] += min(child_0[0],child_0[1]) + ... min(child_N[0],child_N[1]))

즉 모든 노드가 [0,1] 형태로 초기화되어있을 경우, 해당 점화식을 사용하여 리프 노드의 정보를 통해 루트 노드까지 최소 얼리어답터의 수를 구할 수 있게 된다.

예제의 경우 다음과 같은 형태로 결과가 나오며, 출력은 루트노드의 두 개의 값 중 최솟값을 출력하면 된다. 코드로 보는 것이 이해하기 더 쉽다.

정답 코드

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

동적계획법으로 접근 가능한 문제다.

풀이

크기 A인 두 개의 dp 배열을 만든다. 하나는 0부터 해당 인덱스까지 증가하는 부분수열의 최대 개수, 다른 하나는 A-1번부터 해당 인덱스까지 감소하는 부분수열의 최대개수를 담아내어 ans배열에 두 배열의 값을 합쳐서 최댓값을 계산하면 된다.

i는 0부터 A까지, 즉 구하고자 하는 대상의 인덱스, k는 0부터 i까지 즉 처음부터 자기 앞번호까지의 원소를 순회할 때 점화식은 다음과 같다.

if arr[k] < arr[i] 
dp[i] = max(dp[i], dp[k]+1)

즉 자신보다 작은 원소로 끝나는 증가하는 부분 수열에 원소 i를 붙이기만 하면 해당 원소로 끝나는 증가 부분 수열이 완성되기에 해당 조건 내에서 최댓값으로 갱신하면 답을 구할 수 있는 것이다. 예제를 기준으로 구한 dp 배열은 다음과 같다.

감소하는 부분수열의 경우는 해당 배열을 역순으로 탐색하면 구할 수 있다. 주의할 점은 증가하는 부분수열의 개수에서 자기 자신을 포함하여 계산했기에 1로 초기화했으나 감소하는 부분수열은 자기 자신을 포함하지 않은 0으로 초기화해야 중복을 피할 수 있다. 

마지막에는 해당 배열의 총합을 더하여 최댓값을 출력해 주면 된다.

정답 코드

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

수학 + 분할정복 문제다.

풀이

행렬의 제곱연산을 수행하는 함수를 생성. B번의 곱셈을 수행하면 간단하겠지만, B의 최댓값이 크기 때문에 거듭제곱의 원리를 응용하여 연산 횟수를 줄여야 한다.

마지막에 출력해 줄 result 배열을 단위행렬로 초기화한 뒤, B가 0이 될 때까지 반복문을 순환한다. 매 반복문마다 A행렬은 거듭제곱연산이 이루어지고, B가 홀수일 경우에는 result배열에 A행렬을 곱해주는 연산을 수행하면 올바른 결과를 출력할 수 있다.

A의 7 제곱 행렬을 구한다고 가정했을 경우 아래와 같은 형태로 연산이 수행된다.

정답 코드

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

그래프 탐색 문제다.

풀이

모눈종이의 가장자리에는 치즈가 없다. 즉 (0,0) 좌표부터 너비우선탐색을 수행하여 치즈를 마주치면 해당 좌표를 저장. 탐색도중 같은 좌표를 한번 더 마주하게 된다면 해당 치즈는 2변이 실내온도에 닿은 것으로 판정하여 녹은 것으로 판정한다. 좌표를 저장하고 탐색하는 데에 O(1)만에 탐색이 가능한 Set 자료구조를 사용하였다. 치즈의 개수가 0이 될 때까지 탐색을 수행. 반복이 일어난 횟수를 출력하면 된다.

정답 코드

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

다익스트라 알고리즘 문제다. 스위프트의 경우 heap구현이 필요하다. Rhyno님이 구현한 heap을 사용하였다.

풀이

입력되는 간선의 최대개수가 100,000개, 노드의 개수가 1,000개 이기에 우선순위 큐가 필수이며 메모리 초과를 유도하는 테스트 케이스가 주어지기에 다익스트라 알고리즘에 대한 정확한 이해가 필요하다. 이번 문제를 통해 조금 더 다익스트라 알고리즘에 친해졌다.

다익스트라 알고리즘을 통해 최단거리를 구하는데, 최단거리를 나타내는 ans배열에는 (최단거리, 진입노드) 튜플 배열로 생성하여 정보를 담아낸다. 

마지막에는 ans배열을 통해 [ 도착지점 -> 출발지점 ] 역순으로 dfs탐색을 통해 경로와 거리를 출력해 준다.

예제를 기준으로 설명하면 다음과 같다.

다익스트라 알고리즘의 특성상, 매 탐색마다 가중치가 가장 작은 노드부터 탐색하기에 목적 노드를 방문 완료되면, 해당 노드의 경로는 이미 최단 경로인 것을 확신할 수 있다. 문제에서는 항상 시작 지점과 도착 지점의 경로가 있음을 보장했고, 테스트 케이스에서는 시간 초과와 메모리 초과를 유도하는 입력 값이 주어지기에 도착 노드의 방문이 확인되면 곧바로 탐색을 중단하고 갱신된 ans 배열을 통해 dfs 탐색을 수행하면 된다.

정답 코드

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 메소드를 사용하여 풀어내면 된다. 단 출력할 때의 문장 포맷을 잘 확인하고 출력하자. 제대로 확인 안 해서 틀린 부분을 찾아내느라 시간을 낭비했다. 문제를 꼼꼼히 읽었는지를 요하는 문제다.

정답 코드