본문 바로가기
반응형

분류 전체보기155

Algorithm - Heap sort (힙 정렬) Heap sort : Quick sort나 Merge sort 만큼 빠른 정렬 알고리즘. 고급 프로그래밍 기법으로 갈 수록 Heap의 개념이 자주 등장. Heap Tree Structure(힙 트리 자료구조)를 사용하는 정렬. Heap Tree Structure -> 최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전 이진트리 형태로 만들어진 자료구조 / Priority Queue를 위해 만들어진 자료구조. 최댓값 최소값을 쉽게 찾아낼 수 있음. 힙에는 최대 Heap과 최소 Heap이 존재. 최대 Heap은 부모 노드의 값이 자식 노드의 값보다 같거나 큰 Complete binary tree, 최소 Heap은 자식 노드의 값 부모 노드의 값보다 같거나 큰 Complete binary tree. 내림차순 정렬.. 2022. 8. 4.
Algorithm - Sieve of Eratosthenes(소수판별 알고리즘) Sieve of Eratosthenes(에라토스테네스의 체) 고대 그리스 수학자 에라토스테네스의 가장 대표적인 소수(Prime Number) 판별 알고리즘. 마치 체로 수를 걸러낸다고 해서 에라토스테네스의 체 라고 부름. 소수들을 대량으로 빠르고 정확하게 구하는 방법. 소수는 양의 약수를 두개만 가지는 자연수(2, 3, 5, 7, 11, ... 등). 모든 경우의 수를 다 돌며 약수 여부를 확인하는 경우 시간 복잡도 => O(N). 매우 비효율적. -> 특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 됨. (ex. 8 = 2 * 4 = 4 * 2). => O(N^(1/2)) -> 한 두개의 소수를 판별하는 게 아닌 대량의 소수를 한꺼번에 판별하고자 할 때 사용하는 것이 바로 에라토스테네스의 체 즉, 어.. 2022. 7. 30.
Algorithm - 크루스칼 알고리즘(Kruskal) Kruskal Algorithm : 그래프 내의 모든 노드들을 가장 적은 비용으로 연결하기 위해 사용하는 알고리즘. / greedy algorithm으로 분류됨. / 최소 신장 트리를 만들기 위한 알고리즘(신장 트리 = spanning tree, 하나의 그래프가 있을때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미, 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 함 / 최소 신장 트리 = minimum spanning tree, 신장 트리 중에서도 최소한의 비용으로 만들 수 있는 최소 신장트리를 찾는 알고리즘). / 그래프에는 vertex(정점)와 edge(간선)이 있는데, edge에 가중치가 포함되어 있음. / 여러개의 vertex가 .. 2022. 7. 21.
Algorithm - Union Find(합집합 찾기) Union Find : 대표적인 그래프 알고리즘으로 합집합 찾기 라는 의미를 갖고 있음. / 서로소 집합(공통 원소가 없는 두 집합, example- {1,2}, {3,4} == 서로소 관계, {1,2}, {2,3} == 서로소 관계 아님), 상호배타적 집합(Disjoint-Set) 알고리즘 이라고도 불림. / 여러 노드가 존재할 때, 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘. / 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조. / Union Find 알고리즘은 다른 고급 그래프 알고리즘의 베이스가 됨. (ex. Kruskal Algorithm) Disjoint Set = 서로 중복되지 않는 부분 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자.. 2022. 7. 16.
Algorithm - Floyd Warshall(플로이드 와샬) Floyd-Warshall Algorithm : 모든 최단 경로를 구하는 알고리즘. 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘. 알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)를 찾음. 알고리즘 자체는 경로를 반환하지는 않지만, 알고리즘을 약간만 변형시키면 경로를 찾을 수 있음. '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하고 싶다면 플로이드 와샬 알고리즘 사용. / 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택해야 했다면, 플로이드 와샬 알고리즘은 기본적으로 '거쳐가는 정점'을 기준으로 알고리즘을 수행한다는 특징이 있음. / Dynamic Programming 기술 사용. 핵심 - 말그대로 거쳐가는 정점.. 2022. 7. 5.
Counting Sort & Radix Sort Counting Sort & Radix Sort (기수 정렬) - element 값을 명시적으로 비교하지 않아도 정렬할 수 있는 기법 Comparison sort = 두 개 요소 값을 반복적으로 비교하여 정렬을 수행하는 알고리즘. (Decision tree 모델 이라고도 불림) ● Counting Sort counting sort로 1,3,2,4,3을 정렬하면 count[1] = 1; count[2] = 1; count[3] = 2; count[4] = 1; 해당 개수만큼 순서대로 써주면 됨. -> 이 방식은 stable sorting이 불가능. (stable sorting = 처음 가진 순서를 유지한 상태로 정렬을 하는 방식을 말함. 같은 값을 가졌다고 해서 순서를 마음대로 배치시키는 것이 아니라 원래.. 2022. 6. 28.
반응형

티스토리툴바