2023.12.31.

백준 4문제.

 

1. BOJ 10451 순열 사이클 - S3

순열 사이클 분할 기본 문제.

순열 사이클 분할이라는 태그가 무엇인가 싶어서 한 번 풀어보았다.

그런데 문제는 그냥 DSU로 풀려서 이 태그가 도대체 무엇일까라는 의구심이 더 강해지는 문제였다.

 

2. BOJ 27280 이기적인 목봉 체조 (Easy) - G3

DP 문제. 

예전에 실제 대회에서 어떻게 푸는지 감도 안왔던 문제.

이러한 DP 문제를 의외로 풀어본 경험이 없어서 업솔빙 했다.

미리 구간에 대한 힘을 계산을 다 해두고 DP를 돌리는 아이디어가 나한테는 신기했다.

이렇게 올해 설날 때 봤던 문제를 한 해의 마지막 날에 풀게되어 나름 마무리하는데 의미있는 문제.

 

3. BOJ 13547 수열과 쿼리 5 - P2

Mo's Algorithm 문제.

언젠가 손대보고 싶은 알고리즘이었는데, 연말 기념으로 한 번 손대봄. 

예전에는 이해하기 어려웠는데, 나름 이해가 된듯?

그리고 Sqrt decomposition한 결과를 따로 저장해야하는줄 알았는데, 아이디어만 겹치지 실제로는 구현 할 필요가 없어서 다행이었다. (너무 귀찮음...)

내년에는 저거 관련 문제들 많이 풀어봐야지.

 

4. BOJ 13548 수열과 쿼리 6 - P2

Mo's Algorithm 문제.

수열과 쿼리 5번에서 조금 수정을 해서 각 숫자를 몇 번씩 존재하는지를 저장하는 array 말고도 몇 번씩 존재한 숫자가 몇 개 인지를 저장하는 array를 하나 더 생성한다.

그리고 구간 쿼리에 대해서 몇 번씩 존재한 숫자가 몇 개 인지를 저장하는 array 가지고 풀면 된다.

어차피 1칸씩 움직일 때 정답은 +-1 만 변동되니 새로운 array가 0이 된다면 최댓값이 떨어지고, 0 이상이 된다면 최댓값 후보로 된다.

 

오늘 일지는 여기서 끝.

모두들 올해 한 해동안 고생많으셨습니다.

내년에도 모든 일들이 잘 풀리기를 기도하겠습니다 :)