본문 바로가기

파이썬 알고리즘

 (20)
분기 한정 기법 (Branch-and-Bound) 백트래킹 기법 (Backtracking) 문제의 조건에 따라 해를 깊이 우선 탐색으로 찾음 최적화 문제에 대해서는 최적해가 상태 공간 트리의 어디에 있는지 알 수 없으므로, 트리에서 대부분의 노드를 탐색해야 하고 입력의 크기가 커지면 해를 찾는 것이 거의 불가능 이러한 단점을 보완한 탐색 기법이 분기 한정 기법 분기 한정 기법 (Branch-and-Bound) 상태 공간 트리의 각 노드에 특정한 값(한정값)을 부여 노드의 한정값을 활용하여 가지치기를 함으로써 백트래킹 기법보다 빠르게 해를 찾음 분기 한정 기법에서는 가장 우수한 한정값을 가진 노드를 먼저 탐색하는 최선 우선 탐색으로 해를 찾음 해 탐색 원리 1. 최적해를 찾은 후에 나머지 노드의 한정값이 최적해의 값과 같거나 나쁘면 더 이상 탐색 X (가..
동전 거스름돈 문제 동전 거스름돈 문제 대부분의 경우 그리디 알고리즘으로 해결되나, 그렇지 않은 경우도 존재 ex) 거스름돈이 20원일 때 동전이 16원, 10원, 5원, 1원인 경우(그리디는 16원 1개, 1원 4개의 결과가 나옴) DP 알고리즘은 모든 동전 거스름돈 문제에 대해 항상 최적해를 도출 앞서 했던 배낭 문제의 DP 알고리즘에서 배낭의 용량을 1kg씩 증가시켜가며 문제를 해결한 것처럼 거스름돈을 1원씩 증가시켜가며 문제를 해결 C[n] = n원을 거슬러 받을 때 사용되는 최소의 동전 수 ◼ 500원 동전이 필요하면 (n-500)원의 해(C[n-500])에 500원 동전 1개 추가 ◼ 100원 동전이 필요하면 (n-100)원의 해(C[n-100])에 100원 동전 1개 추가 ◼ 50원 동전이 필요하면 (n-50)..
배낭 문제 배낭 문제 n개의 물건과 각 물건 i의 무게 wi와 가치 vi가 주어지고, 배낭의 용량이 C일 때, 배낭에 담을 수 있는 물건의 최대 가치를 구하는 문제 (각 물건은 1개씩만 존재) 배낭의 용량이 0(kg)부터 1(kg)씩 증가하여 최종 용량인 C(kg)가 될 때까지 변화시켜 가며 배낭의 용량 내에서 어떤 물건을 담았을 때 가치가 더 커지는지를 결정 임시 배낭 용량 : 배낭 용량은 C(kg)이지만 배낭 용량이 0(kg)부터 1(kg)씩 증가할 경우의 배낭 용량 K[i, w] = 물건 1 ~ i까지만 고려하고, (임시) 배낭의 용량이 w일 때의 최대 가치 ∴ K[n, C] = 구하고자 하는 최종해 두 가지 경우가 존재 ① 물건 i의 무게 > 임시 배낭 용량 ② 물건 i의 무게 임시 배낭 용량 물건 i를 배..
편집 거리 편집 거리 (Edit Distance) 삽입(insert), 삭제(delete), 대체(substitute) 연산을 사용하여 스트링 S를 수정하여 다른 스트링 T로 변환하고자 할 때 필요한 최소의 편집 연산 횟수 예제 S = strong T = stone E[i, j] = S의 처음 i개 문자를 T의 처음 j개 문자로 바꾸는데 필요한 편집 거리 E[4, 3] = 'strong' → 'stone'에 대해서, 'stro'를 'sto'로 바꾸기 위한 편집 거리 s1 → t1 ['s' → 's'] : s1 = t1 = 's' 이므로 E[1, 1] = 0 s1 → t1t2 ['s' → 'st'] : s1 = t1 = 's'이고, 't'를 삽입하므로 E[1, 2] = 1 s1s2 → t1 ['st' → 's'] :..
모든 쌍 최단 경로 찾기 (플로이드 워셜 알고리즘) 동적 계획 알고리즘 (Dynamic Programming; DP) 입력 크기가 작은 부분 문제들을 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘 분할 정복 알고리즘과 유사한 부분이 많으나 DP는 같은 부분 문제를 다시 풀지 않는다는 점, 부분 문제의 해를 중복 사용한다는 점에서 정복 기법과 다름 모든 쌍 최단 경로 (All Pairs Shortest Paths) 찾기 각 쌍의 점 사이의 최단 경로 다익스트라 알고리즘을 이용한다면 각 점을 시작점으로 정하여 다익스트라 알고리즘 수행 플로이드-워셜 알고리즘 워셜(Warshall) : 그래프에서 모든 쌍의 경로 존재 여부를 찾아내는 동적 계획 알고리즘을 제안 플로이드(Floyed)..
백트래킹 기법 (Backtracking) 백트래킹 기법 (Backtracking) 해를 찾는 도중에 막히면(해가 아니면) 되돌아가서 다시 해를 찾아가는 기법 깊이 우선 탐색을 통해 해를 찾음 TSP(Traveling Salesman Problem)를 위한 백트래킹 알고리즘 tour = [] : 방문한 지점(방문 순서) bestSolution = (tour, tour의 거리) : 현재까지 찾은 가장 거리가 짧은 해 BacktrackTSP(tour) 함수 ① tour가 완전한 해일 때 (모든 지점을 다 방문했을 때) ② tour가 완전하지 않을 때 (모든 지점을 방문하지 않았을 때) ① tour가 완전한 해일 때 (모든 지점을 다 방문했을 때) 만약 tour의 거리가 bestSolution의 거리보다 작으면 bestSolution = (tour, ..
기수 정렬 (Radix Sort) 기수 정렬 (Radix Sort) 제한적인 범위 내에 있는 숫자(ex. 주민등록번호, 학번, 계좌번호)에 대해서 각 자릿수 별로 정렬하는 알고리즘 기(radix) : 특정 진수를 나타내는 숫자들 10진수의 기 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 2진수의 기 : 0, 1 LSD 기수 정렬 Least Significant Digit(LSD) 기수 정렬 1의 자리부터 k자리로 정렬 수행 RL(Right-to-Left) 기수 정렬이라고도 함 MSD 기수 정렬 Most Significant Digit(MSD) 기수 정렬 k자리부터 1의 자리로 정렬 수행 LR(Left-to-Right) 기수 정렬이라고도 함 # LSD(RL) 기수 정렬 from collections import deque def..
힙 정렬 (Heap Sort) 이진 힙 (Binary Heap) 힙 조건(각 노드의 우선순위가 자식 노드의 우선 수위보다 높음)을 만족하는 완전 이진트리 최대 힙(Maximum Heap) : 가장 큰 값을 루트에 저장 최소 힙(minimum Heap) : 가장 작은 값을 루트에 저장 힙에서 부모와 자식 관계 A[i]의 왼쪽 자식 = A[2i] A[i]의 오른쪽 자식 = A[2i+1] A[i]의 부모 = A[i/2] (i가 홀수면 i/2에서 정수 부분만) 힙 정렬 (Heap Sort) 정렬할 입력으로 최대 힙을 만들어 가장 큰 수가 저장되어 있는 루트와 힙의 가장 마지막 노드를 교환(가장 큰 수를 배열의 맨 뒤로 옮김) 힙 크기를 1개 줄인 후 위배된 힙 조건을 해결하여 다시 힙 정렬 수행 루트 90과 힙의 마지막 노드 40을 바꾼 후..

티스토리툴바