본문 바로가기

2021-08-21 Problem Solving 이번에도 문제를 비교적 꾸준하게 풀었던 것 같다. 특히, 이번 주 부터는 ho94949님, dennisstar님과 함께 하루에 랜덤 문제 5개를 뽑아서 하나 이상 푸는 챌린지를 하고 있어서 (나 말고 나머지 두 분은 웬만해서 거의 다 풀긴 하는듯) 더 자극이 되었던 것 같다. 20986. Group Photo 1번부터 $i$번까지만 생각해주는 방식으로 DP를 할 수 있다. 이 DP를 효율적으로 하는 방법에 대해서 생각해보면 되는데, $i$ 앞에 $j$가 오는지의 여부를 $N^2$개의 쌍에 대해 전부 이차원 배열에 구해둔 뒤, $x$축과 $y$축 두 방향 모두에 대해서 prefix sum 전처리를 해두고 활용할 수 있다. 15759. Talent Show 1000을 곱해주는 귀찮은 부분은 따로 빼두고 생각..
레이블과 소수자성 요즘 들어 나의 글쓰기 실력이 지속적으로 줄어가는 것을 느꼈다. 고로, 내가 했던 생각들을 짧게나마 기록하는 습관을 들이려 노력해본다. 우리 사회는 사람들에게 레이블을 붙이는 것을 참 좋아하는 것 같다. 예를 들어, 사회가 나에게 붙여준 레이블은 대학생, 개발자, 20대 등이 있다. 이렇듯, 사회의 각 구성원은 여러 레이블을 단 채로 살아간다. 그런데, 한 사람이 여러 레이블을 달고서 살아간다고 한들, 사회는 모든 레이블에 균등한 가중치를 두고 바라보지 않는다. 두 명의 20대 남성 개발자가 있다고 하더라도, 한 명에게는 20대라는 사실에, 다른 한 명에게는 개발자라는 사실에 더 초점을 두고 바라볼 수도 있는 법이다. 즉, 사회가 개인을 바라볼 때 더 우선적으로 바라보게 되는 레이블이 존재하는 것이다. ..
2021-08-08 Problem Solving 오랜만에 문제 해결을 좀 해봤다. 18227. 성대나라의 물탱크 DFS ordering을 이용하여 트리를 직선으로 펼 수 있다. 구체적으로는, DFS에서 정점 $u$를 처음 방문하는 시각을 $in[u]$, 빠져나오는 시각을 $out[u]$라 할 때, $u$의 서브트리의 방문 시각은 $[in[u], out[u]]$ 범위에 속함을 알 수 있다. 이를 이용하면, 트리를 선형으로 다룰 수 있고, Binary Indexed Tree 와 같은 자료구조를 함께 얹어서 문제를 해결할 수 있다. (왜냐하면, 어떤 정점에 물이 차는 횟수는, 해당 정점을 루트 노드로 하는 서브 트리에 물을 채우려 시도하는 횟수와 같기 때문이다.) 참고로, DFS ordering을 이용하여 트리를 직선으로 펴는 테크닉은 여러 분야에 응용의 ..