[일반] LCA배웟는데

[익명(223.39)]

N을 이진수로 생각해서 parent배열로 O(lgN)에 처리하는 이런 테크닉을 따로 부르는 말이 잇음??

또 이런 테크닉이 쓸 수 있는 조건이 뭐인지 잘 이해가안감 아직 LCA를 아해 못해서 그런가

함수 f의 정의역과 공역이 동일해야하나??

[익명(180.226)]

binary lifting

[익명(58.123)]

sparse table 희소배열 이라고 합니다!

[익명(223.39)]

이것도 LCA배우면서 같이 배웠는데 그러면 순열 그래프에서 N번 이동한 위치 빨리 구하는 것도 sparse tree로 되나?

[익명(223.39)]

이거랑 비슷한 테크닉을 냅색에 활용하는 문제가 있엇어서

[익명(223.39)]

그건 왜 되는건지모르겟네...

[익명(58.123)]

순열그래프가 뭔지 잘 모르는데 a_i -> a_(p_i) 이런식으로 섞는거라면 가능할것같음 근데 LCA에서 보통 쓰는것처럼 정점을 고정하고 2^k꼴을 늘리면서 만드는게 아니라 2^k를 고정하고 모든 정점들에 대해서 처리하는방식? 뭐라해야될지 모르겠네

[익명(223.39)]

boj.kr/12920 내가 말한냅색문제

[익명(223.62)]

정의역과 공역만 같으면 될거같은데?

[익명(223.39)]

아 잘못말햇네 공역

[익명(121.131)]

sparse table, binary lifting 둘 다 비슷한 거 말하는거임 outdegree가 1 이하인 그래프에서 간선 타고 넘어가는 걸 2^k 단위로 빠르게 계산하는 그런거도 가능

[익명(210.217)]

min max 같은건 전처리 잘하면 O(1)에도 됌 ㄷㄷ

[익명(223.39)]

이건 또 뭐노

[익명(210.217)]

https://cp-algorithms.com/data_structures/sparse-table.html
여기에서 Range Minimum Queries (RMQ) 문단 참조

[익명(210.217)]

2의 n승같은건 미리 전처리 해둬야하는 까다로움이 있기도하고 솔직히 상수나 로그나 별반 차이없긴한데... 알아둬도 손해는 없을듯?ㅋㅋ

[익명(210.217)]

이게 필요한 극한의 커팅상황은 오지 않길 빌자..

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[익명(223.39)]

ㄱㅅㄱㅅ