Algorithm/Concepts18 위상 정렬(Topological Sort) 목차 위상 정렬(Topological Sort) 위상 정렬(Topological Sort)은 방향 그래프의 모든 노드를 "방향성을 거스르지 않도록 순서대로 나열하는 것"을 말합니다. 즉, 그래프 상에서 어떤 노드로 가기 위한 선행 노드들을 모두 거친 후에 해당 노드를 방문할 수 있는 순서로 노드들을 나열하는 과정입니다. 위상 정렬은 일반적으로 사이클이 없는 방향 그래프(Directed Acyclic Graph, DAG)에서만 수행할 수 있습니다. 예를 들면, 수강신청을 할 때 선수과목이 있는 경우 선수 과목을 먼저 듣고 나서 해당 강의를 수강할 수 있습니다. A->B / B->C / B->D / C->D 가 있다고 할때, A, B, C, D 순서대로 들어야지 모든 과목을 수강할 수 있습니다. 만약 A B.. 2024. 3. 21. 비트마스킹(Bit Masking) 목차 비트마스킹(Bit Masking) 비트마스킹은 일종의 기술입니다. 이진수 표현을 활용해 값을 저장하거나 연산하는 기법으로 빠른 연산이 가능합니다. 비트 연산자 종류 and(&) : 둘 다 1이여야지 1 / 나머지 0 or(|) : 둘 중에 한 개라도 1이 있다면 1 / 둘다 0일 경우 0 xor(^) : 둘 중에 한개만 1일 경우 1 / 둘다 1이거나 0일 경우 0 not(~) : 1인 것은 0으로 0인것은 1로 변환 왼쪽 쉬프트(n 은 A를 2**n으로 나눈것 비트 연산자의 활용 예시 특정 mask에 n번째 비트값이 1인지 확인하기 1 2024. 3. 21. 느리게 갱신되는 세그먼트 트리(Lazy Segment Tree) 목차 느리게 갱신되는 구간 트리(Lazy Segment Tree) 세그먼트 트리랑 개념은 동일하지만, Lazy 세그먼트 트리는 특장 인덱스 값 하나만 update하는 것이 아닌, 구간의 값을 한 번에 update 해주는 경우에 사용합니다. 해당 구간을 업데이트할때 바로 업데이트를 진행하는 것이 아닌, lazy에 값을 저장해두었다가, 나중에 해당 노드로 들어가게 된다면, 거기에서 그 노드를 업데이트를 진행시켜줍니다. 세그먼트 트리의 경우 update 할때마다 해당구간에 대해서 업데이트를 진행해주게 되면, 그 구간에 대한 인덱스들을 모두 업데이트를 진행해야하기때문에 시간이 오래 걸리게 됩니다. 리스트 길이가 N개고 쿼리가 Q개라고 한다면 결국 쿼리 한개당 구간에 대한 인덱스를 모두 업데이트를 진행해야하기때문.. 2024. 3. 20. 구간 트리(Segment Tree) 목차 구간 트리(Segment Tree) 세그먼트 트리는 구간 쿼리와 갱신(Update) 작업을 효율적으로 처리할 수 있는 자료 구조입니다. 배열의 특정 구간에 대한 정보(예를 들면 합, 최댓값, 최솟값)를 빠르게 계산하고, 배열의 원소가 변경될 때 이 정보를 쉽게 업데이트할 수 있도록 설계되었습니다. 리스트를 슬라이싱 해서 해당 구간의 연산을 자주 하는 문제가 있을 경우 세그먼트 트리를 이용하여 시간 단축이 가능합니다. 전체 배열의 개수가 N이고 (특정 리스트 슬라이싱 구간 연산) 쿼리의 개수가 Q라고 할 경우, 시간복잡도는 리스트 슬라이싱으로 O(N), 쿼리연산으로 O(Q)이므로 결국 O(QN)의 시간복잡도가 걸릴 것입니다. 반면, 세그먼트 트리를 사용하면, 초기 배열에 대한 트리를 구성하는 데 O(.. 2024. 3. 20. 이전 1 2 3 4 5 다음
