본문 바로가기

전체 글

 (86)
[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) 등을 구현하기 위해 사용된다. 이진 트리에서의 방향 간선, 루트 노드, 단말 노드, 각 노드의 깊이, 레벨, 트리의 높이, 노드의 차수 등에 대한 정의는 일반적인 트리에 대한 용어 정의와 동일하다. 하지만 이진 트리는 ..
[Lecture 0 - II] Java Equals() & Generics #equals() in the Class Object Object 클래스는 두 개체가 동일한 개체인 경우에만 true를 반환하는 public equals() 메서드를 구현한다 x.equals(y) == true iff x and y are (references to) the same object 일부 하위 클래스의 경우, 특히 equality comparison의 개념이 실질적으로 의미가 없는 유형에 적합하다 #Identity vs Equality identity: 동일한 것의 관계. x와 y가 동일한 객체인 경우에만 x는 y와 동일하다. Java에서는 == 연산자에 의해 테스트된다. equality: 동일한 값를 갖는 관계 x는 x와 y가 어떤 유용한 의미에서 동등한 함량을 갖는 경우에만 y와 같다. ..
[Lecture 0 - I] Java File I/O #File Class 파일 및 디렉터리 경로 이름의 추상 표현 File(String pathname) 유용한 method들: boolean exists() boolean createNewFile() boolean delete() long length() 텍스트 파일의 데이터 읽기/쓰기에 유용한 클래스와 방법을 알아보자. 텍스트 파일은 모든 데이터 값이 일련의 문자(ASCII 또는 유니코드와 같은 일반적인 체계에서 인코딩됨)로 표현되는 파일이다. 이진 파일은 모든 데이터 값이 기계 메모리에서 이를 나타내는 데 사용되는 동일한 비트 패턴으로 표현되는 파일이다. #FileWriter 클래스 텍스트 파일에 순차적으로 쓰기 위해서는 일반적으로 FileWriter 클래스로 충분하다 FileWriter(String ..

티스토리툴바