2021-08-08 Problem Solving 오랜만에 문제 해결을 좀 해봤다. 18227. 성대나라의 물탱크 DFS ordering을 이용하여 트리를 직선으로 펼 수 있다. 구체적으로는, DFS에서 정점 $u$를 처음 방문하는 시각을 $in[u]$, 빠져나오는 시각을 $out[u]$라 할 때, $u$의 서브트리의 방문 시각은 $[in[u], out[u]]$ 범위에 속함을 알 수 있다. 이를 이용하면, 트리를 선형으로 다룰 수 있고, Binary Indexed Tree 와 같은 자료구조를 함께 얹어서 문제를 해결할 수 있다. (왜냐하면, 어떤 정점에 물이 차는 횟수는, 해당 정점을 루트 노드로 하는 서브 트리에 물을 채우려 시도하는 횟수와 같기 때문이다.) 참고로, DFS ordering을 이용하여 트리를 직선으로 펴는 테크닉은 여러 분야에 응용의 .. 2021-08-01 Problem Solving 한 동안 정신 없는 일정 때문에 알고리즘 문제 해결을 별로 하지 못했으나, 최근에 여유가 생겨 SCPC 대비도 해볼 겸 다시 잡기 시작했다. 이번에 해결한 문제들을 정리해본다. 어찌 뒤로 갈수록 풀이를 대충 적은 것 같다... 21586. Another Substring Query Problem 쿼리가 하나만 주어진다면 어떨까? 문자열 $S$에 특정한 패턴 $P$가 $k$ 번째로 등장하는 지점을 찾는 문제가 된다. 이는 라빈 핑거프린트를 이용하여 문자열을 해싱해놓은 후, $|P|$ 길이의 부분 문자열을 살펴보며 쉽게 해결할 수 있다. 이 경우, 전체 과정이 약 $O(|S| + |P|)$ 정도의 시간에 이루어진다. 그런데, 이 과정을 모든 쿼리에 대해 반복하게 된다면, $O(Q(|S| + |P|))$ 정.. 운전을 시작했다 집에 낡은 소나타 한 대를 아무도 안타서 요즘에는 내가 굴리기 시작했다. 처음에는 아파트 단지 한 바퀴 도는 것도 힘들었는데, 운전 2일차에 분당에서 신사동 호텔까지 차를 끌고 가 봤던게 운전 실력 향상에 큰 도움이 되었던 것 같다. 운전 2일만에 차를 긁어먹은 건 다소 안타까운 일이지만.. 별로 티가 안나서 크게 신경 안쓴다. 주차 연습은 아래 사진을 찍은 마트에 오가면서 크게 늘었던 것 같다. 좁은 골목길을 두어시간 정도 빙글빙글 돌 일이 있었는데 그 때 차 폭 감에 대한 이해도 늘었던 것 같다. 그 외에는 그냥 한남동의 마리또 에 몰리에라는 파스타 가게에 밥 먹으러 다녀오면서 고속도로 주행 연습을 했던 것 같다. 아무튼 안전 운전 하도록 노력해야지. 이전 1 ··· 6 7 8 9 10 11 12 ··· 22 다음
