수도코드
-
알고리즘: 최적알고리즘(분기한정법)으로 외판원문제(TSP)를 풀 수 있을까?알고리즘 2020. 11. 16. 10:22
이전의 포스팅에서는 동적계획법을 이용하여 20개의 도시에 대한 외판원문제(TSP)를 풀었다. 하지만 40개의 도시에 대한 문제로 확장했을 때, 문제를 푸는데 6년이상 걸리므로 해밀토니안 회로 문제를 푸는 되추적 알고리즘을 이용하여 그저 아무경로나 취하는걸로 만족하게 되었다. 하지만 이 알고리즘은 경로를 효율적으로 찾기는 하겠지만 최적의 여행경로와는 거리가 멀 수 있다. 그래서 이번 포스팅에서는 최적의 값을 찾는데 특화된 분기 한정법을 이용하여 40개의 도시에 대한 최적 여행 경로를 구할 수 있는지 알아본다. 다음은 이 포스팅을 읽기전에 참고하면 좋은 것들이다. 알고리즘: TSP 외판원문제 알고리즘 공부하기(동적 프로그래밍)(feat. c++, 의사코드) < TSP(The Travling Salespers..
-
알고리즘: 부분집합의 합(sum of subset) 공부하기!(Backtracking 문제)알고리즘 2020. 11. 9. 23:46
부분집합의 합 구하기 문제에서는 양의 정수(무게) wi가 n개와 양의 정수 W가 있다. 합이 W가 되는 정수의 부분집합을 모두 찾는 것이 목표다. 전에 다루었던 knapsack문제와 유사하지만 부분집합의 합 구하기 문제에서는 조건을 만족하는 모든 집합을 찾는다는 점에서 다르다. 알고리즘: 배낭채우기(knapsack problem) 공부하기!(0-1 knapsack problem) 탐욕 알고리즘과 동적계획법은 최적화 문제를 푸는 두가지 방법이다. 둘 중 어떤 방법을 사용해도 문제를 풀 수 있다. 단일 출발점 최단경로 문제에서는 동적계획법은 모든 마디를 출발점으로 seungjuitmemo.tistory.com 예를 들어보자 n = 3, W =6 w1 = 2, w2 = 4, w3 = 5 이라 할때 각 노드들의..
-
알고리즘: 몬테칼로 알고리즘을 이용한 효율성 추적!알고리즘 2020. 11. 9. 23:17
알고리즘: 되추적(Backtracking) 공부하기! (N-Queens problem을 풀어보자) 되추적은 임의의 집합에서 주어진 기준대로 원소의 순서를 선택하는 문제를 푸는데 사용한다. 전형적인 사례로 체스의 n-Queens Problem이 있다. 이 문제의 목표는 n x n 크기의 서양 장기판에 서로 seungjuitmemo.tistory.com 이 전의 포스팅에서 되추적 알고리즘의 효율성에 대해서 문제 삼았고 이를 해결하지 못했다. 되추적 알고리즘이 어떤 특정 사례를 얼마나 효율적으로 처리하는지에 대한 추정치가 있다면 그 사례에 대해서 그 알고리즘을 사용하는게 타당한 지 결정할 수 있다. 몬테칼로 알고리즘은 확률 알고리즘이기 때문에 표본공간의 무작위 표본의 평균치를 가지고 표본공간에서 정의된 무작위..
-
알고리즘: 되추적(Backtracking) 공부하기! (N-Queens problem을 풀어보자)알고리즘 2020. 11. 9. 20:11
되추적은 임의의 집합에서 주어진 기준대로 원소의 순서를 선택하는 문제를 푸는데 사용한다. 전형적인 사례로 체스의 n-Queens Problem이 있다. 이 문제의 목표는 n x n 크기의 서양 장기판에 서로 잡아먹히지 않도록 n개의 여왕말을 위치시키는 것이다. 즉, 어떤 여왕말끼리도 같은 행이나 열, 대각선상에 위치할 수 없다. 이 문제에서 순서는 여왕말을 둘 n개의 각각 다른 위치이고, 집합은 서양 장기판에서 말을 둘 수 있는 n제곱개의 위치들이 되고, 기준은 어떤 여왕말도 서로 잡아 먹히지 말아야 한다는 것이다. 되추적은 트리의 변형된 깊이우선탐색(DFS)이다. DFS에 대해 간단히 설명하면 부모의 노드에서 내려갈 수 있는 자식노드까지 내려가고 그 이후의 자식 노드가 없다면 다시 부모노드로 돌아가면서..
-
알고리즘: TSP 외판원문제 알고리즘 공부하기(동적 프로그래밍)(feat. c++, 의사코드)알고리즘 2020. 10. 8. 22:25
외판원이 출장시간을 줄이기 위해 거주하고 있는 도시에서 출발하여 각 도시를 한 번씩 방문하고, 다시 출발한 도시로 돌아온다고 했을 때 가장 짧은 여행길을 찾는 알고리즘 start node가 있고 n-1 개의 node를 거쳐 1번 node로 돌아간다. brute-force 알고리즘을 이용해서 문제를 해결할 수도 있지만 n이 20만 되어도 걸리는 시간복잡도는 19!usecs(대략 3857년)으로 평생 구하지 못한다. 하지만 동적프로그래밍을 이용한 TSP알고리즘이면 45초만에 해결가능하다. 그렇다면 예제를 TSP알고리즘을 이용하여 풀어보자 다음과 같이 가중치가 있고, 노드 4개로 이루어진 그래프(V)가 있다. 그리고 위 그래프를 인접매..
-
알고리즘: 큰 수의 곱셈 알고리즘(feat. c++ pseudocode )알고리즘 2020. 9. 27. 19:11
빅데이터 시대에서는 엄청나게 큰 숫자를 다루는 일이 존재한다. 하지만 자료형들은 수를 담을 수 있는 한계가 존재하고 배열로 표현함으로써 더 큰 정수를 표현할 수 있다. 예를 들어, S[5]S[4]S[3]S[2]S[1] = 92420로 표현할 수 있다. 이런 방식으로 표현한다면 표현하지 못할 수는 없다. 하지만 큰 수만 표현할 수 있으면 뭐하냐 효율적으로 연산이 가능해야 한다. 큰 수의 덧셈뺄셈은 많은 시간복잡도를 잡아먹지는 않지만, 곱셈의 경우에는 단순한 방법으로 quadratic-time algorithm(두개의 반복문)을 이용하여 곱셈으로 자릿수를 표현하면 시간복잡도는 다음과 같다. 하지만 이보다 더 좋은 큰자리수 곱셈알고리즘이 존재한다. 분할정복으로 이 보다 더 좋은 차수의 큰 정수 곱셈을 만들어보..