2024.03.11. ~ 2024.03.17.

백준 12 문제.

 

1. BOJ 25416 : 빠른 숫자 탐색 - S2

BFS 문제.

그냥 시작점에서 BFS를 돌려서 모든 칸의 최단거리를 보고,

나중에 모든 칸을 보면서 그 중 1이면 최단거리가 얼마인지를 보면 된다.

크기가 5 * 5 고정이라 최단거리 초기화를 대강 30 정도로만 해도 된다.

(최대 25칸이나 지나야 최단거리라서... 사실 25칸도 무리라고 생각한다.)

N = 5라고 하면 시간복잡도는 O(N^2)인데... N이 너무 작아서 사실상 O(1) 같은 느낌으로 풀린다.

 

2. BOJ 2417 : 정수 제곱근 - S4

Binary Search 문제.

그냥 mid * mid >= N 인지로 Binary Search 돌리면 되는 문제.

그런데, N의 범위가 매우 커서 l,r 범위를 잘 설정해야한다.

귀찮아서 파이썬으로 제출했다.

 

3. BOJ 14868 : 문명 - P4

DSU + BFS 문제.

그냥 BFS를 돌리면서 처음으로 하나의 집합의 크기가 K가 될 때를 찾는 문제인데...

이게 합쳐지는 조건이 두 면이 맞대어 있거나 아니면 칸이 서로 겹치는 경우라서 좀 까다로웠다.

결국에는 한 칸이 다른 한 칸을 합칠 때 무조건 전이나 동시에 찾은 칸만 합치도록 설계해서 풀었다.

계속 맞왜틀 당하다가 정 안 돼서 질문 게시판 봐서 반례를 찾았는데... 저기까지 생각이 미치지 못 했던게 좀 아쉬웠다.

시간제한이 매우 빡빡해서 Smaller-to-Larger까지 일단 넣어줬는데, 없이도 풀 수 있는 것 같긴하다.

 

4. BOJ 31565 : 전역 역전 - G5

Knapsack DP + Implementation 문제.

휴가를 받아서 더 일찍 전역하는 것과 군기교육대나 전문하사로 상대의 전역일을 늦추는 건 상대적인 개념으로 보면 동일한 행위이다.

따라서, 여유를 weight로, 늦추는 기간을 value로 치환하여 Knapsack DP를 돌린 다음에 원래 전역일 차이에서 빼주면 된다. (음수가 나오면 -1를 곱해주어야 한다.)

지난주에 한 시간 남기고 풀기 시작한 전남대 PIMM 알고리즘 파티 E번 문제다. 당시에도 Knapsack DP임은 쉽게 눈치를 챘는데, 시간차이 계산 방법을 찾느라 시간내에 풀지 못했던 기억이 난다.

그거와 별개로 지문 내용도 너무 무섭다. 이런 후임을 안 만나서 다행이라 생각한다.

 

5. BOJ 1789 : 수들의 합 - S5

Math + Greedy 문제.

1+2+...+i > N 이라면, 1 + 2 + ... + (2*i-1) 이렇게 쪼개는 게 최선이 된다.

이렇게 되는 이유를 나름의 증명을 해보자면, 수가 작으면 작을 수록 서로 다른 자연수의 개수가 줄어든다.

그래서 N -> N-1 -> N-1-2 이러한 순서대로 탐색하는게 서로 다른 자연수의 개수가 제일 많아지는 방법이라 생각하여 이렇게 풀었다.

 

6. BOJ 6813 : Signage - S2

Greedy + Implementation 문제.

단어 크기 합 + 단어 개수 - 1 <= w 가 되도록 한 문장을 만들어야 한다.

이후에는 w - 단어 크기 합 만큼의 빈칸들을 단어 개수 -1 군데에 배분을 잘 해주면 된다.

(이 부분은 수학으로 잘 배분해주면 된다.)

다만 내 구현에서는 단어가 딱 하나만 들어가는건 예외 처리가 필요하긴 하다.

솔직히 Greedy 보다는 구현 문제에 더 가까운데, 구현이 그리 재밌지도 않아서 풀기 귀찮았다.

 

7. BOJ 3197 : 백조의 호수 - P5

BFS + DSU 문제.

위의 BOJ 14868처럼 BFS를 날짜별로 돌리면서 두 점의 부모가 언제 같아지는 지 확인하면 된다.

BFS를 날짜끼리 구분해서 돌리는 건 큐 두 개를 관리하면서 구현하면 되고, 합치는 규칙은 현재 보고 있는 점과 같은 날에 녹았거나 좀 더 일찍 녹은 물과만 좌표를 합치면 된다.

혹시나 해서 Smaller to Larger도 같이 구현했는데, 빼고 다시 제출해보니 속도가 더 빨라서 신기했던 문제.

그와 별개로 BFS + DSU 문제 기본 난이도가 이렇게 높은 줄도 몰랐다. (난 진심으로 G3 정도라고만 생각했었다;;;)

 

8. BOJ 11280 : 2-SAT - 3 - P4

SCC 문제.

디코에 박아둔 백준 봇이 추천해서 따로 하고 있는 알고리즘 구현 플젝에 SCC도 추가할 겸 같이 공부해서 풀었다.

OR 문에서 하나가 거짓이면 나머지는 꼭 참이라는 점을 그래프로 표현해서 SCC를 보고 모순을 찾는 게 신기했다. (SCC가 아니라 일방적으로 연결된거면 상관 없다.) 

~ x1은 x_{N+1} 이런식으로 그래프의 크기를 2*N로 설정해서 풀었다.

 

9. BOJ 11281 : 2-Sat - 4 - P3

SCC 문제.

위의 BOJ 11280를 풀어보고 흥미가 생겨 같이 풀었다.

나는 SCC를 타잔 알고리즘으로 짠 다음에 위상정렬을 하지 않고도 AC를 받았다.

그냥 1번 노드부터 순서대로 DFS를 한 SCC들을 SCC를 구한 순서대로 보면서 가능한 SCC 내의 값을 True로 만들었더니 풀렸다.

대강 이유로는 ~p -> q 이긴 하지만 p -> q 라도 상관은 없어서 그런 것 같은데... AC를 받고도 좀 찝찝했다.

 

10. BOJ 11277 : 2-SAT-1 - S1

Bruteforcing 문제.

시리즈가 있어서 1,2를 연달아 풀어보았다.

BOJ 11280 코드를 그대로 들고오는 방법도 있지만, 충분히 O(2^N * M)로도 풀린다.

 

11. BOJ 11278 : 2-SAT-2 - S1

Bruteforcing 문제.

시리즈가 있어서 1,2를 연달아 풀어보았다.

BOJ 11281 코드를 그대로 들고오는 방법도 있지만, 충분히 O(2^N * M)로도 풀린다.

BOJ 11280 과 11281은 난이도 차이가 있을 여지가 존재하지만, 11277과 11278은 Bruteforcing으로 풀다보니 답도 바로 나와서 사실상 차이가 없는 문제였다.

 

12. BOJ 28238 : 정보 선생님의 야망 - S5

Bruteforcing 문제.

O(5C2 * N)으로도 충분히 풀리는 문제였다.

딱히 뭔가 특별한게 없던 문제.

 

이번 주 일지는 여기서 끝.