3. 알고리즘 공부 (49) 썸네일형 리스트형 [416] 세그먼트 트리의 개념 1. 세그먼트 트리영어 단어 segment는 분할, 구간, 분절 등의 뜻을 지니고 있습니다.알고리즘에서 세그먼트 트리는 여러 값을 가지는 리스트의 특정 구간의 정보를 이진 트리 형태로 관리하는 자료구조를 말합니다. 2. 세그먼트 트리가 만들어지는 과정예를 들어, 1 ~ 10까지 10개의 숫자(원소)의 합을 세그먼트 트리로 만들면 다음과 같습니다.가장 먼저 루트는 전체 범위의 정보를 가집니다.그 정보가 숫자들의 합이므로 1~10까지의 합이 됩니다.다만, 아직 그 정보의 값은 정해지지 않습니다.왜냐하면 재귀적으로 자식을 만들고, 리프가 완성되었을 때 반환값을 통해 값이 정해지기 때문입니다.이제 루트의 자식을 만듭니다.이진 트리이므로 자식은 둘이며 범위는 반으로 나누어 줍니다.그럼 자식은 각각 1~5, 6~.. [415] 타잔의 SCC(강한 연결 요소) 알고리즘(파이썬 코드) 1. 강한 연결 요소 개념이번 글에서는 파이썬으로 타잔의 SCC 알고리즘을 구현한 코드를 살펴보겠습니다.강한 연결 요소에 대해 알고 싶으시다면 지난 글을 참고하세요.https://kimwooil.tistory.com/380 [380] 강한 연결 요소(SCC)와 타잔의 SCC 알고리즘(Tarjan's SCC algorithm)1. 강한 연결 요소(SCC; Strongly Connected Components) 유향 그래프(Directed Graph)에서 모든 정점이 다른 모든 정점에 도달할 수 있는 경우, 강하게 연결되었다고 합니다. 다시 말하면, 임의의 두 정점 사이kimwooil.tistory.com2. 타잔의 SCC 알고리즘 파이썬 코드위 이미지와 같이 그래프의 강한 연결 요소를 찾아보겠습니다. 가... [414] 2-SAT 문제(개념만, 코드 없음) 1. SAT(충족 가능성 문제)다음과 같은 논리식이 있다고 하면(∧는 and 연산입니다.),논리식 = 변수1 ∧ 변수2 ∧ 변수3변수1, 2, 3이 어떤 값을 가지냐에 따라 논리식은 참이 될 수도 있지만, 다음과 같은 논리식에서는논리식 = 변수1 ∧ not 변수1만약 변수1이 참이면 not 변수1은 거짓이 되기 때문에 위 논리식은 절대 참이 될 수 없습니다. 이렇게 참/거짓을 가지는 변수들로 이루어진 논리식이 주어졌을 때, 그 논리식이 참이 되는 변수값이 존재하는지 찾는 문제를 충족 가능성 문제(SAT)라고 부릅니다.https://ko.wikipedia.org/wiki/충족_가능성_문제 충족 가능성 문제 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 충족 가능성 문제(充足可能性問題,.. [381] 유향 그래프에서의 누적합 1. 문제위와 같은 유향 그래프가 주어졌을 때, 그래프를 탐색하며 정점의 값을 누적합하려면 어떻게 해야할까요?2. 깊이 우선 탐색(DFS; Depth-First Search)깊이 우선 탐색으로 값을 구하는 과정을 살펴봅시다.먼저 더 이상 간선이 없는 정점까지 탐색 며 값을 누적합니다.또 다른 경로를 탐색합니다.그 결과 누적합 최대값은 65입니다.물론, DFS로 이렇게 풀 수도 있으나 문제점이 보입니다.값이 5와 25인 정점은 다른 경로라면 탐색을 했더라도 다시 탐색해야합니다.이 문제를 해결하기 위해 다른 방법을 생각해봅시다.3. 너비 우선 탐색(BFS; Breadth-First Search)깊이 우선 탐색으로 경로마다 끝까지 탐색을 했더니 같은 정점을 여러 번 살펴봐야하는 문제가 있었습니다.그래서 이번엔.. [380] 강한 연결 요소(SCC)와 타잔의 SCC 알고리즘(Tarjan's SCC algorithm) 1. 강한 연결 요소(SCC; Strongly Connected Components) 유향 그래프(Directed Graph)에서 모든 정점이 다른 모든 정점에 도달할 수 있는 경우, 강하게 연결되었다고 합니다. 다시 말하면, 임의의 두 정점 사이에 한 정점에서 다른 정점으로, 그리고 다시 다른 정점에서 원래 정점으로 경로(사이클)가 존재하는 것을 의미합니다. 무향 그래프의 경우에는 정점이 연결만 되어 있다면 다른 연결된 모든 정점에 도달할 수 있기 때문에 의미가 없습니다. 유향 그래프에서 강하게 연결된 최대 부분 그래프를 강한 연결 요소라고 합니다. 강한 연결 요소를 하나의 정점으로 만드는 것을 응축이라고 하고, 그렇게 만들어진 유향 그래프는 유향 비순환 그래프(DAG; Directed Acyclic .. [355] 파이썬 딕셔너리(dictionary) 자료형 1. 딕셔너리 자료형과 해시 테이블 파이썬의 키/값 구조로 이루어진 자료형입니다. 내부적으로 해시 테이블로 구현되어 있습니다. 리스트 자료형은 인덱스(숫자)만을 사용하여 값을 찾을 수 있지만, 딕셔너리는 해시할 수 있는 모든 객체를 키로 사용할 수 있습니다. 불변 객체는 해시할 수 있으며(hashable), 따라서 문자, 숫자, 집합까지 모두 키로 사용 가능합니다. 해시 테이블의 장점은 조회가 \(O(1)\)에 가능하다는 점입니다. 따라서 딕셔너리의 주요 연산 시간 복잡도는 \(O(1)\)에 처리가 가능하다는 장점이 있습니다. 연산 시간 복잡도 결과 len(Dict) \(O(1)\) 요소의 개수 반환 Dict[key] 또는 Dict.get(key) \(O(1)\) 키에 해당하는 값 반환 Dict[key].. [335] AND, OR, XOR 누적 계산 비트 연산 AND(\(\wedge\)), OR(\(\vee\)), XOR(\(\bigoplus\))과 관련하여 여러 성질을 알아보고, 누적 연산을 효율적으로 하는 방법을 알아봅시다. 비트 연산에 대한 자세한 내용은 다루지 않으므로, 비트 연산의 내용은 아래 위키백과를 참고해주세요. https://ko.wikipedia.org/wiki/비트_연산 비트 연산 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 비트 연산(bitwise operation)은 한 개 혹은 두 개의 이진수에 대해 비트 단위로 적용되는 연산이다. NOT 연산은 각 자릿수의 값을 반대로 바꾸는 연산이다. NOT 0111 = 10 ko.wikipedia.org 1. 비트 연산의 당연하지만 재미있는 성질 비트 연산은 이.. [320] 희소 배열(Sparse Table) 종이 1000장의 두께를 만들고 싶다면 어떻게 할까요? 단순하게 종이 1000장을 쌓으면 됩니다. 하지만 종이 1000장을 쌓는 것(\(1 \times 1000\))보다 더 빠르고 편한 방법이 있습니다. 바로 종이 1장을 10번 접는 것(\(2^{10}\))입니다. 1. 희소 배열(Sparse Table) 위와 같은 갈림길이 없는 순환 그래프가 있습니다. 어떤 정점에서 1000번 이동하면 어떤 정점에 도착할까요? 종이 접기 문제처럼 1000번을 이동하는 대신 2의 제곱수로 건너 뛰며 빠르게 확인할 수 있는 방법이 있습니다. 각 정점에서 간선을 통해 1번 이동하여 도착하는 다음 정점을 표로 나타내면 다음과 같습니다. 출발 정점 1 2 3 4 5 6 7 1회 이동 5 7 7 3 4 3 1 한 번 더 작성하면.. 이전 1 2 3 4 5 6 7 다음
