3. 알고리즘 공부 (60) 썸네일형 리스트형 [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.. [248] 비트마스크 + 동적 프로그래밍(DP) 1. 비트마스크 비트마스크(BitMask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말합니다. 이진수는 0 또는 1을 이용하므로 하나의 비트(bit)가 표현할 수 있는 경우는 두 가지입니다. 보통 어떤 비트가 1이면 "켜져 있다"라고 말하며, 0이면 "꺼져 있다"라고 말합니다. https://ko.wikipedia.org/wiki/마스크_(컴퓨팅) 마스크 (컴퓨팅) - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서 마스크(mask) 또는 비트마스크(bitmask)는 특히 비트 필드에서 비트 연산에 사용되는 데이터이다. 마스크를 사용하면 바이트, 니블, 워드 등의 다 ko.wikipedia.org 가. 비트 크기 .. [168] 독립 집합(트리의 최대 독립 집합 구하기) 1. 독립 집합(Independent set) 어떤 그래프에서 서로 인접하지 않는 정점들의 집합을 그 그래프의 독립 집합(Independent set)이라고 합니다. 다시 말하면 독립 집합의 정점들은 해당 그래프에서 어떤 간선으로도 연결되어 있지 않습니다. 즉, 두 끝 모두에 독립 집합의 정점이 위치하는 간선은 존재하지 않습니다. 그렇다면 간선을 두 종류로 나눌 수 있는데, 하나는 한 쪽 끝만 독립 집합의 정점인 간선이고, 다른 하나는 두 끝 다 독립 집합의 정점이 아닌 간선으로 나눌 수 있습니다. 위 그림의 파란색 정점은 독립 집합을 나타내는데, 어떠한 간선도 두 파란색 점을 연결하지 않는 것을 볼 수 있습니다. https://ko.wikipedia.org/wiki/독립집합 독립집합 - 위키백과, 우.. [163] 최소신장트리와 프림 알고리즘, 크루스칼 알고리즘 1. 그래프(graph)그래프는 정점(vertex)과 간선(edge)을 가지는 자료구조입니다.정점과 간선을 수학에서는 꼭짓점과 변으로 부릅니다.https://ko.wikipedia.org/wiki/그래프_(자료_구조) 그래프 (자료 구조) - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 3개의 꼭짓점과 3개의 변으로 이루어진 그래프. 그래프(graph)는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는ko.wikipedia.org2. 신장 부분 그래프(spanning subgraph)어떤 그래프의 모든 정점을 포함하는 부분 그래프를 그 그래프의 신장 부분 그래프(spanning subgraph)라고 합니다.https.. 이전 1 ··· 3 4 5 6 7 8 다음
