Algorithm/알고리즘 (5) 썸네일형 리스트형 [다이나믹 프로그래밍] Chained Matrix Multiplication 다음과 같은 행렬들을 곱한다고 해보자. 괄호를 어떻게 치든지 결과값은 모두 같을 것이다. 하지만 괄호에 따라서 곱셈 연산의 수는 모두 상이하다. 요런 식으로. 위의 그림에 보이듯이 곱셈 연산의 수가 엄청나게 차이가 난다. 그럼 더 적은 곱셈 연산으로 행렬을 곱하기 위해선 어떻게 해야 할까? 이에 대한 문제가 바로 연쇄 행렬 곱셈 (Chained Matrix Multiplication) 문제이다. 이 연쇄 행렬 곱셈 문제는 다이나믹 프로그래밍을 통해 구할 수 있다. optimal 한 부분 수열을 이용하는 것이다. 전체 행렬에 있어서, 두 개의 부분 수열로 분리한다. 각 부분 수열에 있어서, 최소 비용을 구한 후 합쳐준다 이 과정을 분리할 수 있을 때까지 부분 수열의 길이를 늘려주면서 반복한다. 사용되는 변.. 위상 정렬(Topological Sort) 위상 정렬이란? 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 .. [SSSP(1)] Dijkstra Algorithm Single Source Shortest Path Single Source Shortest Path란 하나의 출발점(Single Source)에서 모든 노드까지 도달하는데 걸리는 비용(시간)을 계산하여 최단 경로를 구하는 것입니다. 우선 최단 경로의 정의는 간선의 가중치가 있는 그래프에서 두 노드 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로라고 할 수 있습니다. 다익스트라 알고리즘은 음수 가중치가 없는 그래프에서 사용할 수 있습니다. 음수 가중치가 있을 때는 벨만-포드 알고리즘을 사용할 수 있습니다. 요것은 다음에 정리를 해보겠습니다. 참고로 모든 노드들에 대한 최단 경로(All Pairs Shortest Path)로는 플로이드-와샬 알고리즘이란게 쓰입니다. 얘는 삼중 for문으로 간단하게 구현.. 정렬(Sorting) 선택정렬(Selection Sort) 버블 정렬(Bubble Sort) 삽입 정렬(Insertion Sort) 합병 정렬(Merge Sort) 퀵 정렬(Quick Sort) 참고 In-Place 알고리즘: 입력 배열 이외의 추가적인 메모리가 필요없는 알고리즘 On/Off-line 알고리즘: 정렬 중 추가로 데이터가 들어올 수 있/없는 알고리즘 Stable Sort: 중복된 키를 순서대로 정렬하는 정렬 알고리즘 1.선택 정렬(Selection Sort) Time Complexity - Best O(n2) - Avg O(n2) - Worst O(n2) In-Place Algorithm Off-line Algorithm Unstable Sort 주어진 배열에서 최소값을 찾아서 앞으로 갖다 놓는 알고리즘. 배열.. 유클리드 호제법(Euclidean Algorithm) "경북대학교 이시형 교수님의 수업을 듣고 작성했습니다." 학교에서 고급 문제 해결을 듣다가 새삼 매우 파워풀한 최대공약수 찾는 방법이라서 글을 쓴다 유클리드 호제법이란? 유클리드 호제법(-互除法, Euclidean algorithm) 또는유클리드 알고리즘은 2개의자연수또는 정식(整式)의최대공약수를 구하는알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되.. 이전 1 다음
