본문 바로가기
반응형

Algorithm16

C++로 BigInteger 구현해보기 BigInteger의 구현 원리를 알아보고 C++로 만들어 보도록 하겠다. 메모리 상에 표현가능한 정수의 범위로는 2의 32승 만큼인 -2,147,483,648 ~ +2,147,483,647이다. 하지만 실생활에선 21억이 넘어가는 숫자를 사용할 일이 충분히 많이 있다. 이런 경우에 사용하기 위해서 자릿수 제한 없이 정수 숫자를 표현할 수 있는 BigInteger에 대해 알아보고 만들어 보겠다. BigInteger는 데이터로 들어온 숫자를 문자열로 취급하여 표현할 것이다. BigInteger x; BigInteger y("-1234"); BigInteger z(y); x = "1234"; BigInteger 변수 선언시 생성자에 문자열이 parameter로써 들어가거나 다른 BigInteger의 값을 가.. 2023. 4. 11.
Algorithm - Merge Sort (병합 정렬) Merge Sort : Divide and Conquer의 방식을 사용한 알고리즘. 문제를 작은 2개의 문제로 분리하고 각각을 해결한 후, 그 결과물들을 모아서 원래의 문제를 해결하는 전략. 순환 호출을 주로 사용해서 구현. (과정 : 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 봄 - 그렇지 않다면 정렬되지 않은 리스트를 반으로 잘라서 비슷한 크기의 리스트 두개로 나눔[divide]. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬[conquer]. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병[merge]) / Quick sort와 동일한 시간 복잡도인 O(N*LogN). Quick sort는 pivot값에 따라 편향되게 분할될 수 있으므로 최악의 경우 O(N^2)의 시간 복잡도를 .. 2022. 8. 18.
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.
반응형

티스토리툴바