분할 정복: 큰 문제를 작은 문제로 나누어 각각을 해결하고 다시 병합하는 방식으로 문제를 해결하는 방식.1. DIvide : 큰 문제를 작은 문제들로 나눈다.2. Conquer : 작은 문제를 더 나눌 수 있으면 더 작은 문제로 나누고, 나눌 수 없으면 문제를 해결한다.3. Merge : 작은 문제를 합하면서 큰 문제를 해결한다.  분할 정복의 조건1. 큰 문제를 작은 문제로 나누어도 큰 문제와 해결 방식이 같아야함. ( 작은 문제로 나누어도 문제의 해결 방식이 동일해야함 )2. 쪼개진 문제 간의 연관이 없어야함. 작은 문제가 다른 작은 문제에 영향을 미치면 안됨.  대표적인 예시로 Merge Sort가 있다.  오늘 내가 이 글에서 주목하고자 하는 것은 분할정복을 통한 거듭제곱의 해결이다.[ 백준 C+..

다익스트라 알고리즘은 최단 경로 문제를 해결할 수 있는 알고리즘이다. 최단 경로 알고리즘에는 BFS, 다익스트라, 플로이드와샬, 벨만-포드가 있다. BFS는 간선의 가중치가 모두 같을 때, 다익스트라와 벨만-포드는 각 간선의 가중치가 다를 때 한 정점에서 다른 정점까지의 최단 경로를 구할 때(벨만-포드는 음의 가중치가 있을 때), 플로이드와샬은 모든 정점에서 다른 모든 정점으로의 최단 경로를 구할 때 사용한다고 함. 알고리즘은 다음과 같은 순서를 통해 수행된다. 1. 시작 노드 설정 2. 최단 거리 테이블 초기화 (연결 되지 않은 노드는 INF) 3. 연결되었지만 방문하지 않은 노드 중 최단 거리를 가지는 노드 선택 & 방문 4. 해당 노드를 거쳐 다른 노드로 갈 때의 비용을 계산하여 최단 거리 테이블을..

투포인터 알고리즘은 슬라이딩 윈도우 알고리즘이라고도 하며, 1차원 배열에서 두 개의 포인터를 조작해서 원하는 결과를 얻는 알고리즘이라고 한다. 보통 완전탐색으로 풀어서 시간초과가 날때의 해결책이 될 수 있다고 한다. 아래 문제가 전형적인 투포인터 알고리즘 문제이다. https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 주어진 1차원 배열 중에 합이 M이 되는 부분의 수를 구하는 문제이다. 1) 포인터를 sta..

배낭 문제란.. 나무위키 왈 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분집합을 찾는 문제라고 함. 즉 쉽게 말해서 도둑이 가방에 담을 수 있는 양이 정해져 있는데 얼마나 효율적으로 비싼 물건을 담아 최고의 이득을 볼 수 있는지.. 이런 문제이다. 배낭문제는 크게 fractional knapsack problem, 0-1 knapsack problem 로 나눌 수 있다! 1. fractional knapsack problem (분할 가능한 배낭문제) 이 유형은 좀 단순하다고 생각된다. 별 다른 제약 없이 짐이 분할이 가능한 것이다. 무슨말이냐면, 위 사진과 같이 짐이 있을떄,..