더블링(doubling, binary lifting, 희소배열,sparse table)에 대해 배우기

https://deepdata.tistory.com/972 희소 배열(sparse table) 자료 구조 배우기https://cp-algorithms.com/data_structures/sparse-table.html Sparse Table - Algorithms for Competitive ProgrammingSparse Table Sparse Table is a data structure, that allows answering range queries. It can answer most range queries in $O(\log n)$, but its trdeepdata.tistory.com 희소 배열(sparse table)로도 알려진 더블링(doubling) 기법은 어떤 횟수 K를 2의 거듭제..

• format_list_bulleted 알고리즘/희소배열(더블링)
• · 2026. 1. 1.
• textsms

대표자가 같으면 union하지 말아야한다 (union by rank 주의점)

https://atcoder.jp/contests/abc420/tasks/abc420_e E - Reachability QueryAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp n개의 정점과 0개의 간선이 주어진다. 각 정점은 1번부터 n번까지 번호가 있고, 처음에 모든 정점은 흰색이다. q개의 쿼리가 주어지는데 각 쿼리는 3종류중 하나이다. 1) u와 v를 무방향 간선으로 연결 2) v가 흰색이면 검은색으로 바꾸고 검은색이면 흰색으로 바꿈 3) 정점 v에서 검은색 정점에 0개 이상의 간선을 타고 도달할 수 있는지 검사한다..

• format_list_bulleted 알고리즘/분리집합
• · 2025. 8. 27.
• textsms

persistent linked list이용한 문자열 변화 추적하기

1. persistent linked list “퍼시스턴트(Persistent) 연결 리스트”는 한 번 만든 리스트를 “불변(immutable)”으로 유지하면서도, 수정할 때마다 과거 버전까지 그대로 보존할 수 있게 해 주는 연결 리스트입니다. 1) 왜 ‘퍼시스턴트’인가?일반 연결 리스트는 노드 값을 바꾸거나 추가·삭제하면 기존 상태가 없던 일처럼 사라집니다.반면 퍼시스턴트 리스트는 “이전 상태”를 그대로 남겨 두고, 수정 후 새 리스트 버전을 만들어 줍니다.즉, 여러 시점(version)의 리스트를 동시에 관리할 수 있죠. 2) 어떻게 불변성을 지키나?노드는 절대 수정하지 않는다.새로운 내용만 새 노드로 생성하고,변경되지 않은 구간은 **기존 노드를 그대로 재사용(공유)**한다.각 버전은 “헤드 포인터..

• format_list_bulleted 알고리즘/고급 자료구조
• · 2025. 6. 23.
• textsms

체력 제한이 있어 끝까지 갈 수 없는 기묘한 다이나믹 프로그래밍(O(NHM)을 O(NM)으로 줄이는 트릭?)

E - Battles in a Row E - Battles in a RowAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp n마리의 몬스터와 차례대로 싸우고자 하는데, 현재 체력 h 마력 m이 있다. i번째 몬스터와 싸울때 두가지 중 하나를 선택할 수 있다. 1) 현재 체력이 A[i]이상일때, A[i]만큼 체력을 감소시키고 몬스터를 처치 2) 현재 마력이 B[i]이상일때, B[i]만큼 마력을 감소시키고 몬스터를 처치 n마리의 몬스터를 모두 쓰러뜨리거나, 어떤 행동도 취할 수 없으면 게임 종료 게임이 끝날때까지 몬스터를 쓰러..

• format_list_bulleted 알고리즘/다이나믹 프로그래밍
• · 2025. 6. 19.
• textsms

vertex multiplexing을 이용한 가중치의 bitwise xor이 최소가 되는 경로

https://atcoder.jp/contests/abc410/tasks/abc410_d D - XOR Shortest WalkAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 방향 그래프가 주어지는데, A에서 B로 가는 간선의 가중치가 W이다. 이때, 1번부터 N번 정점까지 경로의 가중치들의 bitwise xor이 최소가 되는 경로에 대해 그 최솟값을 구하면? 여기서 1번부터 N번 정점까지 경로는, 동일한 간선이나 동일한 정점을 여러번 방문하더라도, 처음 시작점이 1번이고 마지막 종점이 N번인 경로이다. ----------..

• format_list_bulleted 알고리즘/그래프 이론 정복기
• · 2025. 6. 18.
• textsms

원 위에서 정삼각형을 이루게 하는 점을 고르는 방법

https://atcoder.jp/contests/abc409/tasks/abc409_c C - Equilateral TriangleAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 원주의 길이가 L이고 점 1,2,3,..,N이 원 위에 찍혀있다. i+1번째 점은 i번째 점에서 시계방향으로 di만큼 떨어져있다. 서로 다른 세 점 (a,b,c)를 고를때 이들이 정삼각형을 이루게 되는 그러한 (a,b,c)의 개수를 구한다. ----------------------------------------------------------..

• format_list_bulleted 알고리즘/애드 혹 알고리즘
• · 2025. 6. 15.
• textsms