분할 정복(Divide and Conquer)을 사용한 거듭제곱 계산법은 수학적 문제 해결과 알고리즘 설계에서 매우 강력한 접근 방식입니다. 이 방법은 복잡해 보이는 문제를 더 작고 관리하기 쉬운 부분 문제로 나누고, 이를 재귀적으로 해결한 다음, 결과를 조합하여 최종 해답을 도출합니다. 특히, 거듭제곱 계산과 같은 수학적 연산에서 분할 정복 방법은 일반적인 반복 또는 직접 계산 방식보다 훨씬 더 효율적일 수 있습니다. 그 이유를 몇 가지 측면에서 설명해보겠습니다. 시간 복잡도의 개선 가장 직관적인 거듭제곱 계산 방법은 (a)를 (n)번 곱하는 것입니다. 이 방식의 시간 복잡도는 (O(n))입니다. 반면, 분할 정복을 사용한 거듭제곱 계산법은 (O(\log n))의 시간 복잡도를 가집니다. 이는 (n)이..

Knapsack 문제와 Python으로의 구현 Knapsack 문제는 최적화 문제로 알려져 있으며, 가장 잘 알려진 결정론적 알고리즘 문제 중 하나입니다. 다양한 변형이 있지만, 여기서는 가장 대표적인 0-1 knapsack 문제에 대해 설명하겠습니다. 문제 설명: 주어진 물건들과 각 물건의 가치 및 무게, 그리고 일정한 무게를 수용할 수 있는 가방이 있을 때, 가방에 넣을 수 있는 물건들의 가치의 합을 최대화하는 문제입니다. 수식으로 표현하면: n개의 물건이 있고, i번째 물건의 무게는 w[i], 가치는 v[i]라 하자. 가방의 최대 무게는 W로 한정되어 있다. dp[i][j]를 i번째 물건까지 고려하고 가방의 무게 한도가 j일 때의 최대 가치로 정의한다. 본 문제를 풀기 위한 점화식: def knap..

분리 집합(Disjoint Set, Union-Find)은 많은 알고리즘 코딩 테스트에서 중요한 자료구조로 나타납니다. 분리 집합은 여러 노드가 서로 중복되지 않는 집합으로 나뉘어 있을 때, 각 집합을 대표하는 노드 하나를 선택해 그 집합을 대표하도록 구성합니다. 분리 집합의 주요한 사용 용도는 다음과 같습니다: 사이클 판별: 주로 그래프에서 사이클이 있는지 확인할 때 사용됩니다. 간선을 하나씩 추가하면서 두 노드의 루트 노드가 같다면 사이클이 생성되는 것입니다. Kruskal 알고리즘에서 최소 신장 트리를 구할 때 사이클 확인 용도로 사용됩니다. 집합의 병합 및 찾기 연산: 두 집합을 하나로 합치거나, 어떤 원소가 어떤 집합에 속하는지 찾을 때 사용됩니다. 네트워크 연결: 여러 네트워크가 연결되어 있을..

위상 정렬은 방향 그래프의 모든 노드를 방향성을 거스르지 않게 순서대로 나열하는 것입니다. 즉, 어떤 작업을 먼저 해야 다른 작업을 할 수 있는 상황과 같은 "의존성"을 갖는 문제를 표현하고 해결할 때 사용됩니다. 위상 정렬의 전제와 조건 방향 그래프: 위상 정렬은 방향성을 가진 간선으로 이루어진 그래프에서만 수행됩니다. 사이클이 없어야 함: 위상 정렬을 수행할 그래프는 순환이 없어야 합니다. 순환이 있는 경우, 어떤 노드를 먼저 방문해야 하는지 정할 수 없기 때문입니다. 위상 정렬 설명 진입 차수 계산: 각 노드의 진입 차수(들어오는 간선의 수)를 계산합니다. 진입 차수가 0인 노드 찾기: 진입 차수가 0인 노드를 찾고 큐에 넣습니다. 이 노드들은 의존성이 없는 작업이므로 먼저 수행될 수 있습니다. 노..

최단경로 알고리즘이며 모든 노드에서 모든 노드로부터 최단경로를 구할 때 사용하는 알고리즘이다. 플로이드 워셜 vs 다익스트라 저번 시간에 다뤘던 한 지점에서 모든 노드로의 최단경로를 구하는 다익스트라 알고리즘과 플로이드 워셜은 다르다. 다익스트라 알고리즘은 1차원 리스트를 이용하지만 플로이드 워셜 알고리즘은 2차원 리스트를 사용한다. 또한 다익스트라는 방문하지않은 노드 중에서 최단경로를 찾지만 플로이드 워셜은 방문하지않았는지 했는지 관심이 없다. 플로이드 워셜의 점화식 노드의 개수가 N일 때 N번 만큼 2차원 리스트를 갱신하다. 1~N번까지의 노드를 한번씩 K로 정해준 뒤 K를 제외한 N-1개의 노드 중에서 서로 다른 노드 A, B를 고른다. K를 거쳐가는 A-K 경로와 K-B 경로의 가중치를 더해서 기..

본문에 앞서 질좋은 책을 집필해주신 나동빈님한테 감사합니다. 벨만포드 알고리즘을 최단경로 문제에서 다익스트라 대신 사용해도 문제는 없지만 시간복잡도가 증가하기에 가급적으로 음수 간선이 존재할 때만 사용해주자 최단경로 문제 유형 1) 모든 간선이 양수인 경우 2) 음수 간선이 있는 경우 2-1) 음수 간선 순환은 없는 경우 2-2) 음수 간선 순환이 있는 경우 벨만 포드 최단 경로 알고리즘은 음의 간선이 포함된 상황에서도 사용할 수 있다. 또한 음수 간선의 순환을 감지할 수 있습니다. 벨만 포드의 기본 시간 복잡도는 O(VE)로 다익스트라 알고리즘에 비해 느리다. 벨만 포드 알고리즘 단계 1) 출발 노드를 설정한다. 2) 최단 거리 테이블을 초기화합니다. 3) 다음의 과정을 N-1번 반복합니다. 3-1) ..

다익스트라 최단경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 최단경로 알고리즘은 '음의 간선'이 없을 때 정상적으로 동작한다. 다익스트라 알고리즘을 세팅할 때는 다음 단계를 거친다. 1, 주어진값으로 정확하게 그래프를 만들어준다. (양방향성인지 단방향인지, 혹은 최대값이 얼마나 나오는지) 2, 다익스트라 알고리즘을 사용해서 풀어준다. 뭐 이렇게 설명해놨냐고 따질 수 있지만 문제를 풀다보면 이게 전부라는 것을 알 수 있다. 그 다음에 시간 감축은 본인의 자료구조 활용도에 따라 달라지기에 이후는 푸는 사람한테 달려있다. 추가로 자료구조 힙을 쓰기에 힙에 대한 이해가 필요하다. INF를 대체로 int(1e..

고대 그리스 수학자인 에라토스테네스가 발견한 알고리즘이다. 그 시대에 어떻게 발견했나 싶네.. 여러개의 소수를 상대할 때 좋은 알고리즘이다. 소수는 1과 자기자신으로 밖에 나눠지지 않는 수이다. (1 제외) 숫자 N의 소수판별은 N을 N의 제곱근이하인 수로 나눴을 때 나눠지지않았을 경우 소수이다. # N 이하의 소수를 찾으려할 경우 # 소수는 1혹은 자기 자신으로 밖에 나눠지지 않는 수 이다. # 0 - N 까지를 표현해줄 리스트 생성 arr = [True for _ in range(N+1)] for i in range(2, int(N**0.5)+1): if arr[i]: for j in range(i*2, N+1, i): arr[j] = False # 0, 1은 소수가 아니기에 제외 print([i f..