23.05.02 - 23.05.03 공부 (2/2)

 

 
그리고 그 외 잡다한 것들.
 

shake! 2018 B번. 변신 이동 게임

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

15906번: 변신 이동 게임

알고리즘 분류로는 '데이크스트라'로 되어 있지만, 단순 bfs로도 충분히 풀 수 있다. [벽 부수고 이동하기] 시리즈(ex. https://www.acmicpc.net/problem/2206)에서 쓰이는 테크닉을 사용하여 보자.
 
일반 모드로 이동하는 방법은 기존 bfs 돌리듯이 하면 된다. 문제는 변신 모드인데..
현재 모드가 일반 모드라고 하자. 현재 위치에서 변신 모드로 이동하고자 하면 인접 워프 지점까지 $t+1$턴을 소모한 셈이 된다. 따라서 (현재 위치의 턴 수 $+\,t + 1$)이 인접 워프 지점의 턴 수보다 작은지 큰지를 판단하면 된다. 이때, 변신 모드임을 나타내는 인자 하나도 같이 큐(queue)에 넣어 bfs를 진행한다. 모드가 두 가지이므로 이 별도의 인자 또한 두 가지이다.([벽 부수고 이동하기]에서 벽을 부순 상태인지 아닌지를 체크하는 용도와 유사하다.)  따라서 bfs 맵을 status[501][501][2]와 같이 설정하면 된다. 이때 큐(queue)에 넣는 자료형을 tuple로 관리하면 편리하게 bfs를 진행할 수 있다.
 
변신 모드 구현에서 또다른 중요한 점은 '가장 가까운 인접 워프 지점을 어떻게 찾아낼 수 있느냐'일 것이다. 여러 방법이 있을 수 있겠지만 가장 간단한 완전탐색이 시간 내에 돌아간다. 상하좌우 중 어느 한 방향을 잡고 그 방향대로 쭉 탐색하면서 워프 지점이 있는지를 판별한다. 판별했을 경우 바로 종료해야 함을 잊지 말자. 이를 다른 방향으로 3번 더 반복한다.
 
 
 
 

shake! 2018 H번. 우주선 만들기

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

15912번: 우주선 만들기

 어떤 부품부터 시작하여 W_max * E_max 값을 구한다고 하자. 그렇다면 그 이전 부품들에 대한 값들에 대하여서는 전혀 영향을 받지 않게 된다. 따라서 이 문제는 각각의 부분문제에 대한 DP로 해결할 수가 있다.

DP식을 다음과 같이 정의하자.

• $dp[i] =$ $i$번째 부품부터 시작된 W_max * E_max의 최솟값

정의에 따라 DP 식은 다음과 같이 전개될 수 있다.

• $dp[i]$ = 가능한 $k$값 중 (W_max * E_max + $dp[k+1]$)의 최솟값
• W_max, E_max = ($i$번째 부품부터 $k$번째 부품까지의 최대 W, E)

가능한 $i$가 $N$개이고, 각 부분문제에 대하여 $N$번 부품까지를  탐색해 볼 수 있으므로, 시간복잡도는 $O(N^2)$이다.
 
 

UCPC 2022 예선 J번. 수 정렬하기, 근데 이제 제곱수를 곁들인

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

25323번: 수 정렬하기, 근데 이제 제곱수를 곁들인

 작년 처음 나갔던 UCPC에서 마주친 문제를 10개월 만에 다시 풀어보았다. 대회 당시, 풀이는 대강 생각이 났는데 너무나도 큰 수의 범위 때문에 구현을 어찌할 줄 몰라 우왕좌왕하다가 그대로 대회가 끝났었다. 끝나고 나서  에디토리얼을 보고 구현 방법에 감탄했었던 기억이 난다. (아래 풀이도 거의 에디토리얼을 따라가니 참고)

원래 수열과 정렬된 수열을 준비한다. 그 두 수열을 비교하여, 동일하지 않은 수가 있다면 원래 수열의 수와 정렬된 수열의 수를 바꾸어야 하는 것은 자명하다. 따라서 그 두 수의 곱은 제곱수여야 한다.

이때 이것이 가능한 이유는 다음의 중요한 성질이 작용하기 때문이다. 어떤 세 수 a, b, c가 있고, a*b, b*c가 제곱수일 때, a*c 또한 제곱수이다. $a*c = \frac{(a*b)(b*c)}{b^2}$ 인데, $a*b$, $b*c$, $b^2$이 모두 제곱수이기 때문이다.

그러나 두 수의 곱이 제곱수인지 판별하는 것에 대한 구현이 다소 어렵다. 두 수의 곱 대신 수 하나하나를 따로 생각해 보자. 두 수의 곱이 제곱수라면, 두 수의 소인수분해에서 '홀수 지수 소인수'는 두 수의 최대공약수에 반드시 포함된다. 따라서 두 수의 최대공약수로 두 수 각각을 나누고, 그 각각의 수가 제곱수인지를 판별한다. 이때 제곱수인지를 판별할 때에는 이분탐색을 이용한다. 수의 범위가 $10^{18}$까지이므로, left = 0, right = $10^9$로 설정한 다음 mid = (left + right) / 2의 제곱이 해당 수가 되는지를 확인한다.
 
 
 
 
 

ICPC 2021 서울 인터넷 예선 E번. Histogram

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

23242번: Histogram

 앞서 설명한 [우주선 만들기] 문제와 유사하게 풀이할 수 있다. DP식 전개 방식 또한 유사하나, 문제는 구간 개수를 임의대로 할 수 없고 bucket이 정해져 있다는 점이다. 이 bucket 또한 고려하여 DP식을 다음과 같이 전개해 보자.

• $dp[i][j]$ = 가능한 $p$값과 $j$값 중$\sum_{k=i}^{p}(\mathrm{value}_k - \mathrm{avg})^2 + dp[p+1][j-1]$의 최솟값
• 이때 avg는 average frequency를, $j$는 남아있는 bucket 개수를 의미한다.

bucket 요소 추가에 따라 시간복잡도는 $O(N^2B)$.