주간연습 (1) - 2023.08.18 ~ 2023.08.27

마지막 수정 시각: 2023-09-14 21:08:23

골드 5 난이도부터 다이아 4 난이도까지 순서대로 한 문제씩 뽑아서 12개의 문제로 구성된 셋을 일주일동안 푸는 연습을 진행하기로 했다. 그냥 뭐라도 꾸준히 풀어야 실력이 늘 거 같아서 시작. 매주 6~7개 정도 꾸준히 푸는 걸 목표로 생각하고 있다.

12개 중에 총 10개를 풀었다. 풀고 약 한달만에 쓰려고 하니 풀이가 잘 생각 안나서 그냥 감상만 정리.

A. BOJ 16965 (AC)

구간 개수가 작아서 매번 dfs를 통해 연결 여부를 파악해주는 식으로도 충분히 풀린다. \(O(N^3)\)에 해결.

B. BOJ 2459 (AC)

좌표 범위를 두 배로 늘려서 풀면 좀 편하다. 각 철사에 대해 자르는 직선 좌우로 x값이 바뀔 때마다 길이를 계산해준 후 가장 길이가 긴 것을 출력해주면 \(O(N)\)에 풀 수 있다.

C. BOJ 2091 (AC)

여러가지 풀이가 있을 것 같은데 나는 동전을 두 묶음으로 나눠서 (AB)로 만들 수 있는 것 / (CD)로 만들 수 있는 것을 따로 구한 후 서로 매칭해주는 식으로 풀었다.

D. BOJ 7869 (PASS)

딱봐도 구현 번거로워보이는 수학 / 기하 문제인 것 같고 별로 풀고 싶지 않아서 그냥 패스했다.

E. BOJ 17420 (AC)

지문이 조금 이해하기 힘들었지만 문제는 괜찮았다. 기한이 가장 적게 남은 기프티콘만 쓸 수 있다는 점을 이용해서 잘 그리핑해주면 그리디하게 해결할 수 있다.

F. BOJ 2376 (AC)

이것도 지문을 좀 잘못 이해해서 어려웠다. 간선 길이가 1로 고정이라는 걸 늦게 눈치채서... 문제의 조건을 이용하면 단말 정점 거리로부터 형태를 확정할 수 있는 정점 쌍을 바로 찾을 수 있고, 이 쌍을 찾고 나면 이 노드를 하나로 묶어서 다시 동일한 형태로 만들 수 있다. 재귀적으로 반복하면 됨.

G. BOJ 9623 (AC)

세그트리 + 이분탐색 표본같은 문제.

H. BOJ 17034 (AC)

답을 고정해놓고 이분탐색을 잘 하면 된다.

I. BOJ 25008 (AC)

롤링 해시를 잘 응용하면 풀 수 있다.

J. BOJ 20986 (AC)

정렬 문제로 바꿔서 생각해볼 수 있다. 높이 차이가 최대 2 이내라는 조건을 잘 만족할 수 있게 배열을 적절히 변형해서 생각하면 필요한 역위 개수를 구하는 식으로 문제를 바꿔서 모델링할 수 있다. 그 다음은 자료구조와 DP를 적절히 써서 \(O(N^2logN)\)에 해결 가능.

K. BOJ 17133 (AC)

지문이 해석하기 난해한데, 해석하고 보면 그냥 전형적인 플로우 문제다. 문제에서 시키는 형태에 맞춰 잘 모델링해주면 풀린다.

L. BOJ 12752 (PASS)

재밌어보이는 문제인데 어렵고.. 좀 고민해보다가 잘 모르겠어서 그냥 GG쳤다.