Union-Find(또는 Disjoint Set Union, DSU)는 그래프 알고리즘에서 서로소 집합(Disjoint Sets)을 관리하기 위해 사용되는 자료구조입니다. 이 알고리즘은 대표적으로 최소 스패닝 트리(MST) 알고리즘인 Kruskal's Algorithm에서 사용되며, 효율적으로 그래프의 연결성을 판단하거나 집합을 관리할 수 있습니다. 1. Union-Find란 무엇인가?Union-Find는 다음 두 가지 연산을 빠르게 수행할 수 있도록 설계된 자료구조입니다.Find(x): 원소 x가 속한 집합의 대표자(루트 노드)를 찾습니다.Union(x, y): 원소 x와 y가 속한 두 집합을 하나로 합칩니다.이 두 연산을 통해 집합을 동적으로 관리하며, 집합의 연결성을 확인할 수 있습니다. 예를 들어..

오늘은 분할정복에 대해서 설명해보도록 하겠습니다. 우선 분할정복이란 문제를 여러 개의 작은 하위 문제로 나누고, 각각을 독립적으로 해결한 뒤, 그 결과를 결합하여 전체 문제를 해결하는 방식입니다. 이렇게보면 동적계획법이랑 다른게 없어 보일 수 있습니다. 하지만 이 두 알고리즘은 두 차이점이 존재합니다. 분할정복vs동적계획법분할정복 (Divide and Conquer)아이디어: 문제를 여러 개의 작은 하위 문제로 나누고, 각각을 독립적으로 해결한 뒤, 그 결과를 결합하여 전체 문제를 해결하는 방식입니다.특징하위 문제들이 서로 독립적입니다. 즉, 서로 겹치지 않으며, 동일한 부분 문제를 여러 번 해결하지 않습니다.예시는 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 이진 탐색(Binary..

Interval scheduling Job j starts 𝑠𝑗 and finishes at 𝑓 𝑗.Two jobs are compatible if they don’t overlapGoal: find maximum subset of mutually compatible jobs일을 가장 많이 사용하는 방법을 찾는 경우를 찾는다고 했을 때 문제입니다.직관적으로 봤을 때 b, e, h를 고를 시 가장 많은 경우의 수를 고려하지만 직관적으로 해결 하는 것이 아닌 다양한 접근법을 이용해서 해결 해보겠습니다.Approach 1) Earliest start time: Consider jobs in ascending order of 𝑠 𝑗일이 시작되는 시간 중에서 가장 먼저 시작되는 일을 기준으로 시작한다...

비트마스크란?비트마스크(Bitmask)는 이진수의 비트를 사용해 여러 상태나 조합을 효율적으로 표현하는 기법입니다. 각 비트는 특정한 상태를 나타내며, 비트 연산을 통해 다양한 조합을 처리할 수 있습니다. 비트마스크는 조합 문제나 상태 추적 문제에서 특히 유용하게 사용됩니다. 장점메모리 효율성: 비트를 사용해 여러 상태를 간단하게 저장할 수 있어, 메모리 공간을 절약할 수 있습니다.속도: 비트 연산은 빠르기 때문에, 대량의 데이터를 신속하게 처리할 수 있습니다.조합 관리: 비트마스크를 사용하면 여러 상태를 조합하는 문제를 쉽게 해결할 수 있습니다.코드의 간결성: 비트 연산을 사용하면 코드가 간결해지고 가독성이 좋아질 수 있습니다.단점이해의 어려움: 비트마스크의 개념이 초보자에게는 다소 복잡하게 느껴질 수..

투 포인터 기법은 배열이나 리스트를 탐색하는 데 매우 효율적인 알고리즘 기법입니다. 두 개의 포인터를 사용하여 문제를 해결하는 이 기법은 주로 정렬된 데이터에서 특정 조건을 만족하는 쌍을 찾는 데 유용합니다. 이 기법은 많은 경우에 O(N) 또는 O(N^2)의 시간 복잡도를 가지며, 최적화된 솔루션을 제공합니다. 투 포인터(Two Pointer) 기본 개념투 포인터 기법은 다음 두 가지 주요 방식으로 사용됩니다:양 끝에서 시작하기적용 예: 정렬된 배열에서 두 수의 합이 목표 값과 일치하는 쌍을 찾는 문제방법: 배열의 시작과 끝에 각각 포인터를 두고, 두 포인터가 가리키는 값의 합을 계산합니다. 합이 목표 값과 같으면 쌍을 찾은 것이고, 그렇지 않으면 포인터를 조정합니다.같은 방향으로 이동하기적용 예: 특..

이분 탐색(Binary Search)은 정렬된 배열에서 특정 값을 빠르게 찾기 위한 효율적인 알고리즘입니다. 이 알고리즘은 배열을 반복적으로 반으로 나누면서 원하는 값을 찾는 방식으로 동작하며, 시간 복잡도가 O(logn)입니다. 이는 선형 탐색(Linear Search)의 O(n)과 비교할 때 훨씬 더 효율적입니다. 이분 탐색 알고리즘의 동작 원리시작과 끝 설정: 배열의 시작점(low)과 끝점(high)을 설정합니다.중간점 계산: 시작점과 끝점의 중간 인덱스(mid)를 계산합니다.중간값 비교: 배열의 중간 값(arr[mid])과 찾고자 하는 값(target)을 비교합니다.만약 arr[mid]가 target과 같으면, 해당 인덱스를 반환합니다.만약 arr[mid]가 target보다 크면, target은 ..

최소공배수(LCM, Least Common Multiple)를 구하는 여러 가지 방법이 존재하며, 이 중에서도 유클리드 호제법을 활용한 방법이 가장 효율적입니다. 아래에서는 여러 방법을 비교하고, 각 방법의 특징과 효율성을 설명하겠습니다. 1. 완전 탐색 기반 방법 (Brute Force)이 방법은 두 수의 배수를 계산하고, 가장 작은 공통 배수를 찾는 매우 직관적인 방법입니다. 알고리즘a와 b의 배수를 각각 계산합니다.두 수의 배수 중에서 가장 작은 공통 배수를 찾습니다.def lcm_brute_force(a, b): max_ab = max(a, b) lcm_value = max_ab while lcm_value % a != 0 or lcm_value % b != 0: lc..

이번에는 최대공약수(GCD, Greatest Common Divisor)를 구하는 여러 알고리즘을 소개하겠습니다. 각 방법은 효율성이나 구현 방식에 차이가 있습니다. 1. 완전 탐색 방법 (Brute Force)첫 번째는 완전 탐색 방법을 이용한 최대 공약수를 구하는 방법 입니다.가장 직관적인 방법으로, 두 수의 공통된 약수 중에서 가장 큰 값을 찾는 방법입니다. 알고리즘두 수 중 작은 수를 선택합니다.그 수로부터 1까지 모든 수에 대해 두 수 모두를 나눌 수 있는지 확인합니다.두 수를 모두 나눌 수 있는 가장 큰 수가 최대공약수입니다.def gcd_brute_force(a, b): min_num = min(a, b) for i in range(min_num, 0, -1): if ..

탐욕 알고리즘이라고도 불리는 그리디 알고리즘이 있다.그리디 알고리즘은 항상 각 단계에 있어서 가장 좋을 거라 생각되는 선택을 한다. 다시 말해 이 선택이 전체적으로 최적해로 안내하게 될 거라는 바람을 가지고 부분적으로 최적인 선택을 한다. 그리디 알고리즘의 접근 과정selection procedure: 현재 상태에서 가장 greedy한 선택으로 해를 결정feasibility check: 결정한 해의 적절성 검사solution check: 해의 최적성 검사https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 탐욕 알고리즘(Gr..

소수(Prime Number)란 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다.https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0) 소수 (수론) - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 각각의 자리에 놓인 숫자와 소수점을 통해 나타낸 실수(小數)에 대해서는 소수 (기수법) 문서를 참고하십시오. 좌측은 소수, 우측은 합성수. ...소수란 1보다 큰ko.wikipedia.org소수만 구하는 알고리즘 풀이12부터 n까지 나눠보고 나머지가 0이 안나오게 되면 소수가 되는 방법이다. 이 경우에는 시간 복잡도가 O(n)이 된다.bool isPrime(int n) { for (int i = 2; i..