13576 Prefix와 Suffix P2
#string #z
Z알고리즘 연습용으로 풀었다.
Z알고리즘이란, 각각의접미사와 전체 문자열의 가장 긴 공통 접두사의 길이를 빠르게 구하는 알고리즘으로, O(n)으로 해결할 수 있다.Z알고리즘에 관해선 따로 포스팅을 해보거나 해야겠다. 여기서 더 얘기하면 길어질것 같고..Z알고리즘을 돌려 배열을 만든 뒤, 접미사와 접두사가 일치한지, 그리고 bisect를 활용해 몇번 등장하는지 체크해주었다.
32136 소신발언 G1
#parametric search
반대로 생각해 T가 주어 졌을때, 모든 시간안에 얼음을 녹일 수 있는가? 라는 문제로 변경해보면, parametric search으로 T시간안에 녹일 수 있냐 없냐? 문제로 변경하게 된다. 이점을 이분탐색으로 찾아나갈 수 있다
추가로 삼분탐색으로도 풀수 있는데, 2차원 그래프에서 y를 녹는 정도 max(D), x축을 i번째 히터의 위치로 둔다면, convex한 형태의 그래프가 나오는데 이 그래프의 극솟값이 최적으로 놔둘 수 있는 위치 i가 된다.
두 방법에 대해 둘다 풀어봤다. 재미있는 문제
parametric search
http://boj.kr/e49d28bae70644588301cf277803e28f
tenary search
11662 민호와 강호 G4
#tenary search
두 사람의 거리차 d를 y축으로 time을 x축으로 둘 때, 그래프의 형태는 아래로 볼록한 convex한 형태로 나타내지고, 이 그래프의 극솟값은 최소거리차이 가 된다.
위 극솟값을 삼분탐색으로 찾아주면 된다.
27488 Sum of Two Numbers S2
#math #ad_hoc
n이 주어지면 x, y의 합이 n이 되어야 하고, x, y의 각 자릿수의 합이 최대 1차이가 나는 x, y를 찾는 문제
n의 각 자릿수 / 2가 x,y의 그 자리수가 되어야 하고, 짝수면 그냥 /2 나누면 된다.
만약 홀수 일 때 x,y를 /2, /2+1 두개로 나누어야 하는데 이에 대한 예외처리를 잘 해주어야 한다.
"최대" 라는 키워드를 안봐서 무조건 1차이가 나게 해야하는줄 알고 맞왜틀을 좀 한 문제
22352 항체 인식 G5
#graph
BFS, DFS 아무거나 사용하여 그래프 내에 연결되어 있는 component를 찾은 다음,
각 component별 백신의 작용 대상이 될 수 있는지를 검사해야 한다.
27028 Distance Queries P5
#lca
lca의 weight가 붙어 있는 버전
direction이 주어지는데, 아~무쓸데없다. 혼동을주기 위한용
lca의 깊이를 dfs로 수행할때 현재 노드까지의 누적 weight를 같이 계산해주자.
lca 전체 코드는 log n으로 수행할 수 있는 템플릿을 사용했다.
3682 동치 증명 P2
#scc
TBD
과제 때문에 바빠 많이 못풀었다.
'ps > Solved' 카테고리의 다른 글
| 10월 4째주 PS정리 (0) | 2024.10.22 |
|---|---|
| 10월 3째주 PS 정리 (1) | 2024.10.14 |
| 10월 2째주 PS 정리 (0) | 2024.10.07 |
| 9월 4째주 PS정리 (2) | 2024.09.24 |
| 9월 3째주 PS 정리 (0) | 2024.09.16 |