3. 알고리즘 공부 (47) 썸네일형 리스트형 [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 한 번 더 작성하면.. [303] 두 가지 위상정렬(Topological Sorting) 알고리즘 1. 위상정렬이란? 위상정렬은 유향 그래프(digraph; directed graph)에서 간선(edge)의 방향을 거스르지 않도록 정점(vertex)을 나열하는 것을 의미합니다. https://ko.wikipedia.org/wiki/위상정렬 위상정렬 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예 ko.wikipedia.org 예를 들어 위와 같은 유향 그래프가 있을 때, 다음과 같이 정점을 [1, 2, 6, 3, 4, 5, 7]로 정렬하면 간선의 방향을 거스르지 않으면서 정렬됩니다. 이는 위상 정.. [286] KMP 알고리즘(Knuth-Morris-Pratt algorithm) 1. KMP 알고리즘이란? 문자열 검색 알고리즘 중에 하나로 주어진 문자열에서 특정 문자를 모두 찾아내는 알고리즘입니다. 쉽게 생각해서 우리가 흔히 사용하는 Ctrl + F 를 수행할 수 있는 알고리즘이라고 생각하면 됩니다. 이 알고리즘의 이름은, 이 알고리즘을 고안한 세 명의 컴퓨터 과학자인 커누스(Donald Ervin Knuth), 모리스(James Hirram Morris), 프랫(Vaughan Ronald Pratt)의 앞글자를 따서 이름 붙었습니다. https://ko.wikipedia.org/wiki/커누스-모리스-프랫_알고리즘 커누스-모리스-프랫 알고리즘 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서 커누스-모리스-프랫 알고리즘(Knuth–Morris.. 이전 1 2 3 4 5 6 다음
