주간연습 (2) - 2023.08.27 ~ 2023.09.04

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

12개 중에 11개를 풀었다.

A. BOJ 21870 (AC)

문제에서 시키는 과정을 그대로 구현해주면 풀린다.

B. BOJ 24025 (AC)

좀 재밌었던 애드혹 문제. 이상 / 이하 범위 조건을 잘 이용하면 답이 되는 형태를 유도할 수 있다.

C. BOJ 15487 (AC)

DP로 해결할 수 있다. 뽑은 수의 개수와 지금 뽑는 수의 번호를 상태로 정의해서 쓰면 됨.

D. BOJ 1112 (AC)

각 자릿수를 -b진수에 대응시켜서 그냥 b진수 하듯이 처리해주면 된다. 유명한 문제. 처리해야할 케이스가 좀 이것저것 있어서 주의는 필요함.

E. BOJ 17840 (AC)

모듈러 \(M\) 안에서 주기가 반복될 것이므로, 미리 반복 주기를 구해두면 \(O(M+Q)\) 시간에 문제를 해결할 수 있다.

F. BOJ 10523 (AC)

랜덤 알고리즘으로 해결할 수 있다. 임의의 두 점을 골라서 그걸로 직선을 만들어보자. 그리고 나머지 점들에 대해 이 직선 위에 있는 점들의 개수를 세주고, 이게 \(p\)% 이상이면 yes, 충분히 많은 횟수를 테스트했는데도 아니면 no를 출력한다. 이것만으로도 충분한 이유는, p 제한이 최소 20이므로 저런 조건을 만족하는 직선이 있다면 임의의 두 점을 뽑았을 때 이 두점이 해당 직선 위에 올라갈 확률이 굉장히 높기 때문이다. 확률 계산을 직접 해보면 충분히 높은 신뢰도를 얻기 위한 테스트 횟수도 구할 수 있다.

G. BOJ 1217 (AC)

전형적인 2-SAT 문제로 모델링할 수 있다.

H. BOJ 1096 (AC)

잘 모르겠어서 풀이를 보고 풀었다.

상하 / 좌우로 각각 접는 방향에 대해 브루트포스로 경우의 수를 구한 후 그 둘을 조합해서 전체 경우의 수를 구하면 된다.

I. BOJ 9875 (AC)

삼각형 영역 안에 들어가려면 어차피 convex hull 안에도 들어가야하기 때문에, 한쪽 점 집합에 대한 convex hull을 구한 후 나머지 점들이 이 안에 들어가는지 확인하면 된다. convex hull 안에 들어가는지 여부는 hull을 맨 밑에서부터 스위핑하면서 hull이 차지하는 좌우 x 공간 구간 안에 점이 포함되는지 판단해주는 식으로 구현할 수 있다.

J. BOJ 8212 (AC)

DP 식을 잘 모델링해보면 덱을 이용해서 \(O(N)\)에 수행할 수 있게 최적화할 수 있는 꼴이 나온다. 이대로 구현해주면 풀린다.

K. BOJ 24477 (AC)

sparse table을 이용해서 각 지점에서 환승을 \(2^K\)번 했을 때 갈 수 있는 구간의 범위를 전처리해놓는 식으로 문제를 해결할 수 있다. 이제는 꽤 흔한 유형이 된 문제.

L. BOJ 14858 (PASS)

딱 봐도 내가 해결할 수 없는 유형의 수학 문제라 패스했다.