Week 06 알고리즘 공부 기록 [세그먼트 트리]

12.09 ~ 12.15

 

세그먼트 트리의 구현과 응용

 

 

??? : 이번주 과제는 지난주보다 구현량이 없어보이니 알고리즘도 꾸준히 해야지

 

6주차의 원래 목표는 세그먼트 트리 + KMP였는데 세그먼트 트리만 익히고 KMP는 보지도 못했다. 간단하게 이론을 볼땐 구간합을 저장한다길래 아 뭔가 아무튼 지엽적인 문제에 솔루션을 제공하는 자료구조겠구나 싶었는데, 정작 파보니 구간 합뿐만 아니라 정말 모든 종류의 'sub'에 대한 데이터를 다룰 수 있었다. 일단 세그먼트 트리를 구현하는법을 배워도 노드에 무엇을 저장할지, 어떤 노드 취합함수로 쿼리를 해결할지가 다 다르니까 한두문제 푸는걸로는 응용력에 도움이 안돼서 가능한 많은 문제를 풀어봤다.

세그먼트 트리 문제를 풀면서 느낀게, 단기간에 많은 개념을 머리속에 때려넣으면서 수준을 높이니까 새로 들어오는 지식의 유용성에 비해 그것을 이용할 내 구현력? 경험? 그런것이 너무 낮은 것 같다. 

 

게다가 이번주 본론인 말록랩에도 시간을 많이 썼다. 최초 구현은 일단 이해만 하고나면 5주차보다는 쉬웠는데, 성능 개선을 위한 알고리즘 개선이나 최적화가 파도파도 계속 나와서 목요일 아침까지도 계속 이쪽만 파게 됐다...

 

 

이번주 목표는 먼저 지난주에 못했던 KMP를 배우고 class 6을 따는것이다. 그리고 가능하면 class 7에 들어가서 볼록껍질이나 이분매칭, lazy propagation, 최대 유량 중 하나를 알고 넘어가려 한다.

이번주 과제인 웹서버 구현이 이름만 들어도 난이도가 있어보여서 가능할진 모르겠다. 일단 목, 금은 PS에 전부 쓸 생각이라 이틀 안에 최대한 풀어봐야겠다.