본문 바로가기

Computer Science/Data Structures & Algorithms

 (13)
[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 ..

티스토리툴바