오늘부터 PS 공부일지를 써 보려고 한다!
입시가 끝나서 PS를 자유롭게 할 수 있는 몸이 되었으므로,,, 앞으로 꾸준히 글을 쓸 예정이다.
오늘은 LCA 알고리즘과 희소 테이블을 공부했다.
케이스 분류가 정말 빡센 문제였다.
쿼리로 들어오는 두 정점이 일직선 상에 있는지 아닌지를 우선 나누고,
일반적인 트리의 형태를 그려서 각 정점별로 답이 될 수 있는 값을 찾는다.
이 때 판단의 기준을 1번 정점, u, v, lca(u, v), 그리고 각 정점의 depth 값으로 한다.
lca, 그리고 희소 테이블(binary shifting)을 이용하는 문제이다.
1, 2번 쿼리 모두 lca를 찾는 과정에서 만든 이동 배열을 재사용해서 해결할 수 있다.
역시 lca와 희소 배열을 이용하는 문제이다.
희소 배열의 각 항을 dp[n][k]: n번 정점에서 2^k번 올라갈 때 거리의 최대/최솟값으로 정의하면
한 쿼리당 O(logN)으로 해결할 수 있다.
희소 배열을 이용하는 문제인데, 발상이 참신하다.
u번 칸에 있는 개미가 최대로 이동할 수 있는 칸의 번호를 v번이라고 하자.
binary shifting을 이용하면 depth[u] - depth[v]를 이진수로 나타내었을 때, 켜져 있는 비트 수만큼 점프하게 되는데,
가장 depth[v]가 작은 v를 찾기 위해, 크기가 큰 k부터 시도하여 2^k 만큼 점프할 수 있는지를 확인해준다.
크기가 큰 k부터 확인하기 때문에 최적해를 찾을 수 있음이 보장된다.
정리하자면, 희소 배열은 주어진 n에 대하여 n번 이동한 결과를 O(logn)의 시간복잡도로 찾아 주는 자료구조이지만,
이를 응용하면 이분 탐색(parametric search)과 마찬가지로 결정 문제를 최적화 문제로 바꿔 풀 수 있게 해 준다.
이러한 원리를 이용하여 lca도 구하고, 개미(P5) 문제도 풀 수 있게 된다.
최근 업다운 랜디 라는걸 알게 돼서 시도해 보고 있다.
[Baekjoon] 업다운 랜디 #1
무한 랜디법에 대한 소개를 받았습니다. 시간 나는 대로 한 번 달려봅니다. 방식은 대충 solved.ac에서 (ti...
blog.naver.com
하루에 세네문제씩 풀면 그냥 랜디보다 재밌을 것 같다!
골랜디는 그래도 잘 할 줄 알았는데... 골드5에서 입구컷 당해서 슬프다 ㅋㅋ큐ㅠ
게임 이론 문제이다.
첫 문제부터 아직 공부해 보지 않은 게임 이론 문제가 나와서 적잖히 당황했다...
돌이 n개 남아있을 때, 선공이 지기 위한 조건은 n-1, n-3, n-4번째 턴에서 선공이 승리할 때이다.
손으로 케이스를 몇 개 써보면 7의 주기로 승패가 결정난다는 것을 알 수 있다.
문자열 문제인데, 오늘 공부한 희소 테이블이 생각나 바로 짰더니 맞았다.
다만 구현에서 좀 실수가 있어서 시간 내엔 못 풀었다.
정해는 주기가 최대 len이라는 점을 이용해 브루트포스로 푸는 방법인 것 같다.
(일대일대응의 성질)
20444번. 색종이와 가위(G5, 수학, 25:00)
드디어 시간 안에 풀었다!
가로선과 세로선의 개수를 변수로 두고 식을 세운다.
식을 정리하면 정수 조건의 부정방정식이 나오는데, Naive하게 탐색하면 시간 초과를 받는다.
나는 식을 한 문자에 대해 정리하여 이차방정식을 얻어내고, 이차방정식의 근이 정수근인지를 판별하는 알고리즘을 짰다.
(참고) https://woojin029.tistory.com/3
제곱수 판별 알고리즘
정수 N이 주어졌을 때, N=k*k로 나타내어지는 정수 k가 존재하는지 판별하는 알고리즘이다. sqrt 함수의 시간복잡도가 O(logN)이라고 가정하면, 알고리즘의 시간복잡도는 O(logN)이 된다. int issqrt(int n){
woojin029.tistory.com
이분 탐색으로 정수근이 존재하는지 판별하는 방법도 있는 것 같다.
(왜 내 골랜디에는 이런 문제들밖에 안 나오는가....)
단순한 dp 문제지만 mod 처리, 사람 순서 등 실수할 구석이 많은 문제이다.
지금까지 지나온 층수, 두 사람 간 간격을 dp 인자로 두고 식을 세우면 된다.
'PS > 공부' 카테고리의 다른 글
| 2024-03-19 PS 공부 (1) | 2024.03.19 |
|---|---|
| 2024-01-21 PS 공부 (1) | 2024.01.21 |
| 2023-12-13 PS 공부 (0) | 2023.12.13 |
| 2023-12-06 PS 공부 (0) | 2023.12.06 |
