Algorithm

[Algorithm] 유니온 파인드

[Algorithm] 유니온 파인드 (글쓴날 : 2020.05.16) * 이 글은 글쓴이가 공부한 내용을 정리하며 올리는 글입니다. 유니온 파인드 1) 유니온 파인드란? 유니온 파인드란 집합을 관리하는 트리 형태의 자료구조로 Disjoint-set(서로소 집합, 분리 집합)이라고도 하며, 보통 배열에서 인덱스를 노드로 나타내어 각 인덱스의 값에 해당 인덱스의 부모 노드를 저장합니다. 유니온 파인드는 주로 그래프 문제에 적용할 수 있으며, 다른 그래프 알고리즘인 Dijkstra algorithm, Bellman-Ford algorithm 등과 달리, 순수히 노드 간의 연결 관계를 파악할 때 유용하게 사용됩니다. 핵심 연산으로는 2가지가 있으며, 유니온 파인드라는 이름과 걸맞게 다음과 같습니다. 1) uni..

[Algorithm] 슬라이딩 윈도우

[Algorithm] 슬라이딩 윈도우 (글쓴날 : 2020.05.15) * 이 글은 글쓴이가 공부한 내용을 정리하며 올리는 글입니다. 슬라이딩 윈도우 1) 슬라이딩 윈도우란? 슬라이딩 윈도우 알고리즘은 사실 따로 다룰 필요가 없을 정도로 투 포인터 알고리즘과 비슷합니다. 딱 한 가지 다른 점은 바로 범위의 제한인데, 투 포인터의 경우 연산을 위하여 포인터를 이동시키는 범위에 대한 제한이 전혀 없지만, 슬라이딩 윈도우의 경우 특정 범위를 제한하여 이동하는 특징이 있습니다. 이에 따라 크기가 고정적인 창문(특정 범위)을 옆으로 미는 것(이동)을 묘사하여 슬라이딩 윈도우라는 이름이 붙은 것 같습니다. 이런 슬라이딩 윈도우는 주로, 자료구조 Deque를 사용하여 구현합니다. 예를 들어, N개의 숫자가 들어있는 ..

[Algorithm] 투 포인터

[Algorithm] 투 포인터 (글쓴날 : 2020.05.13) * 이 글은 글쓴이가 공부한 내용을 정리하며 올리는 글입니다. 투 포인터 1) 투 포인터란? 투 포인터 알고리즘이란 주로 배열 안에 있는 값들을 연속해서 더하거나 연산하는 경우에 사용되며, 인덱스를 가리키는 두 개의 변수(포인터)를 선언하여 사용하는 특징이 있어 투 포인터라 불립니다. 예를 들어 N개의 숫자가 들어있는 배열이 주어질 때, 부분 집합의 합이 특정 숫자인 M인 경우의 수를 구하는 문제에 적용한다면, 배열의 인덱스를 가리키는 startPointer와 endPointer를 생성한 후 특정 규칙에 의해 각 포인터를 움직여 배열을 탐색해 문제를 해결할 수 있으며, 그 규칙은 다음과 같습니다. 1-1) 현재까지의 합이 M보다 크거나 같..

[Algorithm] 에라토스테네스의 체

[Algorithm] 에라토스테네스의 체 (글쓴날 : 2020.03.23) * 이 글은 글쓴이가 공부한 내용을 정리하며 올리는 글입니다. 에라토스테네스의 체 1) 에라토스테네스의 체란? 에라토스테네스의 체란 소수를 구할 때 사용되는 매우 유용한 알고리즘입니다. 소수란 1과 자신을 제외한 약수가 없는 1이 아닌 자연수를 뜻하며, 이러한 소수를 원하는 범위까지 효율적으로 구하고 싶다면 에라토스테네스의 체를 사용하시면 됩니다. 에라토스테네스의 체의 주요 원리는 정해진 숫자의 범위 내에서 합성수를 지우는 방식으로, 처음 1은 소수가 아니니 지우고, 남아있는 수 중 제일 작은 숫자인 2를 소수로 판별하여 2의 배수를 모두 지웁니다. 똑같이 남아있는 수 중 제일 작은 수인 3을 소수로 판별하여 3의 배수를 모조리 ..

[Algorithm] 유클리드 호제법

[Algorithm] 유클리드 호제법 (글쓴날 : 2020.03.23) * 이 글은 글쓴이가 공부한 내용을 정리하며 올리는 글입니다. 유클리드 호제법 1) 유클리드 호제법이란? 유클리드 호제법이란 어떤 두 자연수의 최대공약수를 구하는 알고리즘의 하나로 최대공약수를 구하는 알고리즘 중 가장 대표적인 알고리즘입니다. 호제법이란 주어진 두 수로 서로 다른 수를 나누어 원하는 결과를 얻는 방법을 의미하며, 그에 따라, 유클리드 호제법은 어떤 자연수 a, b가 있을 때 (a > b), 두 수의 최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수와 같다. 라는 성질을 이용한 알고리즘입니다. 위의 원리에 따라, a를 b로 나눈 나머지를 다시 a로 사용하고 b로 또 나누고 이렇게 반복하다, 나누어떨어질 때 나눈 수가..