inchori

그래프(Graph)는 G = (V, E)로 표현 가능하다 그래프는 V는 정점(Vertex)이고 E는 간선(Edge)로 구성되어 있다. 많은 알고리즘 문제들을 푸는 핵심은 그래프의 측면에서 생각하는 것 그래프의 특징 - 무방향(undirected) 그래프 vs 방향(directed) 그래프 G = (V, E)에서 (x, y) 간선이 (y, x)을 의미하면 무방향 그래프, 아니면 방향 그래프 - 가중(weighted) 그래프 vs 비가중(unweighted) 그래프 각 에지에 가중치라고 부르는 수치가 할당 두 정점 사이의 최단 경로를 구할 때 분명해진다 비가중 그래프에서 최단 경로는 최소 에지의 개수이며 BFS로 구할 수 있다. - 단순(simple) 그래프 vs 비단순(non-simple) 그래프 자기-루..

퀵 정렬(Quick Sort): 랜덤화에 의한 정렬 정렬을 하려는 n개의 원소들로부터 랜덤 원소 p를 피벗(pivot)으로 선택 퀵 정렬은 피벗 p를 제외한 n - 1개의 원소들을 두 부분으로 분리: - 왼쪽 부분에는 정렬된 순서에서 p보다 먼저 나오는 원소 - 오른쪽 부분에는 정렬된 순서에서 p보다 나중에 나오는 원소 피벗 p는 정렬이 끝난 순서에서 위치하여야 할 배열의 자리에 머무르게 된다. 분할된 후 한쪽 편에 있는 어떠한 원소도 마지막 정렬된 순서에서 다른 쪽으로 옮겨지지 않는다 -> 피벗의 양쪽으로 나뉘어져 있는 원소들은 서로 독립적으로 정렬 가능 (재귀 알고리즘 표현 가능) quick_sort(item_type s[], int l, int h) { int p; if ((h - 1) > 0) {..

정렬을 주목해야 하는 이유 - 정렬은 알고리즘을 설계하는 데에 있어서 기본적인 구성요소(Building Block) 역할을 한다. - 분할-정복, 자료구조 등과 같은 알고리즘 설계에 사용되는 흥미 있는 아이디어들이 정렬의 과정에서 나타난다. - 역사적으로 컴퓨터는 다른 어떤 것보다도 정렬에 많은 시간을 할애하였다. 정렬의 응용 - 탐색 : 모든 값들이 정렬된 경우 이진 탐색을 사용하면 O(logN) 시간에 검사할 수 있다. - 최근접쌍(Closest Pair) : N개의 숫자가 주어질 경우, 차이가 가장 작은 두 수를 어떻게 찾을까? 정렬을 사용하면 O(NlogN)의 시간을 가진다. - 원소 유일성 - 도수 분포 : N개의 원소가 주어졌을 때 어떤 원소가 가장 많은 빈도로 나타내는가? 원소들이 정렬되어 ..

/** 자료구조는 따로 다시 정리할 예정**/ 이진 탐색 트리(Binary Search Tree) 이진 탐색을 이용하기 위해서는 두 원소에 대한 빠른 접근 필요 루트 있는 이진 트리의 재귀적 정의 1. 아무것도 없음 2. 루트로 불리는 한 노드와 왼쪽 서브트리와 오른쪽 서브트리로 구성 이진 탐색 트리에서는 이진트리의 각 노드에 하나의 키의 라벨이 있다. 어떤 노드의 값이 x이면, - 왼쪽 서브트리에 있는 모든 노드들의 값은 x보다 작다. - 오른쪽 서브트리에 있는 모든 노드들의 값은 x보다 크다. 이진 탐색 트리의 구현 typedef struct tree { item_type item; struct tree *root; struct tree *left; struct tree *right; } 트리에서의 ..

/** 자료구조는 따로 다시 정리할 예정**/ 연속(Contiguous) 대 연결 자료구조(Linked Data Structures) 자료구조는 배열에 따라 구현 vs 포인터에 따라 구현 - 연속적 자료구조는 메모리의 연속된 한 구역으로 구성 배열, 행렬, 힙, 해시 테이블 등 - 연결된 자료구조는 포인터에 의해 뚜렷이 구분되는 메모리의 구역들로 구성 리스트, 트리, 그래프 등 배열(Array) 연속적으로 자료가 할당되는 가장 핵심적인 자료구조 각 원소들을 인덱스 혹은 주소로 그 위치를 찾을 수 있는 고정 크기(fixed-size) 구조 연속적으로 할당된 배열의 장법 - 주어진 인덱스로 상수 시간 접근 : 배열의 인덱스만 알면 데이터 요소 즉시 접근 가능 - 공간 효율성 - 메모리 지역성 : 배열은 매우..

2. 알고리즘 분석 알고리즘 분석의 가장 중요한 도구는 1) RAM 계산 모델 2) 최악의 경우(worst-case)의 점근적 분석(asymptotic analysis)이다. RAM 계산 모델 기계-독립적인 알고리즘 설계는 임의 접근 기계(Random Access Machine: RAM) 가상의 컴퓨터에 달려있다. 가상의 컴퓨터의 특징 - 각각의 단순 연산은 하나의 단계 동안에 실행 - 루프와 서브루틴은 단순 연산이 아니다. - 메모리 접근은 하나의 단계 동안에 이루어진다. 메모리 크기는 무한하여, 원하는 만큼의 메모리를 사용할 수 있다. 알고리즘을 언어와 기계에 독립적인 방식으로 이해하고 연구할 수 있다. 최선, 최악, 평균의 경우 복잡도 RAM 계산 모델을 사용하면 알고리즘이 몇 개의 단계를 실행하는..