Jinlib

그래프 탐색 문제 그래프 탐색 문제란? 어떤 한 그래프와 해당 그래프의 시작 정점이 주어졌을때, 시작점에서 간선(Edge, E)을 타고 이동할 수 있는 정점(Vertex, V)들을 모두 찾아야 하는 문제를 의미합니다. 이 문제를 해결하는 그래프 탐색 알고리즘에는 흔히 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이 있습니다. 이에 대해서 알아보도록 합시다. 두 알고리즘의 공통점은 그래프 탐색 문제에 대한 해답을 올바르게 찾는다는 점이다. 각 알고리즘의 특성을 살펴보자. 1. 깊이우선탐색(Depth-First Search, DFS) DFS는 깊이 우선 탐색이라고 불리며 그 이유는 그래프의 시작점에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하기 때문입니다. 알고리즘 개요는 시작점-> 시작..

세그먼트 트리 또는 인덱스 트리1. 정의위와같이 각 노드에는 구간에 대한 정보가 저장이 되어있는 트리를 의미한다.일반적으로 구간의 합 또는 곱, 구간의 최대값 또는 최솟값을 의미합니다. 예)배열의 데이터 수 : 8개배열의 데이터 A[8] = {1,2,3,4,5,6,7,8}목적 : 구간에 대한 합 세그먼트 이론시 높이 3인 트리가 만들어지며 오른쪽 위에 숫자만큼 각 구간에 대한 정보를 담고 있다. 위와 같이 각 노드는 자식에 대한 합을 포함 하고 있다. 배열은 0부터 인덱스가 시작하므로,A[3] ~ A[6]까지의 합을 구한다고 가정할때, 아래와 같이 주황색 부분의 합만 구하면 된다. 즉, 4+11+7 = 22로 부분에 대한 합을 쉽게 구할 수 있습니다. 위와같이 수행하면 부분의 합에 대한 부분을높이가 O(..

이번 글에서는 알고리즘의 계산복잡도 함수가 재귀식(Recurrence relation) 내지 점화식 형태로 표현되는 경우를 살펴보도록 하겠습니다. 재귀식 또는 점화식이란 피보나치 수열(다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 되는 수열)처럼 수열의 항 사이에서 성립하는 관계식을 말합니다. 이로부터 데이터 수 nn에 대해 닫힌 형태(closed-form expression)의 정확한 계산복잡도 함수를 찾는 것이 이 글의 목표입니다. (복잡도의 기준은 알고리즘이 필요로 하는 시간과 메모리 등 자원인데 전자를 ‘시간복잡도’, 후자를 ‘공간복잡도’라 합니다) 이번 글 역시 고려대 김선욱 교수님 강의를 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.재귀식 형태로 표현된 시간복잡성알고리즘의 계산복잡도..

알고리즘의 가장 중요한 기본 성질은 "어떤 주어진 문제의 해결 능력"이다. 알고리즘의 성능을 분석하기 위한 기준으로 다음과 같은 요소들을 참고할 수 있다. 1. 정확성(correctness)2. 수행량(amount of work done) = 시간 복잡도(time complexity)3. 사용공간(amount of space used) = 공간 복잡도(space complexity)4. 단순성(simplicity)5. 최적성(optimality) 1. 정확성정확성이란 "알고리즘이 타당한 입력이 주어졌을 때 유한 시간 내에 계산이 수행되어 올바른 결과를 출력하는 것"이라고 정의할 수 있다.정확성을 증명하는 방법으로는 수학적 귀납법이다. 특히 수학적 귀납법은 알고리즘 내의 루프가 의도한대로 수행 되는지를 증..

안녕하세요정렬 알고리즘1 글을 써놓고 2는 바빠서 못썼네요ㅎㅎ..오늘은 퀵정렬만 정리해보려고 합니다. 퀵정렬은 개념을 아예 모르시는 분들이 보면 이해하기가 처음엔 힘들어요.그래서 그런분들을 위해 퀵정렬만!! 정리해보려고해요.하하 정렬 알고리즘 - Quick Sort 퀵정렬!!자, 이름부터 퀵(Quick)이네요.퀵은 다들 아시는 것처럼뜻은 ① (동작·활동 등이) (재)빠른 ②(속도상으로·걸리는 시간이 짧아서) (재)빠른 ③(재)빨리, 신속히 입니다. 이름부터 뭔가 빠른 정렬 알고리즘 같죠? 실제로다른 정렬 방법에 비해 일반적으로 가장 빠른 알고리즘으로 알려져 있습니다. 하지만!!대상 데이터의 특징이나 데이터 크기에 따라 반드시 위 말이 맞는 것은 아닙니다. 실제로 최악의 경우에 시간복잡도가 n^2기도 하구..

Quick Sort 분할할 축값을 정하는 방법의 개선Random vs Median-of-Three 삽입정렬을 소구간에 적용하는 방법 Partition을 사용해서 selection 문제를 해결할 수 있음 1. Divide and conquer (partition) algorithmpivot왼쪽: pivot(축) value 보다 작은 값오른쪽: 큰 값partitiontemplate int partition(TYPE a[], int n){TYPE v, t;int i, j; v = a[n - 1];i = -1;j = n - 1; while (true) {while (a[++i] v); // 우측부터 v 보다 작은 값..