2024.03.04. ~ 2024.03.10.

백준 24 문제.

 

1. BOJ 31503 : DP (Large) - P5

O(NlogN) LIS 문제.

문제를 해석해보면 결국 특정 위치의 원소가 꼭 들어갈 때의 LIS의 길이 구하기 문제가 된다.

i 번째 원소를 포함한 LIS의 길이는 (i 번째 원소가 마지막 원소인 LIS의 길이) + (i 번째 원소가 제일 처음에 들어있는 LIS의 길이) - 1 이 되는데,

여기서 배열의 원소들에 -1를 곱하고 역으로 뒤집으면  "N번째 원소부터 볼 때 i 번째 원소가 제일 마지막 원소인 LIS의 길이" = "i 번째 원소가 제일 처음에 들어있는 LIS의 길이"가 된다.

따라서, O(NlogN) LIS로 먼저 " i 번째 원소가 마지막 원소인 LIS의 길이"를 모든 i 번째 원소에 대해서 미리 계산하고,

배열에 모두 -1를 곱하고 뒤집어 또 O(NlogN) LIS로  "N번째 원소부터 볼 때 i 번째 원소가 제일 마지막 원소인 LIS의 길이"를 구한다.

이후에 각 쿼리 별로 미리 계산해 둔 결과값을 가져다가 쓰면 되므로 총 시간복잡도는 O(NlogN + Q)가 된다.

왜인지 모르게 BOJ 11045가 생각나는 문제였다.

(사실 Softeer에서 O(NlogN) LIS 버젼의 가장 긴 바이토닉 수열 찾기 문제가 있었는데, 그게 더 비슷한것 같다.)

 

2. BOJ 31501 : DP (Small) - G3

DP (O(N^2) LIS) 문제.

위의 문제의 Small 버젼이라 Large 버젼의 AC 코드를 그대로 내서 풀었지만, O(NlogN) LIS 부분을 O(N^2)으로 구해도 되는 문제였다.

위의 문제는 BOJ 11045가 생각만 나는 문제였다면, 이 문제 같은 경우에는 아에 BOJ 11045의 아이디어를 좀만 꼬아서 낸 문제 같아 G3를 주긴 했다.

 

3. BOJ 31476 : :blob_twintail_thinking: - G5

DFS + BFS 문제.

양갈래 블롭은 {현재 탐색하고 있는 노드, 갈라진 횟수}를 BFS로 넘기면서 쉽게 구현이 가능하다.

BFS를 하면서 탐색 가능한 노드의 개수를 세고 이를 포니테일 블롭들의 탐색 방법인 DFS를 하면서 현재 몇 개의 노드를 탐색했는지 확인할 때 활용한다.

그래서 전부 탐색했으면 그 때 기준으로만 포니테일의 탐색 시간을 기록하고, 나중에 DFS가 끝나면 서로 비교하는 방법으로 구현하였다.

지문에서 입구의 노드 번호가 1인 것 등 정확히 명시해주었으면 하는 부분들이 있었던 아쉬운 문제.

 

4. BOJ 31477 : 양갈래 구하기 - G5

DFS + Tree DP 문제.

간선의 개수가 N-1개이므로 트리임은 명확하다.

dp[i]를 'i번째 노드 밑의 리프 노드들과 연결이 끊어질려면 필요한 최소 비용'이라고 정의하고,

i번째 노드 밑의 자식의 노드 번호를 j, i번째 노드와 j번째 사이 간선의 비용을 E[i][j] 라고 한다면 dp[i] = sum(E[i][j], dp[j])가 된다. 

이를 DFS를 돌리면서 DP 테이블을 채우고 dp[1]을 출력하면 된다.

난이도는 G3으로 기여했는데, 이유는 아래 문제와 난이도가 사실상 동일하다고 판단했기 때문이다.

 

5. BOJ 12784 : 인하니카 공화국 - G3

DFS + Tree DP 문제.

위 문제랑 사실상 동일한 문제다.

다만, 트리임을 명시하는게 'N-1개의 간선이 있다.' -> '최소한의 간선으로 모든 노드간의 이동이 가능하도록 그래프를 설계하였다.' 이게 좀 다른데...

별 차이가 없는 것 같아서 위 문제도 G3, 이 문제도 G3으로 기여하였다.

 

6. BOJ 30599 : Divisibility Trick - G5

Ad hoc + Constructive + Math 문제.

d를 d번 이어서 적는다면 각 자리 수는 d번씩 나오기 때문에 d의 배수가 된다.

d가 최대 1000인데, 1000을 1000번 적으면 딱 10^6자리 수가 나와서 괜찮다.

 

7. BOJ 31478 : 포니 양은 놀고 싶어! - G1

Number Theory + FLT + Modular Inverse + Exponential with DnC 문제.

FLT의 a ^ {p-1} mod p = 1 이라는 성질을 활용하면...

A^{B^C} mod 7 = A^{ a * (7-1) + b } = A^b 이러한 식으로도 정리가 되므로 B^C mod 6 = b 이니 이를 분할정복을 활용해서 O(logC)만에 계산하면 된다. 이후 A^b는 사실 b가 작아서 O(b)도 괜찮지만 그냥 O(logb)로도 계산해도 된다.

B^C / A 는 그냥 그대로 B^C mod 7을 또 분할정복을 활용해서 계산하고, A ^ 5 mod 7로 모듈로 역원 계산을 해주어 곱해주면 된다.

 

8. BOJ 31502 : 만화에서 나오는 거 따라하고 그러면 안 된다 - G2

Dijkstra + BFS 문제.

BFS를 C 기준으로 돌려서 B에서 다시 역추적해서 경로를 파악한다.

이후에, A 기준으로 Dijkstra를 돌려서 경로에 있는 모든 노드들에 대해서 최단거리를 파악해보면 된다.

B -> C 로 BFS 한 다음 C에서 역추적한다고 계속 틀렸었는데, C부터 역추적 한다면 B에서 C로 갈 때 항상 간선들이 제일 많은 노드로 가는 건 아니니깐... 그걸 나중에 알고 허탈했었다.

이 문제를 사람들이 많이 안 풀었는데, 당시 풀었을 때는 G1로 기여해서 G1가 되었으나 나중에 생각이 바뀌어 다시 G2로 기여하니 G2가 되었다.

 

9. BOJ 6118 : 숨바꼭질 - S1

BFS 문제.

각 노드별로 최단거리 파악 + 그 중에서 최장거리인 노드 개수, 최장거리, 제일 작은 노드 번호 찾기.

그리 어렵지 않은데... 이게 왜 S1?

일단, BFS 기본 문제가 S2~S3 같아서 S2로 기여했다.

 

10. BOJ 16456 : 하와와 대학생쨩 하와이로 가는 거시와요~ - S1

DP + 약간의 관찰 문제.

모든 칸을 한 번씩만 지나갈려면, 2칸을 건넌 상태에서 다음에 해야할 행동은 뒤로 1칸 가는 게 고정됨을 알 수 있다.

그리고 뒤로 1칸 가는 행동의 다음 행동은 항상 또 2칸을 건너는 행동으로 고정됨을 알 수 있다.

그래서 결과적으로는 2칸을 건넜다면 다음에는 꼭 1칸만 뛸 수 있다고 생각해도 된다.

그래서 DP table을 dp[0][i]를 마지막에 1칸 뛰는 방법으로 i칸에 도착한 방법의 개수, dp[1][i]를 마지막에 2칸 뛰는 방법으로 i칸에 도착한 방법의 개수라고 하면...

dp[0][i] = dp[1][i-1] + dp[0][i-1], dp[1][i] = dp[0][i-2]로 점화식을 세울 수 있다.

근데 여기서, dp[1][i-1] = dp[0][i-3]은 결국 dp[0][i]에 더 해지는 것을 파악하면 또 DP 테이블을 1차원으로 줄일 수 있다.

DP식 최적화가 가능한게 뭔가 마음에 든 문제였다.

 

11. BOJ 31497 : 생일 축하합니다~ - B2

Implementation + Ad hoc 문제.

그냥 각 사람별로 2번씩 물어보면 된다. 두 번 다 맞다는 말이 나오면 해당 사람이 생일이다.

그런 경우가 없었으면 한 번만 맞다는 말이 나온 사람이 생일이 된다.

 

12. BOJ 24417 : 알고리즘 수업 - 피보나치 수 2 - S4

나는 DnC (Squaring) + Math 문제로 풀었다.

1도 풀었는데, 1과는 다르게 N의 범위가 2*10^8까지 가능해서 코드1의 실행 횟수에는 뭔가 패턴이 있다는 판단을 하였다.

그래서 대강 대입해보니 이게 또 피보나치 수를 이루는 것을 알았다.

매우 큰 N에 대해서 N번째 피보나치 수는 당연히 분할정복을 활용한 거듭제곱으로 행렬 계산을 하니까 그렇게 풀었는데...

이게 난이도가 S4로 측정되어 다른 풀이 방법이 있나 싶었다. (기본이 그래도 골드 중위권일텐데...)

기여창을 보니 C++로는 O(N) dp도 통과한다고 해서 다시 풀어보니 한 600~700 ms 사이로 통과했다.

그래서 붙은 태그는 Math + DP인데... 아마 원작자의 의도는 내 풀이였을 것 같다.

 

13. BOJ 25418 : 정수 a를 k로 만들기 - S3

BFS 문제.

사실상 숨바꼭질 시리즈랑 비슷하게 풀 수 있다.

 

14. BOJ 2003 : 수들의 합 2 - S4

나는 Prefix Sum + Hash map으로 풀었다.

P[i]를 A[1] + ... + A[i]로 두었을 때, A[i]가 마지막 원소로 존재하는 연속된 수열 중 수열의 합이 M인 개수는 j < i 인 P[j] 중 

P[j] = P[i]-M을 만족하는 결과가 몇 개인지를 세어보면 된다.

이를 Hash map으로 관리하여 각 값이 몇 번씩 나오는지를 세어보게 하면 된다.

근데 정해는 그냥 모든 구간에 대해서 브포를 돌리는거라고 한다. (애매할 것 같아서 안 했는데...)

 

15. BOJ 13156 : Selling CPUs - G5

DP 문제.

문제 상황을 보고 State를 정하는 작업을 하였다.

State : DP[i][j] = i번째 상인까지 총 j개를 팔았을 때의 최대 이득

점화식 : DP[i][j] = max(DP[i-1][j-k] + p[i][k]) (0 <= k <= j)

이러면 총 시간복잡도 O(MN^2)으로 DP식을 돌려서 풀 수 있었다. 푸는데 한 13분 정도 걸렸다.

슬슬 DP랑 Greedy 연습도 시작해야지.

 

16. BOJ 26607 : 시로코와 은행털기 - G3

Knapsack DP 문제.

a+b = x 는 고정이므로 k개의 ai의 합을 M이라고 하면 M * (kx - M) 이런 꼴을 우리는 최적화 하려는 걸 알 수 있다.

그러면 dp식을 아래와 같이 세우면 된다.

State : dp[i][j] = i명의 사람의 a의 합이 j인지 가능한가?

점화식 : dp[i][j] = dp[i-1][j-p[l]] || dp[i][j] // l번째 사람까지 보았을 때...

그래서 나중에 dp[k][j] = 1인 j들을 보고 j * (kx-j)를 계산하여 그 중 최댓값을 구하면 된다.

(사실 kx/2에 제일 가까운 j를 찾아서 구해도 되기는 하는데... 그러면 이분탐색을 해야하니 좀 더 번거롭긴하다.)

DP 연습을 확실히 많이 해야겠다는 생각이 들었던 문제.

 

17 ~ 18. [제4회 고려대학교 MatKor Cup : 2024 Winter/Spring Open Contest] - (Solved : 2 / 15) : 배경 조건만 맞추었다.

 

17. BOJ 31533 : Furiosa AI 영상 처리 가속 - B2

Math + Case-working .문제.

일단 확실한 건 Renegade를 한 컴퓨터에 바르면 해당 컴퓨터는 일하는 속도가 더 빨라진다.

그러므로 Renegade를 특정 컴퓨터에 발랐을 때, 해당 컴퓨터에 두 개의 일을 모두 주는 경우랑 하나하나 나눴을 때 경우의 시간을 모두 계산하여 그 중 최솟값을 출력하면 된다.

 

18. BOJ 31534 : 현대모비스 선풍기 굴리기 - S5

Math + Geometry 문제.

기하 문제라서 아래와 같이 그려서 설명해야할 것 같다.

a,b,h는 문제에서 나온 변수고, 나머지는 임의로 내가 지은 것임.

 

그러면 그리는 자취의 넓이는 ((c+d) ^ 2 - c ^ 2) * phi 가된다.

h2 = h * a / (b-a), c ^ 2 = h2 ^ 2+ a ^ 2, (c+d) ^ 2 = (h2+h) ^ 2 + b ^ 2 이므로 이를 대입해서 계산하면 되는데,

b = a 면 아에 원통 모양이라서 자취가 무한하게 남으니 -1를 출력해주어야 한다.

그리고 혹시나 몰라서 나는 a > b이면 swap(a,b)를 해주긴 했다. (어차피 뒤집어서 굴려도 같은 넓이가 나오니깐)

 

19. BOJ 1275 : 커피숍2 - G1

Segment Tree 문제.

사실상 Segment Tree 기본문제였다. 

수열과 쿼리 문제와 다른 점은 한 쿼리에 합 쿼리 + 업데이트 쿼리가 같이 들어오는 정도였다.

 

20~24. [2024 상반기 전남대학교 PIMM 알고리즘 파티] - (Solved : 5 / 9) : 끝나기 1시간 전부터 풀기 시작했다. 1시간만에 5솔 정도에 모두 1트 AC받아서 기분이 너무 좋았다.

 

20. BOJ 31561 : 시계탑 - B4

Math 문제였다.

그냥 처음 30분은 나누기 2를 한 결과를 더하고, 30분이 넘어가는 시점부터 남은 30분에서는 3/2를 곱하면 된다.

 

21. BOJ 31562 : 전주 듣고 노래 맞히기 - B1

Implementation + Hash map 문제였다.

여러 구현 방법이 있겠지만 나는 key : 첫 세 음, value : 노래 제목 이렇게 넣었다.

그러면서 만약에 key가 중복되면 value를 ?로 바꿔서 중복 체크를 하였다.

 

22. BOJ 31563 : 수열 회전과 쿼리 - S2

Math + Prefix Sum 문제였다.

상대적인 위치가 변하지 않으니 첫 번째 element의 위치가 어느 위치로 변하는 지만 기록해도 된다.

이후에 Prefix Sum을 할 때 역으로 각 원소들의 처음 위치를 계산하여 알맞게 Prefix Sum 결과를 더하면 된다.

 

23. BOJ 31564 : 육각타일미로 탈출기 - S1

BFS 문제였다.

기본적인 BFS 문제인데, 그냥 y와 x의 변화량이 y가 짝/홀일 때 바뀌는 정도?

Implementation에 좀 더 비중을 둔 문제 같았다.

 

24. BOJ 31566 : 힘세고 강한 아침 - G2

Floyd-Warshall 문제였다.

문제 설명만 보면 결국 특정 노드를 지나지 않고 최단거리 찾는 건데...

그냥 N이 작아서 각 노드별로 해당 노드를 지나지 않고 플로이드-워셜을 돌리고, 쿼리별로 O(1)로 대답을 해주면 된다.

총 시간복잡도는 O(N^4 + Q)인데, 오프라인 쿼리를 쓴다면 O(N^4 + QlogQ)가 되긴 할 거다.

(오프라인 쿼리를 쓴다면 필요없는 계산은 더 줄일 수 있어서 좀 더 빠르긴 하다. 그렇지만... 굳이?)

 

그러고보니 지난주부턴가 이번주 부턴가 이제 브론즈는 대회 문제 아니고서는 기록하지 않기로 하였다.

이번 주 일지는 여기서 끝.