알고리즘
-
알고리즘...102일지 2022. 1. 14. 13:20
그래프 기본 개념 현상이나 사물을 정점과 간선으로 표현하는 것을 말한다. 정점(Vertex) 대상이나 개체 간선(Edge) 대상이나 개체 간의 관계 그래프는 간선이 상호 통행이 가능한지, 일방통행만 가능한지에 따라 유향 그래프와 무향 그래프로 나뉜다. 유향 그래프 정해진 방향으로만 이동이 가능한 그래프, 화살표로 간선을 표현한다. 무향 그래프 쌍방으로 이동이 가능한 그래프, 실선으로 간선을 표현한다. 또, 각각의 정점이 가지는 관계의 정도를 간선에 가중치로 표현하기도 한다. 더보기 참고문헌 한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘
-
동적 프로그래밍 개념프로그래밍 기초/알고리즘 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..
-
알고리즘...101일지 2022. 1. 11. 13:51
트리를 이용한 집합의 처리 연결 리스트를 이용한 집합의 처리보다 효율적인 방식으로 각각의 집합을 트리로 표현하는 방법이다. 기존의 트리와는 달리 자식 노드가 부모 노드를 가리키는 방식으로 표현된다. 이러한 방식을 사용하는 경우 두 집합을 합칠 때 단순하게 합치려는 노드의 루트가 기존 집합의 루트를 가리키도록 하면 된다. 연산의 효율성을 높이는 방법 - 랭크를 이용한 Union 각 노드에 자신의 서브 트리의 높이를 랭크(Rank)라는 이름으로 저장하고 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 집합에 붙인다. - 경로 압축 FindSet 진행 시 중간에 만나는 모든 노드에 대해 루트를 직접 가리키도록 바꾸어 추후 FindSet을 할 때 경로의 길이를 줄이는 방법이다. 더보기 참고문헌 한빛아카데미.문병..
-
알고리즘...100일지 2022. 1. 10. 14:45
연결 리스트를 이용한 집합 처리 집합을 표현하기 위해 각 노드는 대표 노드(집합의 최초 노드)를 가리키는 포인터와, 다음 원소를 가리키는 포인터, 값을 나타내는 변수를 가진다. 또, 집합의 연산을 쉽게 하기 위해 각 노드는 tail 노드를 가리키는 포인터를 따로 가지고 있게 된다. 이 집합을 사용하기 위해서는 다음의 함수가 필요하다. MakeSet(x) 원소 x로 이루어진 집합을 만든다. FindSet(x) 원소 x를 가지는 집합을 찾는다. Union(x, y) 원소 x를 가진 집합과 원소 y를 가지는 집합을 하나로 합친다. 수행 시간은 MakeSet과 FindSet은 상수 시간이 걸리지만 Union은 집합의 크기에 따라 상수 시간을 벗어날 수 있다. 이 수행 시간을 최소화하기 위해 큰 집합에 작은 집합..
-
해시 테이블 구현 및 테스트프로그래밍 기초/알고리즘 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..
-
알고리즘...99일지 2022. 1. 6. 17:54
해시 테이블 충돌 해결 더블 해싱 구현 충돌 해결 방법 중 개방주소 방법의 더블 해싱을 구현한다. 다른 부분은 상위 클래스에서 구현이 되어있으므로 충돌 해결 방법만 추가로 구현한다. int HashTable_OpenAddressing_DoubleHashing::GetProperHashIndex(int idx, int data) { int jumpValue{ HashTable::GetHashIndex(data, HashFunction::Multiplication) }; if (CurrentHashFunction() == HashFunction::Multiplication) { jumpValue = HashTable::GetHashIndex(data, HashFunction::Division); } int ..