이분탐색을 처리할때, 일반적인 방법으로 구현하려면 쿼리마다 구간의 시작, 끝, 중간값을 다 저장하고 있어야 하는데, 구현도 귀찮고 수행 시간도 좀 걸린다
그보다 binary jumping 으로 이분탐색을 구현하면, 쿼리마다 현재 확인할 구간 위치 하나만 들고 있으면 되므로 구현이 훨씬 편해진다. 스텝값은 모든 쿼리에 공통이니.
0에서 시작해서 n/2, n/4.. 이렇게 증가시켜 나가는 방법보다. n에서 시작해서 n/2, n/4,.. 이렇게 감소시켜 나가는 방법이 좀더 효율적으로 구현할수 있었다.
디자인적으로 고민을 많이 했는데, PBS의 공통 로직과, 문제에 따라 달라지는 개별 로직을 분리해서 라이브러리화 시키는 것이 복잡했다.
어떻게든 PBS부분을 라이브러리 함수로 뽑아낸다면, 이 함수는 시뮬레이션을 한단계씩 진행하고, 각 단계에서 특정 쿼리의 조건이 만족되는지를 확인하고, 각 단계에서 특정 쿼리가 원하는 답을 얻어낼수 있어야 한다. 추가적으로 시뮬레이션을 다시 처음부터 진행할수도 있어야 한다.
가장 제대로 짜려면.. proceed(), is_valid(), get_answer(), reset() 의 멤버변수를 갖는 Simulation 인터페이스를 만들고, 유저는 이 인터페이스를 구현한 클래스를 PBS 함수에 인자로 넘겨주도록 하는 것이 옳은 설계일 것이다..
하지만 PS하는데 무슨 인터페이스에 상속까지 해가면서 코드를 짜는거는 좀 너무 나간것 같은 느낌….
함수에 전달할 것을 좀 줄여보려는 고민끝에 두가지 방법이 나왔다. 둘다 유저가 클래스를 만들어야 하는 것은 피하고, 차라리 함수 클로저를 이용해서 시뮬레이션 상태를 유지하려는 방법인데..
하나는, proceed() 함수를 직접 만들지 않고 매 스텝마다 is_valid 함수를 yield해주는 제너레이터로 구현하는 것. 대충 이런식이다
# 유저가 구현해야 할 부분
def simulate(queries):
def is_valid(query_no):
u, v = queries[query_no]
return dsu.find(u) == dsu.find(v)
def get_answer(query_no)
u, v = queries[query_no]
return dsu.size(u)
dsu = disjointset.DisjointSet(n)
for u, v in merge_list:
dsu.union(u, v)
yield is_valid, get_answer
def main():
...
binsearch.pbs(simulate, len(queries), len(merge_list))
...
# 라이브러리 부분
def pbs(simulate, ...):
...
for t, (is_valid, _) in zip(range(X), simulate()):
for q in queries:
if is_valid(q):
...
...
다른 방법은 proceed와 is_valid함수를 리턴해주는 클로저를 만드는 것. 대충 이런식이다
# 유저가 구현해야 할 부분
def simulate(queries):
def is_valid(query_no):
u, v = queries[query_no]
return dsu.find(u) == dsu.find(v)
def get_answer(query_no)
u, v = queries[query_no]
return dsu.size(u)
def proceed():
u, v = next(merge_iter)
dsu.union(u, v)
dsu = disjointset.DisjointSet(n)
merge_iter = iter(merge_list)
return proceed, is_valid, get_answer
def main():
...
binsearch.pbs(simulate, len(queries), len(merge_list))
...
# 라이브러리 부분
def pbs(create_simulator, ...):
...
proceed, is_valid, _ = create_simulator()
for t in range(X):
proceed()
for q in queries:
if is_valid(q):
...
...
전자가 좀더 짧은 느낌이라 전자로 구현했었는데.. 사실 크게 차이나는 부분은 아니다. 속도도 별로 차이는 없다
중요한것은 한참 뒤에 PBS라이브러리를 써서 문제를 풀때, 만들어야 하는 simulate 함수의 형태를 쉽게 다시 기억해낼 수 있는가인데.. 이것도 둘다 비슷해보인다; 음??