Algorithm_응용

어떤 자연수를 나누어 떨어지게 하는 수약수는 항상 1과 자기 자신의 수가 포함단순한 방법1부터 자기 자신까지 1씩 증가하면서 나누어 떨어지는 경우, 즉 나머지가 0인 경우 리스트에 추가해준다.시간 복잡도 : O(n)효율적인 방법어떤 수 N의 약수는 항상 $N=A\*B$

노드를 합치고, 부모 노드를 찾아 서로소 집합을 찾아내는 알고리즘트리 구조를 활용Union-find 알고리즘은 두 가지의 함수로 이루어진다Find : 두 노드의 부모 노드를 확인하여 같은 집합에 속하는 지를 확인Union : 두 부분집합이 같은 집합에 속하는 경우, 하

주어진 문제를 결정문제로 변형하여 이분탐색을 통해 해결하는 것배열 안의 특정 범위를 좁혀가는 목적으로 사용최대 최소값과 같은 최적해를 구하는 문제에서 유용하게 쓰임시간 복잡도 : O(logN)파라메트릭 탐색은 모든 문제에 적용할 수 없고, 아래의 세 조건을 만족해야 함

탐욕적인 방법(Greedy method)을 이용해 모든 정점을 최소 비용으로 연결하는 최적의 해를 구하는 것각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택이전 단계에서 만들어진 신장 트리와 상관 없이 무조건 최소 간선만을 선택그래프의 간선들의 가중치를 기준으로

신장 트리 중 사용된 간선들의 가중치 합이 최소인 트리각 간선의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소 비용이 얻어지는 것은 아님네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것

음의 가중치가 없는 그래프의 한 정점(Vertex)에서 모든 정점까지의 최단거리를 구하는 알고리즘매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복(Greedy)가중치가 음수인 경우 다익스트라 알고리즘은 사용할 수 없으며, 이 경우 Floyd

배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정한 가치의 무게가 정해진 짐들을 배낭에 담을 때, 가치의 합이 최대가 되는 조합을 찾는 알고리즘Fractional Knapsack Problem물건을 쪼갤 수 있는 배낭 문제로, 가치가 높은 순으로 정렬한 뒤 배낭

투 포인터 알고리즘(Two Pointers Algorithm) 두 포인터를 사용하여 문자열이나 정렬된 배열(또는 리스트)에서 원하는 값을 찾거나 구간합을 구할 때 유용한 알고리즘 슬라이딩 윈도우와 유사하나, 고정된 구간이 아닌 가변적인 구간을 탐색한다는 점에서 차이