본문 바로가기

Computer Science

 (46)
[Lecture 16] Weighted Graph / 가중 그래프 #Weighted Graph 수학의 그래프 이론 분야에서, 그래프 번호매김(graph labeling)은 전통적을 정수로 표현되는 라벨을 그래프의 모서리나 꼭짓점, 또는 둘 다에다 붙이는 것이다. 공식으로 표현하면 그래프 G = (V, E)가 주어졌을 때, 꼭짓점 번호매김(vertex labeling)은 V에서 라벨의 집합으로 가는 함수이다. 이런 함수가 정의된 그래프는 꼭짓점-라벨 그래프(vertex-labeled graph)라고 부른다. 유사하게, 모서리 번호매김(edge labeling)은 E에서 라벨의 집합으로 가는 함수이다. 이 경우에, 그래프는 모서리-라벨 그래프(edge-labeled graph)라고 부른다. 모서리 라벨이 순서 집합(예, 실수)의 원소라면, 이 그래프는 가중 그래프(weig..
[Lecture 15] Graph Traversal / 그래프 운행법 #Graph Traversal 그래프 운행법, 그래프 트래버설 또는 그래프 순회란 그래프를 구성하는 모든 정점들을 체계적으로 방문하는 방법이다. 큐를 이용한 넓이 우선 탐색 방법과 스택을 이용한 깊이 우선 탐색 방법이 있다. 또 부모 노드를 먼저 검사하고 왼쪽 노드에서 오른쪽 노드의 순으로 방문하는 방법인 전위 운행법과 왼쪽 노드, 부모 노드, 오른쪽 노드의 순으로 방문하는 방법인 중위 운행법, 왼쪽 노드에서 오른쪽 노드의 순으로 방문한 후 부모 노드를 검사하는 방법인 후위 운행법이 있다. [네이버 지식백과] 그래프 운행법 [graph traversal] 일부 알고리즘은 그래프의 모든 정점을 정확히 한 번 방문해야 한다.정점이 방문되는 순서는 중요할 수 있으며 특정 알고리즘에 따라 달라질 수 있다. 이 ..
[Lecture 14] Graph / 그래프 #Graph 그래프는 꼭짓점과 변의 집합을 이루는 순서쌍을 의미하며, 관계를 간선과 정점으로 표현한 구조이다. 간선으로 연결한 두 정점을 '인접(Adjacent)해 있다' 혹은 '이웃 관계'라고 표현하며, 그래프에서 정점들이 연결된 다양한 노선을 경로라고 표현한다. 쉽게 말해 데이터의 원소에 해당하는 정점(Vertex)과 정점간의 관계를 간선(Edge)으로 연결하여 표현한 형태의 자료구조이다. 일반적으로 정점은 원으로 표현하고 변은 화살표나 선분으로 표현한다. 변을 화살표로 나타내는 경우에는 해당 방향으로만 이동할 수 있으며, 이러한 그래프를 유향 그래프(Directed graph)라고 말한다. 반대로 선분으로 표현되는 경우에는 양방향 모두 이동이 가능하며, 이러한 그래프를 무향 그래프(Undirecte..
[Lecture 13] B-Tree / B-트리 #B-Tree Intro 전산학에서 B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 쉽게 말해 다방향 탐색 트리이다. 대용량의 파일을 효율적으로 검색하고 갱신하기 위해 고안된 트리 형태의 자료 구조이다. 방대한 양의 저장된 자료를 검색해야 하는 경우 검색어와 자료를 일일이 비교하는 방식은 비효율적이다. B-트리는 자료를 정렬된 상태로 보관하고, 삽입 및 삭제를 대수 시간으로 할 수 있다. 대부분의 이진 트리는 항목이 삽입될 때 하향식으로 구성되는 데 반해, B-트리는 일반적으로 상향식으로 구성된다. n개의 키 (s1,s2,s3...,sn)가 있는 한 노드를 ..
[Lecture 7] 점근(asymptotic) 표기법/ Big-O 표기법 #Big-O 표기법 점근 표기법은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 알고리즘의 복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰인다. 대표적으로 다음의 세 가지 표기법이 있다. 대문자 O 표기법 알고리즘의 상한 및 상한은 필요한 시간의 가장 많은 양(최악의 경우 성능)으로 정의된다. 빅 오 표기법은 점근적 상한을 설명하는 데 사용된다. 수학적으로, 만약 f(n)가 알고리즘의 실행 시간을 설명한다면, f(n)는 O(g(n)이고, 양의 상수 C가 존재하고 n이 존재한다면, 모든 n >= n0에 대해 0 0과 N > 0이 존재한다면 f(n)는 Ω(g(n)이라고 말한다. Big-Ω는 n의 충분히 큰 값에 대해 함수의 성장률에 대한 하한을 나타낸다. #Bi..
[Lecture 6] Algorithm Analysis / 알고리즘 분석 #알고리즘 알고리즘(algorithm)은 특정 문제 또는 문제의 모음을 해결하기 위해 수행할 일련의 작업을 지정하는 유한한 명령 집합이다. 간단히 말해 주어진 문제를 논리적으로 해결하기 위해 필요한 절차, 방법, 명령어들을 모아놓은 것이다. 넓게는 사람 손으로 해결하는 것, 컴퓨터로 해결하는 것, 수학적인 것, 비수학적인 것을 모두 포함한다. 알고리즘은 다음과 같은 속성을 가져야 한다: 유한성 / finiteness: 알고리즘은 한정된 수의 명령이 실행된 후에 완료되어야 한다. 명료성 / unambiguity: 각 단계는 하나의 해석만 가지고 명확하게 정의되어야 한다 수열의 정의 / definition of sequence: 각 단계에는 고유하게 정의된 선행과 후속 단계가 있어야 한다. 첫 번째 단계(시..
[Lecture 4] Hash Function / 해시 함수 #Hash Function 하나의 문자열을 보다 빨리 찾을 수 있도록 주소에 직접 접근할 수 있는 짧은 길이의 값이나 키로 변환하는 알고리즘을 수식으로 표현한 것. 즉, 해싱 함수(hashing function) h(k)는 어떤 키 k에 대한 테이블 주소(table address)를 계산하기 위한 방법으로 주어진 키 값으로부터 레코드가 저장되어 있는 주소를 산출해 낼 수 있는 수식을 말한다. 문자열을 찾을 때 문자를 하나하나 비교하며 찾는 것보다는 문자열에서 해시 키를 계산하고 그 키에 해당하는 장소에 문자열을 저장해 둔다면, 찾을 때는 한 번의 해시 키 계산만으로도 쉽게 찾을 수 있게 된다. 또한 해쉬 함수는 임의의 길이의 입력 메시지를 고정된 길이의 출력 값으로 압축시킨다. 이 때문에 데이터의 무결성..
[Lecture 1] BST / Binary Search Tree / 이진탐색트리 #Binary Trees Binary Tree, 이진트리란 컴퓨터 과학에서 사용되는 데이터 구조의 하나로, 뿌리가 있는 나무 구조(트리, tree)에서 어떤 노드의 자식의 수가 최대 2개를 넘지 않는 트리를 말한다. 이진 트리는 비어 있거나 루트의 왼쪽 하위 트리와 오른쪽 하위 트리라고 불리는 두 개의 이진 트리와 함께 루트라고 불리는 노드로 구성되어 있다 한 노드의 자식 노드가 최대 2개(왼쪽, 오른쪽)인 자료구조로, 이진 탐색 트리(binary search tree) 및 힙(heap) 등을 구현하기 위해 사용된다. 이진 트리에서의 방향 간선, 루트 노드, 단말 노드, 각 노드의 깊이, 레벨, 트리의 높이, 노드의 차수 등에 대한 정의는 일반적인 트리에 대한 용어 정의와 동일하다. 하지만 이진 트리는 ..

티스토리툴바