Algorithm Strategies

[Algorithm Strategies] 06. Divide & Conquer - Karatsuba Multipy

1. Divide & Conquer 1.1 Karatsuba Multipy - Example Program 1.1.1 Problem - 빠른 곱셈 알고리즘으로, 두 개의 정수를 곱하는 알고리즘 - 32비트 정수 둘을 곱할 때 쓰는 것이 아닌 수백자리, 나아가 수만 자리는 되는 큰 숫자들을 다룰 때 주로 사용 - 이 곱셈 알고리즘을 적용하기 전 기존의 곱셈 알고리즘을 설명 1.1.1.1 O(n2) Mutiply vector DivideConquer::multiply(const vector& a, const vector& b); - 곱셈을 진행할 때 일반적인 정수형 변수가 아닌 정수형 배열을 입력받는 점을 확인 - 이 배열들은 곱할 수의 각 자릿수를 맨 아래 자리부터 저장, 이렇게 순서를 뒤집으면 입출력할 ..

[Algorithm Strategies] 05. Exhaustive Search - Clock Sync

1. Exhaustive Search 1.1 Clock Sync - Optimization Problem 1.1.1 Problem - 4 X 4 격자 형태로 배치된 열어섯 개의 시계가 존재, 이 시계들은 12시, 3시, 6시, 9시를 가리키고 있음 - 이 시계들을 모두 12시를 가리키도록 변경, 시간을 조작하는 유일한 방법은 열개의 스위치들을 조작하는 것 - 각 스위치들은 모두 적게는 세 개에서 많게는 다섯 개의 시계에 연결 - 한 스위치를 누를 때 마다 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직임 스위치 번호 연결된 시계들 스위치 번호 연결된 시계들 0 0, 1, 2 5 0, 2, 14, 15 1 3, 7, 9, 11 6 3, 14, 15 2 4, 10, 14, 15 7 4, 5, 7,..

[Algorithm Strategies] 04. Exhaustive Search - Traveling Sale

1. Exhaustive Search 1.1 Traveling Sale - Optimization Problem 1.1.1 Problem - 어떤 나라에 n개의 큰 도시, 각 도시들은 모두 직선 도로로 연결 - 한 영업 사원이 한 도시에서 출발해 다른 도시들을 전부 한번 씩 방문한 뒤 시작 도시로 돌아오려고 함 - 이때 모든 경로 중 가장 짧은 경로로 찾는 방법 1.1.2 Algorithm Strategy - 나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환 double Exhaustive::shortestPath(vector& path, vector& visited, double currentLength); - 모든 도시를 방문하는 방법 중 가장 거리가 짧은 위치를 찾아 값을 반환 ..