프로그래밍 기초/알고리즘
-
그래프 알고리즘프로그래밍 기초/알고리즘 2022. 1. 21. 13:33
동적 프로그래밍 그래프 기본 개념 현상이나 사물을 정점과 간선으로 표현하는 것을 말한다. 정점(Vertex) 대상이나 개체 간선(Edge) 대상이나 개체 간의 관계 그래프는 간선이 상호 통행이 가능한지, 일방통행만 가능한지에 따라 유향 그래프와 무향 그래프로 나뉜다. 유향 그래프 정해진 방향으로만 이동이 가능한 그래프, 화살표로 간선을 표현한다. 무향 그래프 쌍방으로 이동이 가능한 그래프, 실선으로 간선을 표현한다. 또, 각각의 정점이 가지는 관계의 정도를 간선에 가중치로 표현하기도 한다. 인접 행렬을 이용한 그래프의 표현 각 행, 열을 순서대로 정점을 나타내고 각각의 간선은 해당하는 행, 열의 위치에 값을 할당하는 방식으로 그래프를 표현하여 이해하기 쉽고 간선의 존재 여부를 곧바로 파악할 수 있다. 가..
-
동적 프로그래밍 개념프로그래밍 기초/알고리즘 2022. 1. 12. 10:45
동적 프로그래밍 동적 프로그래밍 개념 큰 문제의 해답에 작은 문제의 해답이 포함되는 알고리즘을 재귀적으로 처리할 때 나타나는 비효율을 제거하기 위한 프로그래밍 방식을 동적 프로그래밍이라고 한다. 가령 피보나치수열의 경우 다음과 같은 식으로 나타난다. f(n) = f(n-1) + f(n-2) f(1) = f(2) = 1 이를 재귀적으로 해결하기 위해서는 기존에 구했던 해답을 다시 구하는 등의 반복이 일어난다. 이러한 문제를 해결하기 위해 부분 결과를 저장하면서 해를 구하는 것이 동적 프로그래밍의 핵심이다. 가령 위에서 설명한 피보나치수열의 문제를 동적 프로그래밍을 적용해 해결한다면 다음과 같이 풀 수 있다. 피보나치수열 알고리즘 fib(n) { if (f[n] ≠ 0) then return f[n]; el..
-
해시 테이블 구현 및 테스트프로그래밍 기초/알고리즘 2022. 1. 7. 17:51
해시 테이블 구현 STL의 vector를 이용하여 해시 테이블을 구현한다. 해시 테이블 기본 클래스 해시 테이블 처리 중 충돌 처리에 따라 함수를 나누기 위해 기본 기능을 가진 클래스를 구현한다. HashTable.h #pragma once #include "../Common.h" #include #include using std::string; /// /// 해시 테이블에서 사용할 해시 함수 /// enum class HashFunction { Division, Multiplication, }; /// /// 해시 테이블의 구성 요소 테스트를 위한 베이스 클래스 /// class HashTable { public: HashTable(HashFunction hashFunction = HashFunctio..
-
해시 테이블 알고리즘프로그래밍 기초/알고리즘 2021. 12. 22. 14:42
해시 테이블 해시 테이블은 원소의 위치가 값에 의해 계산되어 결정되는 자료구조로 해시 테이블의 값을 정하는 건 해시 함수인데, 이 함수를 통해 각각의 원소의 자리를 상수 시간에 계산할 수 있다. 해시 테이블에 원소가 차 있는 비율을 적재율이라 하며, 테이블의 크기가 m이고 테이블에 저장된 원소의 개수가 n이면 적재율은 n/m이 된다. ※ 테이블의 모든 영역에 값을 적절하게 분배하지 못하는 경우 성능이 떨어질 수 있다. 해시 함수 해시 함수는 해시 테이블에서 키 값을 테이블의 인덱스로 만들어 주는 함수로 다음의 성질을 가진다. 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다. 계산이 간단해야 한다. 만약 데이터가 어느 한 인덱스에 몰려서 저장되게 된다면 충돌이 자주 발생하여 성능에 악영향을 미치기 때..
-
R 트리 알고리즘프로그래밍 기초/알고리즘 2021. 12. 9. 16:48
R 트리 B 트리를 다차원 검색 트리로 확장한 트리 자료구조이다. R 트리에는 다음의 두 종류의 노드가 존재한다. 영역 노드 트리의 차원에 따라 노드가 가지는 공간을 표현하는 노드 키 노드 실제 키와 소속된 페이지 번호를 가지는 노드 R 트리는 다음의 성질을 갖는다. 루트를 제외한 모든 내부 노드는 └k/2┘ ~ k 개의 영역을 갖는다. 모든 리프 노드는 같은 깊이를 가진다. 모든 레코드는 리프 노드에서만 가리킨다. R 트리의 표현 R 트리는 KDB 트리와 달리 키를 포함하는 최소 영역에만 노드가 존재한다. 아래와 키가 존재할 때 R트리의 표현은 다음과 같다. 이름 key1 key2 A 8 100 B 4 10 C 6 35 D 1 10 E 6 60 F 5 45 G 7 85 H 3 20 I 10 70 J 2..
-
KDB 트리 알고리즘프로그래밍 기초/알고리즘 2021. 11. 30. 14:07
KDB 트리 B 트리를 다차원 검색 트리로 확장한 트리 자료구조이다. KDB 트리는 노드의 키를 통해 분기하는 게 아니라 전체 영역을 쪼개가며 진행하게 된다. KDB 트리에는 다음의 두 종류의 노드가 존재한다. 영역 노드 트리의 차원에 따라 노드가 가지는 공간을 표현하는 노드 키 노드 실제 키와 소속된 페이지 번호를 가지는 노드 이때, k 차원의 키를 사용하는 영역 노드는 다음과 같이 표현된다. (, , ... , ) ※ KDB 트리의 모든 내부 노드는 영역 노드이며, 모든 리프 노드는 키 노드이다. KD 트리에서의 검색 KD 트리의 검색은 다음의 순서를 따른다. 루트 노드에서부터 검색하려는 키가 포함된 영역을 가지는 영역 노드를 따라 진행한다. 리프 노드에 도달한 경우 리프 노드에 검색하려는 키가 존재..
-
KD 트리 알고리즘프로그래밍 기초/알고리즘 2021. 11. 18. 18:51
KD 트리 이진 검색 트리를 다차원 검색 트리로 확장한 트리 자료구조이다. KD 트리는 같은 레벨의 노드는 동등한 위치의 필드를 사용하여 분기를 진행하며 k 개의 필드를 가지는 KD 트리에서 레벨 k에 도달한 경우 다시 0 번째 필드를 사용하여 분기를 진행한다. ※ 다차원 검색 트리는 노드의 키가 하나의 필드가 아닌 여러 개의 필드로 이루어진 검색 트리를 말한다. KD 트리에서의 검색 기본적으로 이진 검색 트리와 동일한 방식으로 탐색을 진행하나 KD 트리는 각 레벨 별로 다른 필드를 사용하여 검색을 진행하는 점이 다르다. 레벨 0 에서는 첫 번째 필드를 사용하여 분기하고 레벨 1에서는 두 번째 필드를 사용하여 분기를 진행한다. 이렇게 진행하다 레벨 k 에서는 다시 첫 번째 필드를 사용하는 방식으로 검색을..
-
B 트리 구현 및 테스트프로그래밍 기초/알고리즘 2021. 11. 11. 19:58
B 트리 이진 검색 트리를 기반으로 노드에 Balance Factor(이후 BF)를 추가하여 BF의 상태에 따라 트리의 균형을 유지한다. B 트리 개요 검색 트리가 방대하면 검색 트리를 메모리에 모두 올려두고 사용할 수 없게 되어 검색 트리가 디스크에 있는 상태에서 작업을 해야 한다. 이런 경우에 CPU 작업 효율성보다 디스크 접근 횟수가 효율을 좌우하게 된다. B 트리는 디스크 환경에서 사용하기 적합한 외부 다진 검색 트리로 B 트리의 한 노드에는 최대 k개까지의 키가 크기 순으로 저장되어 있다. ※ 검색 트리가 디스크에 있는 상태로 사용되면 이를 외부 검색 트리라고 한다. B 트리에 k개의 키가 존재하는 경우 k + 1 개의 자식을 가지게 된다. 이때, 주어진 키를 key 0 ~ key k - 1로 ..