Week 08 알고리즘 공부 기록 [lazy propagation, 머지 소트 트리, 펜윅 트리, mo's, mcmf]

12.23 ~ 12.29

 

lazy propagation

머지 소트 트리

펜윅 트리

오프라인 쿼리 / mo's

min cost max flow

 

이번주는 PintOS 프로젝트 1을 진행했다. OS란 무엇인가 잘 설명된 영상 강의들을 몇시간 들었는데, 아무래도 영상이란게 자기가 글을 읽는것에 비해서 정보의 밀도가 낮다보니 그리 집중이 되지가 않았다. 그래서 남는 머리와 손으로 알고리즘 문제를 풀어가면서 듣고 강의는 거의 한귀로 듣고 한귀로 흘린 것 같다. 이걸 멀티태스킹이라 해도 되나? 대학생 시절이랑 똑같은듯...

 

세그먼트 트리의 갱신을 필요한 시점까지 늦춰 효율을 개선한 lazy propagation

정렬된 부분수열을 저장하는 머지 소트 트리

크기 n으로 가볍지만 부분합에 대해서는 세그먼트 트리와 같은 기능을 할 수 있는 펜윅 트리

쿼리간의 순서가 답에 영향을 주지 않는 오프라인일 때 쿼리의 그룹분할과 정렬로 시간복잡도를 줄이는 mo's

최대 유량 문제에서 간선에 코스트가 추가된 min cost max flow 문제를 해결하는 알고리즘

 

mo's정도만 새로 배운 개념인데 이건 직관적으로 이해가 되는 종류의 알고리즘이고, 나머진 다 기존에 알던 알고리즘에서 연계되는 개념이다. OS 강의도 흐름을 놓지 않는 선에서 들으면서 하다보니 이해에 깊이가 필요한 종류의 알고리즘은 다루기 버거웠다. FFT라든가.

 

다음주부터는 1월이다. 12월의 알고리즘 공부 목표는 달성했으니 연말까진 문제풀이는 잠깐 놓아주고, 1월의 플랜을 세워봐야겠다. 레이팅도 목표에 거의 도달했고 배우기로 점찍어둔 알고리즘도 몇 안남았다. 아마도 1~2주 안에 새로운걸 배우는 과정은 정리하고, 남은 기간은 배웠던걸 정리하고 그리디나 DP 위주로 풀어보며 문제해결력을 기르는데 쓸 것 같다.