백준 2042 - 구간 합 구하기 (Python)
이번 문제에서 세그먼트 트리를 사용하는 이유는 구간합을 빠르게 검색하고 수정하기 위해서입니다. 개념 자체는 쉬우니 바로 코드를 보고 이해하시면 됩니다.
Recent Posts
백준 2150 - Strongly Connected Component (Python)
되게 생소한 개념이라 찾아가며 풀었습니다. 자세한 내용은 코사라주 알고리즘, 타잔 알고리즘을 찾아보면 됩니다.
백준 13511 - 트리와 쿼리 2 (Python)
희소 테이블을 만든 뒤 다음의 조건에 따라 풀었습니다. lca-u + lca-v 출력 k <= depth[u] - depth[lca] 이면 u에서의 k-1번째 노드를 출력 k > depth[u] - depth[lca] 이면 남은 거리를 계산해서 v부터 계산
백준 3176 - 도로 네트워크 (Python)
바로 전 문제와 거의 흡사합니다. dp에 [노드, 최소거리, 최대거리] 이렇게 저장하는게 핵심입니다. pypy3로 제출해야 합니다.
백준 11438 - LCA 2 (Python)
전처리로 부모 관계를 정해준 뒤 푸는게 핵심입니다. pypy3로 제출해야 합니다.