특정 지점에서 다른 모든 지점까지의 최단거리를 구하는 알고리즘에서 사용될 수 있습니다. 그러나 가중치의 유무에 따라서는, 반드시 Dijkstra를 사용해야 하는 경우도 있습니다. 가중치란? 비용(cost), 무게(weight) 등 여러 가지 단어로 나타나는, 중요도(우선 순위)를 말합니다. 가중치가 있는 경우에 대한 예시로 경매장을 들 수 있습니다. 경매장에서의 가중치는 가격입니다. 더 늦게 손을 든 사람일지라도 더 높은 가격(중요도가 큰 것)을 제시한 사람이 우선적으로 소유권을 갖습니다. 그러나 반대로, 이미 정해진 같은 가격으로 물건을 파는 타임 세일의 경우 먼저 물건을 집은 사람이 반드시 먼저 사게 됩니다. 이러한 경우에는 가중치가 없다고 말할 수 있습니다. 가중치가 있는 경우 따라서 가중치가 있는..
재귀 + 브루트포스 + "후보에서 탈락 시 해당 파트의 탐색 종료" 재귀 + 브루트포스가 DFS라면 (모든 조건을 다 탐색) 백트래킹은 모든 경우를 탐색하되 불가능한 후보임을 발견하면 해당 경우는 탐색을 종료한다. 시간 복잡도는 브루트포스와 동일하나 대부분의 경우에서 브루트포스보다 빠르게 동작한다. 후보에서 탈락 방문 중인 노드가 유망한지 체크하고, 유망하지 않다면 하위 트리를 가지치기한다. 종료 조건에 도달한 경우(마지막까지 유망한 경우의 수), 전역으로 선언된 결과값에 이를 반영한다. 구현 def check_node(node, target): global answer # 정답을 담을 변수는 함수 밖에서 관리 if not promising(node): # 방문 중인 노드가 유망하지 않다면 return ..
소수가 아닌 수를 모두 걸러내 소수 여부를 판별하는 알고리즘 소수 여부를 판별할 숫자만큼의 배열을 생성한다. number = 100 # 100까지의 숫자에 대한 소수 여부 판별 prime = [True] * (number+1) 0과 1은 소수가 아니므로 False 처리한다. prime[0] = prime[1] = False 2부터 시작해 해당 숫자가 소수인지 판별하고 소수라면 해당 숫자의 배수는 모두 소수가 아님(False) 처리한다. 소수가 아니라면 넘어간다(continue). for i in range(2, number+1): if not prime[i]: continue for j in range(i*2, number+1, i): prime[j] = False 이 과정을 거치고 나면 각 숫자에 대해..
다이나믹 프로그래밍 (동적 계획법) 최적해를 구하기 위해 매우 많은 시공간이 필요한 경우 연산 결과를 저장하여 중복 연산을 방지함으로써 시공간 효율성을 높임 간단히 말하자면 한 문제를 무조건 한 번만 풀도록 결과를 저장해 사용한다는 것 언제 사용하는가 큰 문제를 작은 문제(큰 문제의 분할)로 나눌 수 있는 경우 작은 문제와 큰 문제의 해결 로직이 같아야 함 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일 해결 로직이 순수함수(동일 입력에 반드시 동일 출력이 보장)에 해당해야 함 어떻게 저장하는가 위 조건을 만족하는 문제들의 연산 결과들은 수열에 해당한다고 볼 수 있다. 수열은 규칙적으로 배열된 숫자들의 모임이기 때문에 배열(리스트)에 저장한다. 분할 정복 알고리즘과의 차이 분할 정복 알고리..
순차 탐색 앞에서부터 하나씩 차례대로 탐색하는 방법 array = [3, 1, 7, 5, 9] for i in range(len(array)): if array[i] == 7: print(i) break 리스트를 차례대로 순회하므로 시간 복잡도는 O(N)이다. 이진 탐색 정렬된 리스트에 대하여 찾으려는 데이터와 중간 지점의 데이터를 비교해나가며 탐색하는 방법 순차 탐색과 달리 정렬이 되어 있어야 사용할 수 있다. 중간이 정확히 안 나누어질 때는 소수점 이하를 버린다. 시간 복잡도는 O(logN)이다. 구현 def binary_search(array, target, start, end): while start array[middle]: start = middle + 1 elif target < array[..
정렬 알고리즘(Sorting Algorithm) 데이터를 일정한 순서대로 열거하는 알고리즘 어떤 정렬을 쓰냐에 따라 프로그램의 효율성이 좌지우지될 수 있다. 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬, 병합 정렬, 힙 정렬 정도까지는 알고 있으면 좋다. 선택 정렬(Selection Sort) 순회하며 제일 작은 데이터를 맨 앞으로 옮김으로써 왼쪽부터 정렬을 완성해가는 방식 코드 def selection_sort(array): for i in range(len(array)): min_index = i for j in range(i + 1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = arra..
