1일 1트리 기록장

1일 1트리란?

- 고등학교 2학년에서 3학년으로 넘어가는 겨울방학에 1일 1수쿼 프로젝트를 진행하여 하루에 수열과 쿼리 문제를 하나 이상 해결하거나 풀이를 정리하는 과제를 스스로에게 부여하여 1달 조금 넘게 진행하였다. 당시의 기억이 행복하게 남아있기도 하고, PS를 거의 2년간 쉰 지금 아직도 수쿼 관련된 자구들은 기억에 남아있는 것을 보아 학습효과도 상당히 좋았던 것 같다.

- 이를 이어 오늘부터 1일 1트리를 진행하려고 한다!

- 는 아니고... 사실 지금 학기 중이고 곧 시험기간이라 많이 바쁘다.

 

- 아직 PS를 본격적으로 공부해보지 않은 친한 친구들과 팀을 꾸려 ICPC에 나가게 되었다. 나도 PS를 오래 쉬었으니 인터넷 예선을 통과하여 리저널을 찍먹하는 것이 목표이다.

- 팀원 중 한 명이 원래 수학을 잘하기도 하고, 요즘 자구와 DP에 빠져있다. 그리고 고등학교 시절 PS를 했을 때도 그래프가 약점이기도 했어서, 이번 기회에 그래프 위주, 그 중에서도 트리 알고리즘 위주로 공부하려고 한다.

 

- 1일 1수쿼 마냥 매일 풀거나 기록하는 것은 사실상 불가능하다. 학업 등 더 우선순위인 것들이 있기 때문.

- 몇 달이 걸릴지 모르겠지만 HLD, CD 등 예전에 알고 있었지만 감이 떨어진 개념들부터 트리와 관련된 "그들만의 웰노운"까지 전부 정복하려고 한다.

- 대부분의 글은 나의 독자적인 설명의 비율보다는 kks227 / JusticeHui 등 유명한 블로그의 내용을 보고 정리한 것의 비율이 높을 것이라는 사실을 밝힌다.

 

그럼 시작~

 

공부 기록

1. Heavy Light Decomposition

 

교과서 : https://justicehui.github.io/hard-algorithm/2020/01/24/hld/

기록장 : https://unorderedmap.tistory.com/49

10/7 : 남극 탐험(D5), 국제 메시 기구(D4), 안전한 비상연락망(D4)

10/8 : 트리와 쿼리 10(D3)

 

2. Centroid Decomposition

 

교과서 : https://justicehui.github.io/hard-algorithm/2020/08/25/centroid/

기록장 :

10/8 : UCPC 만들기(D5)

10/10 : 공장들(D4)