728x90 반응형 Algorithm/Algorithm16 [Algorithm] 최단 경로 탐색(Shortest Path) - 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm) 개요 ◎ 플로이드 워셜 알고리즘이란? ◎ 그림 예시 ◎ 구현 코드 (Java) ◎ 시간 복잡도 ◎ 다익스트라 알고리즘과 비교 안녕하세요. J4J입니다. 이번 포스팅은 플로이드 워셜 알고리즘에 대해 적어보는 시간을 가져보려고 합니다. 플로이드 워셜 알고리즘이란? 플로이드 워셜 알고리즘은 정점들 간의 최단 경로를 탐색하기 위한 알고리즘 기법으로 시작 정점과 도착 정점 외에도 중간 정점을 선택하여 최소 거리를 탐색하는 방법을 사용합니다. 예를 들어 A, B, C, D, E 정점이 있다고 가정하면 다음과 같이 탐색을 합니다. 1-1. 중간 정점을 A로 선택합니다. 1-2. 모든 정점들 간의 거리를 중간 지점인 A를 거쳐서 가는 거리와 비교하여 최솟값들을 저장합니다. 2-1. 중간 정점을 B로 선택합니다. 2-2.. 2021. 2. 1. [Algorithm] 최단 경로 탐색(Shortest Path) - 다익스트라 알고리즘(Dijkstra Algorithm) 개요 ◎ 다익스트라 알고리즘이란? ◎ 그림 예시 ◎ 구현 코드 - 인접 행렬 (Java) ◎ 시간 복잡도 - 인접 행렬 ◎ 구현 코드 - 힙 (Java) ◎ 시간 복잡도 - 힙 안녕하세요. J4J입니다. 이번 포스팅은 다익스트라 알고리즘에 대해 적어보는 시간을 가져보려고 합니다. 다익스트라 알고리즘이란? 다익스트라 알고리즘은 그래프에서 정점 간의 최단 경로를 탐색하기 위해 사용되는 알고리즘 기법으로 시작 정점에서부터 다른 정점들까지 도달하기 위해 필요한 최소 거리를 찾기 위해 사용됩니다. 다익스트라를 이용해 최단 경로를 구하는 식은 D[i][j] = min(D[i][j], D[i][k] + D[k][j])이고 이를 이용해 최단 경로를 구하는 방법은 다음과 같습니다. 예를 들어 A, B, C, D, E 정.. 2021. 1. 31. [Algorithm] MST - 크루스칼 알고리즘(Kruskal Algorithm) 개요 ◎ 크루스칼 알고리즘이란? ◎ 그림 예시 ◎ 구현 코드 (Java) ◎ 시간 복잡도 ◎ 특징 안녕하세요. J4J입니다. 이번 포스팅은 크루스칼 알고리즘에 대해 적어보는 시간을 가져보려고 합니다. 크루스칼 알고리즘이란? 크루스칼 알고리즘은 대표적인 MST 구현 알고리즘 중 하나로 정점들 간의 연결된 길(간선)의 가중치를 작은 순서대로 선택하며 MST를 만드는 기법입니다. 예를 들어 A, B, C, D, E 정점이 있다고 가정해보겠습니다. A ↔ C 가중치: 3 A ↔ D 가중치: 5 B ↔ C 가중치: 4 B ↔ D 가중치: 4 C ↔ E 가중치: 2 D ↔ E 가중치: 1 일때 다음과 같은 순서로 가중치를 선택합니다. 1-1. 가중치가 1로 가장 작은 D ↔ E 간선을 임의로 선택합니다. 1-2. .. 2021. 1. 30. [Algorithm] MST - 프림 알고리즘(Prim Algorithm) 개요 ◎ 프림 알고리즘이란? ◎ 그림 예시 ◎ 구현 코드 - 인접 행렬 (Java) ◎ 시간 복잡도 - 인접 행렬 ◎ 구현 코드 - 힙 (Java) ◎ 시간 복잡도 - 힙 ◎ 특징 안녕하세요. J4J입니다. 이번 포스팅은 프림 알고리즘에 대해 적어보는 시간을 가져보려고 합니다. 프림 알고리즘이란? 프림 알고리즘은 대표적인 MST 구현 알고리즘 중 하나로 정점을 기준으로 갈 수 있는 가중치가 가장 작은 길(간선)을 선택한 뒤 다음 정점을 방문하며 MST를 만드는 기법입니다. 예를 들어 A, B, C, D, E 정점이 있다고 가정해보겠습니다. A ↔ C 가중치: 3 A ↔ D 가중치: 5 B ↔ C 가중치: 4 B ↔ D 가중치: 4 C ↔ E 가중치: 2 D ↔ E 가중치: 1 이고 A 정점에서 출발한다면.. 2021. 1. 27. [Algorithm] 최소 신장 트리(MST, Minimum Spanning Tree) 개요 ◎ 최소 신장 트리란? ◎ 신장 트리란? ◎ 그림 예시 ◎ 신장 트리 특징 ◎ 최소 신장 트리 구현 알고리즘 안녕하세요. J4J입니다. 이번 포스팅은 최소 신장 트리에 대해 적어보는 시간을 가져보려고 합니다. 최소 신장 트리란? 최소 신장 트리는 신장 트리들 중 가중치의 합이 가장 작은 신장 트리를 의미합니다. 여기서 가중치라고 하는 것은 그래프에서 길(간선)을 지나기 위해 지불되는 값이라고 생각하면 됩니다. 예를 들어 A에서 출발하여 C에 도착한다고 가정해 보겠습니다. A→B 가중치: 5 B→C 가중치: 8 이면 A→C로 이동하기 위한 가중치의 합은 13이 되는 것입니다. 신장 트리란? 신장 트리란 최소한의 길(간선)을 이용하여 모든 정점들을 이동 가능하도록 만들어진 트리입니다. 따라서 하나의 그.. 2021. 1. 24. [Algorithm] 너비 우선 탐색(BFS, Breadth First Search) 개요 ◎ 너비 우선 탐색이란? ◎ 사용 목적 ◎ 그림 예시 ◎ 구현 코드 - 인접 행렬 (Java) ◎ 구현 코드 - 인접 리스트 (Java) ◎ 시간 복잡도 안녕하세요. J4J입니다. 이번 포스팅은 너비 우선 탐색(BFS)에 대해 적어보는 시간을 가져보려고 합니다. 너비 우선 탐색이란? 너비 우선 탐색이란 그래프 탐색 기법 중 하나로 한 번 탐색을 시작한 정점에 연결된 모든 정점을(깊이가 같은 정점) 탐색한 뒤 다른 깊이에 있는 정점을 탐색하는 기법입니다. 추가적으로 그래프 탐색에 대해서도 설명드리면 한 정점을 시작으로 다른 존재하는 모든 정점을 한 번씩 방문하는 탐색을 그래프 탐색이라고 합니다. 사용 목적 너비 우선 탐색의 사용 목적은 시작 정점부터 다른 정점까지의 최단 거리를 구하기 위해 사용됩니다.. 2021. 1. 21. [Algorithm] 깊이 우선 탐색(DFS, Depth First Search) 개요 ◎ 깊이 우선 탐색이란? ◎ 사용 목적 ◎ 그림 예시 ◎ 구현 코드 - 인접 행렬 (Java) ◎ 구현 코드 - 인접 리스트 (Java) ◎ 시간 복잡도 안녕하세요. J4J입니다. 이번 포스팅은 깊이 우선 탐색(DFS)에 대해 적어보는 시간을 가져보려고 합니다. 깊이 우선 탐색이란? 깊이 우선 탐색이란 그래프 탐색 기법 중 하나로 한 번 탐색을 시작한 정점의 최대 깊이까지 탐색을 한 뒤 같은 높이에 있는 다른 정점을 탐색하는 기법입니다. 그래프 탐색에 대해서도 설명을 드리자면 한 정점을 시작으로 다른 존재하는 모든 정점을 한 번씩 방문하는 탐색을 그래프 탐색이라고 합니다. 사용 목적 깊이 우선 탐색을 사용하는 목적은 모든 정점을 탐색하여 원하는 값이 존재하는지 찾기 위해 사용합니다. 대표적인 예는 .. 2021. 1. 18. [Algorithm] 이분탐색(Binary Search) 개요 ◎ 이분 탐색이란? ◎ 구현 코드 (Java) ◎ 그림 예시 ◎ 사용 목적 ◎ 시간 복잡도 ◎ 조건 ◎ 자바에서 제공하는 메서드 안녕하세요. J4J입니다. 이번 포스팅은 이분 탐색에 대해 적어보는 시간을 가져보려고 합니다. 이분 탐색이란? 이분 탐색이란 여러 탐색 기법들 중 하나로 탐색하는 구간을 두 부분으로 나누어 탐색하는 기법입니다. 탐색을 위해 탐색하는 구간을 두 부분으로 나누지만 실질적으로 탐색은 한 구간만 선택하여 탐색하고 이 행동을 반복하여 찾고자 하는 값을 도출해 내는 방식입니다. 구현 코드 (Java) package search; public class BinarySearch { public static void main(String[] args) { int[] intArray = n.. 2021. 1. 17. [Algorithm] 부분집합(Subset) 개요 ◎ 부분집합이란? ◎ 구현코드 (Java) ◎ 시간 복잡도 안녕하세요. J4J입니다. 이번 포스팅은 부분집합에 대해 적어보는 시간을 가져보려고 합니다. 부분집합이란? 부분집합은 고등학교 수학 시간 때 배웠던 것으로 집합 A와 집합 B가 있을 때 집합 A에 존재하는 모든 원소들이 집합 B에 존재하면 집합 A는 집합 B의 부분집합(A ⊆ B)이라고 합니다. 단순하게 생각하면 집합 B가 집합 A를 포함하고 있다라고도 말할 수 있습니다. 예를 들어 한 집합 안에 {A, B, C}라는 값이 들어있다면 이 집합의 부분집합은 다음과 같습니다. 1. ∅ (공집합) 2. {A} 3. {B} 4. {C} 5. {A, B} 6. {A, C} 7. {B, C} 8. {A, B, C} 집합의 개수가 n개가 있다고 할 때 .. 2021. 1. 14. [Algorithm] 조합(Combination) 개요 ◎ 조합이란? ◎ 구현코드 (Java) ◎ 시간 복잡도 안녕하세요. J4J입니다. 이번 포스팅은 조합에 대해 적어보는 시간을 가져보려고 합니다. 조합이란? 조합은 고등학교 수학 시간에 배웠던 것으로 개념을 정의해보면 서로 다른 n개 중에서 순서를 생각하지 않고 r개를 택하는 경우의 수를 의미합니다. 대표적으로 4명의 학생 중 2명의 회장을 뽑는 회장 뽑기 문제가 있습니다. (1명은 회장, 1명은 부회장이면 순열) ※ 순열에 대해 궁금하시면? [Algorithm] 순열(Permutation) 4명의 학생을 각각 A, B, C, D라고 가정할 때 2명의 회장이 뽑히는 경우를 구해보면 다음과 같습니다. 1. A, B 2. A, C 3. A, D 4. B, C 5. B, D 6. C, D 순열을 구하는 공.. 2021. 1. 13. [Algorithm] 순열(Permutation) 개요 ◎ 순열이란? ◎ 구현코드 (Java) ◎ 시간 복잡도 ◎ 번외 안녕하세요. J4J입니다. 이번 포스팅은 순열에 대해 적어보는 시간을 가져보려고 합니다. 순열이란? 순열은 고등학교 수학 시간에 배웠던 것으로 개념을 정의해보자면 서로 다른 n개 중에서 순서를 생각하며 r개를 택하는 경우의 수를 의미합니다. 대표적으로 n명의 사람들이 r명을 택하여 일렬로 줄을 서는 경우의 수를 구하라고 하는 것이 있습니다. 예를 들어 3명(A, B, C) 중 2명을 택하여 일렬로 줄을 세운다고 하면 경우는 다음과 같습니다. 1. A B 2. A C 3. B A 4. B C 5. C A 6. C B 순열을 구하는 공식도 다음과 같이 있습니다. 위의 예시를 공식에 대입해보면 P(3) = 3! / (3-2)!으로 6이라는 .. 2021. 1. 11. [Algorithm] 정렬 - 퀵 정렬(Quick Sort) 안녕하세요. J4J입니다. 이번 포스팅은 정렬 알고리즘 중 퀵 정렬에 대해 적어보는 시간을 가져보려고 합니다. 퀵 정렬이란? 퀵 정렬은 분할 정복법(Divide and Conquer)이 사용되는 정렬 방법으로 pivot이라는 리스트 안의 한 원소를 기준으로 좌측에는 pivot보다 작은 원소, 우측에는 pivot보다 큰 원소로 분할시켜 정렬하는 방식을 사용합니다. 예를 들어 길이가 5인 배열에 원소 값이 {3, 1, 15, 11, 7}이 저장되어 있다면 정렬되는 방식은 다음과 같습니다. 1-1. 정복 단계를 거치며 pivot 값을 구합니다. 1-2. pivot값은 7이 되며 pivot을 기준으로 작은 원소인 {3, 1}, 큰 원소인 {11, 15}로 분할시킵니다. 2-1. {3, 1} 배열에 정복 단계를 .. 2021. 1. 10. [Algorithm] 정렬 - 합병 정렬(Merge sort) 안녕하세요. J4J입니다. 이번 포스팅은 정렬 알고리즘 중 합병 정렬에 대해 적어보는 시간을 가져보려고 합니다. 합병 정렬이란? 합병 정렬은 분할 정복법(Divide and Conquer)이 사용되는 정렬 방법으로 저장되어 있는 값들을 모두 분할시킨 뒤 정복을 통해 결합할 때 값들을 정렬해주는 방식을 사용합니다. 예를 들어 길이가 5인 배열이 있다고 가정하면 정렬되는 방식은 다음과 같습니다. (길이가 같은 값은 `를 추가시켜 구분합니다.) 1-1. 길이가 5인 배열을 반으로 나누어 길이가 3, 2인 배열로 분할 시킵니다. 2-1. 길이가 3이 된 배열을 반으로 나누어 길이가 2`, 1인 배열로 분할시킵니다. 2-2. 길이가 2가 된 배열을 반으로 나누어 길이가 1`, 1``인 배열로 분할시킵니다. 3-1.. 2021. 1. 9. [Algorithm] 정렬 - 삽입 정렬(Insertion Sort) 안녕하세요. J4J입니다. 이번 포스팅은 정렬 알고리즘 중 삽입 정렬에 대해 적어보는 시간을 가져보려고 합니다. 삽입 정렬이란? 삽입 정렬은 매 회전마다 현재 인덱스의 값이 왼쪽에 존재하는 인덱스의 값보다 작을 경우 위치를 바꾸며 정렬해주는 방식입니다. 하지만 작지 않을 경우에는 현재 턴을 종료하여 다음 턴으로 넘어갑니다. 왜냐하면 이미 지나온 인덱스들은 정렬이 되어있어 특정 인덱스에서 값이 작지 않다면 왼쪽에 존재하는 나머지 값들과 비교했을 때도 작지 않기 때문입니다. 예를 들어 길이가 5인 배열이 있다고 가정하면 정렬되는 방식은 다음과 같습니다. 1-1. 1번 인덱스의 값이 0번 인덱스의 값보다 작을 시 위치를 변경합니다. 2-1. 2번 인덱스의 값이 1번 인덱스의 값보다 작을 시 위치를 변경합니다... 2021. 1. 9. [Algorithm] 정렬 - 선택 정렬(Selection Sort) 안녕하세요. J4J입니다. 이번 포스팅은 정렬 알고리즘 중 선택 정렬에 대해 적어보는 시간을 가져보려고 합니다. 선택 정렬이란? 선택 정렬은 매 회전마다 인덱스를 탐색하여 최솟값을 처음부터 순서대로 집어넣는 정렬 방식입니다. 예를 들어 길이가 5인 배열이 있다고 가정하면 정렬되는 순서는 다음과 같습니다. 1-1. 0번 인덱스를 임시 최솟값으로 지정합니다. 1-2. 1~4번 인덱스를 탐색하여 임시 최솟값보다 작은 게 존재할 시 0번 인덱스와 위치를 변경합니다. 2-1. 1번 인덱스를 임시 최솟값으로 지정합니다. 2-2. 2~4번 인덱스를 탐색하여 임시 최솟값보다 작은 게 존재할 시 1번 인덱스와 위치를 변경합니다. . . . 4-1. 3번 인덱스를 임시 최솟값으로 지정합니다. 4-2. 4번 인덱스를 탐색하.. 2021. 1. 6. [Algorithm] 정렬(Sorting) 안녕하세요. J4J입니다. 이번 포스팅은 정렬 알고리즘에 대해 적어보는 시간을 가져보려고 합니다. 정렬 알고리즘이란? 정렬 알고리즘은 배열 등에 저장되어 있는 요소들을 일정한 순서대로 정렬(재 배치) 하는 것을 의미합니다. 예를 들어 배열에 저장되어 있는 정수 값들을 크기가 작은 순서대로 정렬할 때 사용되거나(오름차순 이라고도 하죠) 또는 알파벳으로 이루어진 문자열들을 사전 순서대로 정렬할 때 사용될 수 있습니다. 정렬 알고리즘 종류에는 선택 정렬(selection sort), 삽입 정렬(insertion sort), 퀵 정렬(quick sort), 합병 정렬(merge sort) 외에도 많은 종류들이 존재합니다. 이런 정렬 들 중 퀵 정렬이 가장 흔하게 사용되고는 하는데 그 이유는 정렬을 할 때 가장 .. 2021. 1. 3. 이전 1 다음 728x90 반응형
