Algorithm22

• 

  [알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree) 신장 트리(Spanning Tree) 신장 트리는 연결 그래프의 부분 그래프이다. 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리이고, 모든 노드는 적어도 하나의 간선에 연결이 되어있어야 한다. 또한 이름에서 알 수 있듯이, 트리이므로 사이클이 존재해서는 안된다. 연결 그래프이므로, DFS(깊이 우선 탐색), BFS(너비 우선 탐색)를 이용하여 구현이 가능하다. 이 때 연결 그래프에는 하나의 신장트리 뿐만이 아닌 다양하게 존재할 수 있다. 이와 같은 연결 그래프가 있을 때, 나올 수 있는 신장 트리는 다음과 같다. 최소 신장 트리(Minimum Spanning Tree) 위에서 신장 트리에 대해 알아보았다. 그래프의 간선에 가중치가 있다면, 그것을 가중치 그래프라고 한다. 가중치 무방향 그래프에.. Algorithm 2022. 7. 21.

• 

  [알고리즘] 그래프 탐색(Graph Search) /BFS, DFS 그래프 그래프란 공집합이 아닌 노드(vertex, node)들의 유한 집합 V와 이 노드들을 연결하는 간선(edge)들의 집합 E로 구성된다. -> G = (V, E), |V| = n, |E| = m 트리는 그래프의 한 종류이다. 그래프에서 사이클이 존재하지 않으면 곧 트리이다. 노드의 차수: 노드에 연결된 간선의 수를 말하며, 방향 그래프에서는 진입 차수(indegree)와 진출 차수(outdegree)로 나누어 고려한다. 경로(path): 두 개의 노드를 연결하는 일련의 노드들 - 노드 a에서 b까지의 경로 a, v1, v2, . . . , vk, b가 존재하기 위해서는 간선 (a, v1), (v1, v2), . . ., (vn-1, vk), (vk, b)가 존재해야 한다. - 단순 경로: 한 노드를.. Algorithm 2022. 6. 2.

• 

  [알고리즘] 퀵 정렬(Quick Sort) - 랜덤 피벗 https://jjunsu.tistory.com/187 [알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 중앙으로 잡았을 때 퀵 정렬 퀵 정렬은 합병 정렬과 마찬가지로 분할 정복을 알고리즘이다. 가장 훌륭한 알고리즘 중 하나로 평균적으로 매우 빠른 수행 속도를 자랑한다. 시간복잡도는 평균적으로 O(nlogn)이고, 추 jjunsu.tistory.com https://jjunsu.tistory.com/188 [알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 첫 값으로 잡았을 때 https://jjunsu.tistory.com/187 [알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 중앙으로 잡았을 때 퀵 정렬 퀵 정렬은 합병 정렬과 마찬가지로 분할 정복을 알.. Algorithm 2022. 4. 14.

• 

  [알고리즘] 퀵 정렬(Quick Sort) - 피벗을 맨 끝 값으로 잡았을 때 https://jjunsu.tistory.com/187 [알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 중앙으로 잡았을 때 퀵 정렬 퀵 정렬은 합병 정렬과 마찬가지로 분할 정복을 알고리즘이다. 가장 훌륭한 알고리즘 중 하나로 평균적으로 매우 빠른 수행 속도를 자랑한다. 시간복잡도는 평균적으로 O(nlogn)이고, 추 jjunsu.tistory.com https://jjunsu.tistory.com/188 [알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 첫 값으로 잡았을 때 https://jjunsu.tistory.com/187 [알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 중앙으로 잡았을 때 퀵 정렬 퀵 정렬은 합병 정렬과 마찬가지로 분할 정복을 알.. Algorithm 2022. 4. 13.

• 

  [알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 첫 값으로 잡았을 때 https://jjunsu.tistory.com/187 [알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 중앙으로 잡았을 때 퀵 정렬 퀵 정렬은 합병 정렬과 마찬가지로 분할 정복을 알고리즘이다. 가장 훌륭한 알고리즘 중 하나로 평균적으로 매우 빠른 수행 속도를 자랑한다. 시간복잡도는 평균적으로 O(nlogn)이고, 추 jjunsu.tistory.com 퀵 정렬 왼쪽 피벗 저번에는 피벗을 중앙으로 잡았을 때를 알아봤었다. 이번에는 피벗을 맨 왼쪽으로 잡았을 때를 알아보도록 하자. 맨 앞의 원소를 pivot으로 하고, left를 pivot의 한칸 뒤 원소로 잡는다. 또한 right는 맨 뒤의 원소로 잡는다. 이제 left가 pivot보다 클 때까지 증가시키고, right는 pivot보다 작아.. Algorithm 2022. 4. 13.

• 

  [알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 중앙으로 잡았을 때 퀵 정렬 퀵 정렬은 합병 정렬과 마찬가지로 분할 정복을 알고리즘이다. 가장 훌륭한 알고리즘 중 하나로 평균적으로 매우 빠른 수행 속도를 자랑한다. 시간복잡도는 평균적으로 O(nlogn)이고, 추가적인 공간을 거의 사용하지 않는다. 실제 가장 많이 사용하는 정렬 알고리즘이기도 하다. 비교 기반 정렬 알고리즘은 O(nlogn)보다 빠를 수 없다. 퀵 정렬의 과정 1. 배열 안에 있는 요소 중 하나를 피벗(pivot)으로 고른다. 2. pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽으로 옮기고 pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮겨 분할한다. 3. 분할된 왼쪽 배열과 오른쪽 배열에서 다시 pivot을 정하고 재귀를 이용하여 더 이상 나눠지지 않을 때까지 분할을 반.. Algorithm 2022. 4. 10.

• 

  [알고리즘] 마스터 정리(도사 정리) 도사정리 재귀 관계씩으로 표현한 알고리즘의 동작 시간을 점근적으로 계산하여 간단하게 계산하는 방법으로, 재귀 알고리즘의 시간 복잡도를 결정해주는 블랙박스 툴이다. 재귀 알고리즘의 점화식(recurrence)으로부터 시간 복잡도를 결정하며, 표준 점화식으로만 가능하다. f(n)이 점근적으로 양이라는 말은 충분히 큰 n에 대해 f(n)이 양이라는 의미이다. 표준 점화식 3개의 파라미터로 구성된 대부분 재귀 알고리즘을 분석할 때 사용할 수 있는 점화식을 표준 점화식이라 한다. 여기서 a는 재귀호출의 수, b는 입력 크기가 줄어드는 정도, d는 일반 과정에서 소요되는 시간 복잡도의 지수이다. (a는 작을수록 좋으며, b는 클수록 좋다.) a, b, d는 모두 n과 독립적인 상수이고, d=0이라면 상수 시간을 뜻.. Algorithm 2022. 4. 9.

• 

  [알고리즘] 분할 정복(Divide & Conquer) 분할정복이란? 문제를 나눌 수 없을 때까지 나누어 각 작은 사례에 대한 해답을 얻고, 이들을 결합하여 원 문제에 대한 해답을 얻는 알고리즘이다. 시간복잡도는 O(nlogn)이며, 공간복잡도는 O(n)을 갖는다. 보통 다차시간 알고리즘의 성능을 개선하기 위해 사용한다. 분할정복의 전략 문제를 같은 유형의 작은 문제로 나눈다. (Divide) 작은 문제를 재귀적으로 해결한다. 해결 결과를 결합하여 원래의 문제에 대한 해결책을 제시한다. (Conquer) 합병 정렬(Merge Sort) 일반적인 방법으로 구현했을 때, 안정 정렬에 속한다. 구체적인 방법을 알아보면, 하나의 리스트를 두 개의 균등한 크기로 분할, 정렬한 후, 정렬된 두 리스트를 합하여 하나의 정렬된 리스트가 되게 하는 것이다. 합병 정렬의 단계.. Algorithm 2022. 4. 6.

• 

  [알고리즘] 재귀 함수, 꼬리 재귀 재귀 함수 재귀 함수는 어떠한 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 방식의 함수이다. 반복문을 사용하는 함수를 재귀 함수를 통해 구현하는 것이 가능하다. 재귀 함수는 보통 재귀적 사용이 자연스러울 때 사용된다. 재귀 함수의 장점 코드가 간결해지고, 가독성이 좋아진다. 변수 선언을 줄일 수 있다. 재귀 함수의 단점 시간 복잡도의 계산이 반복문에 비해 어렵다. 함수 호출이 많아지면 Stack Overflow의 위험이 있다. 호출할 때마다 메모리의 스택이 쌓여 성능에 문제가 생긴다. 재귀 함수의 예제 public static int factorial(int n) { if(n == 1) return 1; return n * factorial(n - 1); } 꼬리 재귀 알고리즘 재귀 함수의 단점을.. Algorithm 2022. 4. 6.

• 

  [알고리즘] Brute Force Algorithm(전수 조사 알고리즘) Brute Force Algorithm(전수 조사 알고리즘) 모든 경우를 다 조사해보는 방법이다. 처음부터 끝까지 계산을 해나가며 해답을 찾는데, 이는 경우의 수가 제한적일 경우에만 사용 가능하다. 하지만 컴퓨터가 계산을 해나가기 때문에 생각보다 범위가 크다. Brute Force의 종류 선형 구조 - 순차 탐색 비선형 구조 - DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 순차 탐색이 흔히 말하는 Brute Force라고 생각이 된다. DFS와 BFS는 후에 따로 설명을 하겠다. 전수 조사 방법 전수 조사는 보통 재귀적으로 구현한다. 하지만 모든 재귀는 반복문을 이용해 동일한 기능을 구현할 수 있으므로, 반복문을 통해서도 구현이 가능하다. 가능한 모든 경우의 수를 전부 조사하는 방법이라 단순한 접.. Algorithm 2022. 4. 4.