알고리즘
-
알고리즘: 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)가 있다. 그리고 위 그래프를 인접매..
-
알고리즘: 플로이드 와샬(Floyd Warshall) 알고리즘(Dynamic programming) (feat. c++)알고리즘 2020. 10. 2. 21:47
가중치가 포함된 어떤 그래프가 있을 때 모든 지점에서 모든 지점까지의 최소거리를 구하는데 유용하다. 물론 Brute-force 알고리즘을 이용하면 구할 수 있지만, 이는 매우 비효율적이다. 그래서 이러한 문제들은 동적프로그래밍을 이용하여 효율적으로 해결한다. 플로이드를 이용하기 위한 그래프 인접행렬에 대한 표현은 다음과 같다. 그리고 W를 통해서 D를 구한다. 아울러 P를 두어 두 지점 사이를 거치는 지점을 매핑한다. void floyd(const int W[N][N], int D[N][N], int P[N][N]) { for (int i = 0; i < N; i++)for (int j = 0; j < N; j++) D[i][j] = W[i][j]; for (int k = 0; k < N; k++) fo..
-
알고리즘: 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..
-
알고리즘: 큰 수의 곱셈 알고리즘(feat. c++ pseudocode )알고리즘 2020. 9. 27. 19:11
빅데이터 시대에서는 엄청나게 큰 숫자를 다루는 일이 존재한다. 하지만 자료형들은 수를 담을 수 있는 한계가 존재하고 배열로 표현함으로써 더 큰 정수를 표현할 수 있다. 예를 들어, S[5]S[4]S[3]S[2]S[1] = 92420로 표현할 수 있다. 이런 방식으로 표현한다면 표현하지 못할 수는 없다. 하지만 큰 수만 표현할 수 있으면 뭐하냐 효율적으로 연산이 가능해야 한다. 큰 수의 덧셈뺄셈은 많은 시간복잡도를 잡아먹지는 않지만, 곱셈의 경우에는 단순한 방법으로 quadratic-time algorithm(두개의 반복문)을 이용하여 곱셈으로 자릿수를 표현하면 시간복잡도는 다음과 같다. 하지만 이보다 더 좋은 큰자리수 곱셈알고리즘이 존재한다. 분할정복으로 이 보다 더 좋은 차수의 큰 정수 곱셈을 만들어보..
-
알고리즘: 슈트라센(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) 덧셈의..
-
알고리즘: Divide and conquer를 이용한 quick sort 구현 (feat. c++)알고리즘 2020. 9. 27. 11:27
이름은 빠른 정렬이지만 사실상 가장빠른 정렬 알고리즘이라고 할 수는 없다. 차라리 분할교환정렬(partition exchange sort)라고 하는게 더 정확하다. 이번 포스팅은 quick sort를 분할 정복으로 구현한다. 사실상 quick sort 분할정복구현에는 가중치가 분할 > 정복이다. 즉 정복에는 별거 없다. 하지만 분할과정이 까다롭다. quick sort를 분할 정복으로 다음과 같이 나눈다. 배열의 원소 중 하나를 pivot으로 잡는다. (어떤 값을 pivot으로 잡든 상관 없다. 단지 기준을 만들어주기 위함이다) 주로 배열의 가장 끝값이나 처음 값을 기준으로 잡는다. 예를 들어 다음과 같은 배열이 있다. array = { 6, 2, 5, 3, 7, 10..
-
알고리즘: 백준 2565번 전깃줄 (feat. c++) 최장증가수열문제(LIS)알고리즘 2020. 8. 31. 22:41
백준 2565번 문제입니다. 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 좀 꼬아놓은 최장증가 수열 문제 (사실 최장증가수열문제는 처음 접해보았다...) 처음에는 파이썬으로 스택을 이용해서 풀었지만 무슨 이유인지 틀렸다고 나왔다... (틀린 코드) n = int(input()) line_list = [] for i in range(n): line_list.append(list(map(int, input().split()))) del_count = 0 while True: cross = [] for i in ran..
-
알고리즘: 백준 11048번 이동하기 (feat. python)알고리즘/백준(BaekJoon) 2020. 8. 27. 22:42
백준 11048번 링크입니다. 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 �� www.acmicpc.net DFS 인줄 알았지만 시간초과가 나길래 다시 보니 다이나믹프로그래밍이였던 문제 dp를 이차원 리스트로 만들어서 dp[N][M] = (N, M)까지 오기까지의 합이라고 한다면 dp[N][M] = max(dp[N - 1][M], dp[N][M - 1], dp[N - 1][M - 1]) + maze[N][M] 라고 할 수 있다. import sys input = sys.stdin.readline N, M = map(in..