공부 정리

* 에라토스테네스의 체 고대 그리스의 수학자인 에라토스테네스가 발견한 소수(1과 자기자신으로만 나누어지는 수)를 찾는 방법이다. 내용은 다음과 같다. - 알고리즘 1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 2. 2는 소수이므로 오른쪽에 2를 쓴다. 3. 자기 자신을 제외한 2의 배수를 모두 지운다. 4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. 5. 자기 자신을 제외한 3의 배수를 모두 지운다. 6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. 7. 자기 자신을 제외한 5의 배수를 모두 지운다. 8. 위 과정을 계속 반복하면 원하는 구간의 모든 소수가 남는다. 이 때, 100까지의 소수를 구할 때 어디까지 위의 방법을 반복해야 할까? 예를 들어서 17의 배..

* Hash? 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 특징: 뭘 넣든 비슷한 길이의 알 수 없는 난수가 결과로 출력된다. 글자가 한 글자만 바뀌어도 완전히 다른 결과가 출력된다. 출력값으로 임의의 값을 예측할 수 없다. 같은 내용을 입력 값으로 주면 결과값은 언제나 같다. 이를 이용해 해시 테이블이라는 자료구조를 사용할 수 있으며 해시 값 자체를 index로 사용한다. 따라서 시간 복잡도는 O(1)로 매우 빠른 데이터 검색이 가능하다. * Hashing 과정 키(Key) ----> 해시 함수(hash function) ----> 해시값(hash value) [이름] [해싱과정] [index(hash value) : data] * 키(key) : 매핑 전 원래 데이터의 값 * 해시..

* Divide and Conquer Algorithm (분할 정복)? 해결할 수 없는 문제를 더 이상 나눌 수 없는 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다. Quicksort, Merge sort, Closest Pair of Points 등의 알고리즘이 이 분할 정복 알고리즘에 해당한다. 분할 정복 알고리즘은 3 부분으로 나뉠 수 있다. 나누기 (Divide): 문제를 더 작은 문제로 나눈다. 정복 (Conquer): 하위 문제가 해결될 때까지 재귀적으로 호출하여 하위 문제를 해결한다. 결합(Combine): 하위 문제가 해결되었기 때문에 문제 해결을 할 수 있다. 보통 재귀적으로 함수를 호출하여 문제를 해결하지만, 재귀적으로 함수 호출이 잦게 되면 함수 호출 스택 오버헤드 때문에..

* Binary Search Algorithm(이진 탐색 알고리즘) 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 이진 탐색 알고리즘을 사용하기 위해선 반드시 오름차순으로 정렬이 되어 있는 리스트라는 전제 조건이 필요하다. 1. 중앙 원소와 찾고자 하는 X를 비교한다. 2-1. 만약 중앙 원소가 찾고자 하는 원소와 같다면 해당 원소 리턴 2-2. X가 중앙 원소보다 크다면 배열의 우측을 대상으로 탐색 재실행, 작다면 좌측을 대상으로 탐색 재실행 * 시간 복잡도 탐색하고자 하는 원소가 N개라면, 첫 시도에는 N개의 원소를, 두번째 시도에는 N/2개의 원소를, 세번째 시도에는 N/4의 원소를 탐색할 것이다. 자료의 갯수가 N개라면 시행 횟수는 밑이 2인 log2N이다. 따라서 시간복잡..

* PRIM 정의 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식. 그리디 알고리즘이다. 임의의 정점을 하나 선택해서 시작한다. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택한다. 모든 정점이 선택될 때 까지 1번과 2번의 과정을 반복한다. 서로소인 2개의 집합(2 disjoint-sets) 정보를 유지한다. 트리 정점들(tree vertices) - MST를 만들기 위해 선택된 정점들 비트리 정점들(non-tree vertices) - 선택되지 않은 정점들 프림 알고리즘은 싸이클링 여부를 체크할 필요가 없다. 왜냐면 연결되지 않은 정점들만 찾으므로 * PRIM 적용 예 * PRIM Algorithm Code for Java import ja..

먼저 알아야 하는 것 : MST, Union-Find Union-Find Algorithm 이걸 카테고리를 알고리즘으로 해야하는지... 자료구조로 해야하는지... * Union-Find (= disjoint-set / merge-find) 알고리즘 Union-Find 알고리즘은 2개의 기능을 가지고 있는 알고리즘이다. 1. Find : 어느 부.. superbono-2020.tistory.com * Kruskal 정의 간선을 하나씩 선택해서 MST를 찾는 알고리즘. 그리디 알고리즘의 한 종류이다. 간선 리스트를 작성한다. 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬한다. 가중치가 가장 낮은 간선부터 선택(두 정점을 해당 가중치의 비용으로 연결한다)하면서 트리를 증가시킨다. -> 사이클이 존재하면 ..

* 그래프에서 최소 비용 문제 1. 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 -> 최소 신장 트리 2. 두 정점 사이의 최소 비용의 경로 찾기 * 신장 트리 - n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 * 최소 신장 트리(Minimum Spanning Tree) - 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리 * MST의 특징 사이클이 포함되어서는 안된다. 간선의 가중치의 합이 최소여야 한다. -> MST의 정의 * 현실에서의 MST 현실에서의 예를 들자면 케이블 회사가 클라이언트를 모두 연결하면서 케이블을 연결하는 비용을 최소로 하고 싶을 때 등이 있다. MST의 알고리즘에는 KRUSKAL과 P..

* 위상 정렬이란? 위상 정렬(topological sorting/ topological ordering)은 유향 그래프의 꼭지점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 하려면 반드시 그래프가 유향 비사이클 그래프(DAG : Directed Acyclic Graph)여야 한다. 그렇다면 만약 트리는 위상정렬을 할 수 있을까? 정답은 할 수 있다이다. 그러나 DAG가 트리라고 할 수 있는가? 정답은 아니다이다. 그러니까 DAG의 부분집합에 트리가 있는 것이라고 생각하면 된다. * Pseudocode L ← 정렬된 요소를 담은 빈 리스트 S ← 진입차수가 없는 노드들 while S is not empty do remove a node n from S add n to L for e..

이걸 카테고리를 알고리즘으로 해야하는지... 자료구조로 해야하는지... * Union-Find (= disjoint-set / merge-find) 알고리즘 Union-Find 알고리즘은 2개의 기능을 가지고 있는 알고리즘이다. 1. Find : 어느 부분집합에 특정한 원소가 있는지를 찾는다. 이것은 두 원소가 같은 부분집합에 포함되어 있는지 찾는 방식으로 사용할 수 있다. 2. Union : 두 부분집합을 하나의 부분집합으로 합친다. 한국말로는 서로소 집합/상호 배타 집합이라고도 불린다. - 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다. 교집합이 없다는 소리이다. - 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다. 구분할 수 있는 이 원소를 대표자(represen..

다익스트라 알고리즘: 시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다. 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사하다. 다익스트라 알고리즘의 pseudo 코드 진행 방식은 다음과 같다. 정점까지의 최소거리를 담는 D 배열을 만든다. 시작 정점의 D값은 0으로 둔다. 나머지 정점의 값들은 무한으로 둔다. 1- 선택: 현재 방문하지 않았고 최소 거리를 가지고 있는 정점을 선택한다. 2- 갱신: 현재 알고있는 정점의 최소 거리(D[value])와 현재 정점(D[현재]) + 현재 정점 ~ 해당 정점 (D[value])값을 더해서 작은 값으로 해당 정점까지의 거리(D[value])를 갱신해준다. 그리고 해당 정점을 방문했다고 체크해준다. // A Java pr..