시간복잡도
-
알고리즘: 최적알고리즘(분기한정법)으로 외판원문제(TSP)를 풀 수 있을까?알고리즘 2020. 11. 16. 10:22
이전의 포스팅에서는 동적계획법을 이용하여 20개의 도시에 대한 외판원문제(TSP)를 풀었다. 하지만 40개의 도시에 대한 문제로 확장했을 때, 문제를 푸는데 6년이상 걸리므로 해밀토니안 회로 문제를 푸는 되추적 알고리즘을 이용하여 그저 아무경로나 취하는걸로 만족하게 되었다. 하지만 이 알고리즘은 경로를 효율적으로 찾기는 하겠지만 최적의 여행경로와는 거리가 멀 수 있다. 그래서 이번 포스팅에서는 최적의 값을 찾는데 특화된 분기 한정법을 이용하여 40개의 도시에 대한 최적 여행 경로를 구할 수 있는지 알아본다. 다음은 이 포스팅을 읽기전에 참고하면 좋은 것들이다. 알고리즘: TSP 외판원문제 알고리즘 공부하기(동적 프로그래밍)(feat. c++, 의사코드) < TSP(The Travling Salespers..
-
알고리즘: 스케줄짜기(Scheduling)공부하기! (시스템 내부시간 최소화, 마감시간이 있는 스케줄짜기)알고리즘 2020. 11. 6. 13:08
어떤 미용사에게 여러가지를 서비스를 받으려고 기다리는 손님이 있다고 하자. 서비스에 걸리는 시간은 모두 다르고 미용사는 얼마나 걸릴지 알고 있다. 손님들이 기다리는 시간을 최소가 되도록 손님을 서비스하는 것을 스케줄 짜기(sheduling)이라 하며 기다리고 머리하는데 걸리는 시간을 시스템 내부시간(time in the system)이라 한다. 그리고 마감시간이 정해진 경우(scheduling with deadlines)가 있는데 각 작업을 끝내는데 같은 시간이 걸리지만 각 작업과 관련된 보상을 최대로 얻기 위해서 마감시간을 고려해야하는 경우다. 이렇게 스케줄짜기는 시스템 내부시간(time in the system)과 마감시간이 있는 스케줄짜기(scheduling with deadlines)로 나뉘며 이..
-
알고리즘: 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)가 있다. 그리고 위 그래프를 인접매..
-
알고리즘: Dynamic programming을 이용한 이항계수(Binomial Coefficient) (feat.c++)알고리즘 2020. 10. 2. 15:39
이항계수는 다음과 같이 표현되며 다음과 같은 성질을 따른다. int binomial(int n, int k) { if (k == 0 || k == n) { return 1; } return binomial(n - 1, k) + binomial(n - 1, k - 1); } 이렇게 간단하게 구현 가능하지만, 효율적이지는 않다. 알고리즘을 재귀호출하면서 이미 했던 계산을 반복해서 수행하기 때문이다 하지만 동적프로그래밍을 이용하면 중복되는 부분을 커버하여 효율적인 알고리즘을 만들 수 있다. Divide and conquer가 top-down 방식이였다면 dyna..
-
알고리즘: 슈트라센(Strassen) 행렬 곱셈 알고리즘 (feat.c++ ,pseudocode)알고리즘 2020. 9. 27. 15:33
이번 포스팅은 일반적인 정방행렬의 곱셈을 알아보고 더 빠른 슈트라센(Strassen) 행렬곱셈에 대해서 알아본다. void matrixMulti(const int a[][N], const int b[][N], int c[][N]) { for (int i = 0; i < N;i++) for (int j = 0; j < N; j++) { c[i][j] = 0; for (int k = 0; k < N; k++) { c[i][j] = c[i][j] + a[i][k] * b[k][j]; } } } 일반적인 행렬곱셈은 우리가 아는 행렬곱셈 그대로 코딩하면 위와 같은 3중 for문으로 구성된다. 1. 시간복잡도 분석 입력 크기 행과 열의 수가 n이라고 할 때 1) 곱셈의 관점 2) 덧셈의..
-
알고리즘: 예제를 풀어보자! (feat. 투자의 귀재 규식이)(Brute force, Divide and conquer)알고리즘 2020. 7. 13. 20:04
규식이는 친구들 사이에서 투자의 귀재로 알려져 있습니다. 페이스북과 인스타그램에 자신의 성과를 과시하기 때문인데요. 사실 규식이가 그 정도의 실력자는 아닙니다. 성과가 좋을 때에만 SNS에 공유해서 그렇게 비춰질 뿐이죠. 계속해서 멋진 모습을 보여주기 위해, 특정 기간 중 수익이 가장 큰 구간을 찾아내는 함수 sublist_max를 작성해 보려고 합니다. 우선 함수 sublist_max는 파라미터로 며칠 동안의 수익이 담겨 있습니다. 예를 들어서 profits가 [7, -3, 4, -8]이라면 첫 날에는 7달러를 벌었고, 둘째 날에는 3달러를 잃었고, 셋째 날에는 4달러를 벌었고, 마지막 날에는 8달러를 잃은 거죠. 먼저 이 문제를 Brute Force 방법을 이용해서 이 문제를 한 번 풀어봅시다! 1...