Hyun's_Devlog

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

세그먼트 트리 문제다.

풀이

구간 합 구하기 문제와 다른 점은 세그먼트 트리의 갱신 부분에 주의할 부분이 있다는 점이다. 처음에는 단순히 기존값으로 나누고, 새로운 값으로 다시 곱해주면서 리프노드까지 도달하는 방법으로 접근했지만, 예제에서 알 수 있듯이 트리의 값이 0으로 바뀌게 되면 다음 갱신에 문제가 발생한다. 따라서 리프노드부터 먼저 갱신이 이루어지고, 루트노드까지 새로운 값으로 계산을 해주어야 한다. 

정답 코드

재귀호출 시에 범위를 반대로 적어 "틀렸습니다"를 연발했다.. 아는 유형의 문제라 방심했던 탓이다. 항상 집중해서 문제를 풀 것.

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

세그먼트 트리 문제다.

풀이

각 노드에 (Int, Int) 자료형을 통해 최솟값과 최댓값을 담는 세그먼트 트리를 생성하여, 각 구간별 최솟값과 최댓값이 담기는 세그먼트 트리를 생성하여 조건에 맞게 출력하면 된다.

[1,2,3,4,5] 배열을 기준으로 만든 세그먼트 트리다. 리프노드에는 동일한 값을 넣었다. 

트리를 읽어야 할 때는 구간에 해당하는 노드를 탐색, 각각의 최댓값과 최솟값을 비교하여 반환하면 된다.

해당 그림은 1 ~ 4번 인덱스 구간의 최솟값, 최댓값을 읽어올 때 참고하게 될 노드다.

범위 밖의 노드라면 입력 범위의 최댓값과 최솟값을 바꾸어 출력하게 하였다. ((1,000,000,000, 1) 리턴)

정답 코드

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

세그먼트 트리 기본문제다. 

풀이

세그먼트 트리란 구간합을 이진트리의 형태로 구현한 자료구조이다. 부모노드에는 두 자식노드의 총합이 담기며, 두 자식노드는 중간을 기준으로 좌측 범위의 총합, 우측 범위의 총합의 형태로 나뉜다. 그림으로 보는 것이 이해하기 더 쉬울 것이다.

크기 5인 배열의 세그먼트 트리의 구조다. 각 배열의 값이 리프노드에 담기며, 부모 노드로 구간 합을 계산하여 루트에는 배열의 총합이 담기게 된다.

예제 [1,2,3,4,5] 배열의 세그먼트 트리를 그려보면 다음과 같이 만들어진다. 세그먼트 트리의 경우 구간합의 변경에 굉장히 용이하다. 그 이유는 바로 트리구조에서 오는 접근성 때문인데, 부모 노드를 기준으로 두 배를 하면 좌측 자식 노드, 거기에 1을 더하면 우측 자식 노드에 접근이 가능하기 때문이다. 따라서 루트 노드는 0이 아닌 1부터 시작하며 기본적으로 해당 구조의 재귀호출을 통해 구간합의 변경과 조회가 이루어진다.

1번 ~ 4번 인덱스까지의 구간합을 구하게 된다면 좌측 그림과 같이 해당 구간에 접근하여 계산이 이루어진다. 사실 누적합을 이용해서 푼다면 O(1)만에 계산이 가능하지만, 자료의 변경이 일어난다면 처음부터 누적합을 다시 구해야 하기에, 결국 자료의 크기가 N일 때 O(N)시간이 걸리게 된다. 세그먼트 트리의 경우 우측 그림과 같이 조회뿐만 아니라 루트에서 해당 구간 만의 접근을 통해 변경이 가능하기에 O(logN)시간만에 해결이 가능하게 된다. 해당 문제의 경우 구간의 변경이 빈번하게 이루어지기에 세그먼트 트리의 구현을 요구하는 문제인 것이다.

정답 코드

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 탐색을 수행하면 된다.

정답 코드