알고리즘/알고리즘 개념

[알고리즘] 에라토스테네스의 체(Sieve of Eratosthenes)

에라토스테네스의 체 (Sieve of Eratosthenes) ① 에라토스테네스의 체 (Sieve of Eratosthenes)이란? ▷ 소수 판별 알고리즘입니다.▷ 소수를 대량으로 빠르고 정확하게 구하는 방법입니다. ▷ 소수 : 양의 약수를 두 개만 가지는 자연수입니다.1234567public static boolean isPrimeNumber(int x) { int end = (int) Math.sqrt(x); for(int i = 2; i

2018. 5. 9. 11:37
알고리즘/알고리즘 개념

[알고리즘] 크루스칼 알고리즘(Kruskal Algorithm)

크루스칼 알고리즘 (Kruskal Algorithm) ① 크루스칼 알고리즘이란? ▷ 최소 비용 신장 트리를 찾는 알고리즘입니다.▷ 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다.▷ 최소 스패닝 트리(MST, Minimum Spanning Tree)를 찾음으로서 간선의 가중치의 합이 최솟값이 되도록 하는 알고리즘이라고도 할 수 있습니다. ▶ 스패닝 트리 : 그래프에서 일부 간선을 선택해서 만든 트리. ▶ 최소 스패닝 트리 : 스패닝 트리 중에 선택한 간선의 가중치의 합이 최소인 트리.▷ 변의 개수 E(간선), 꼭짓점의 개수 V(노드)라고 하면 이 알고리즘은 O (E log V )의 시간복잡도를 가진다. ▶ E(간선): 거리, 비용에 해당되며 선에 해당되는 부분입니다. ▶ V(노드):..

2018. 4. 28. 22:45
알고리즘/알고리즘 개념

[알고리즘] 유니온 파인드 (Union-Find)

유니온 파인드(Union-Find) ① 유니온 파인드란? ▷ 대표적 그래프 알고리즘으로 '합집합 찾기'라는 의미를 가지고 있습니다.▷ 상호 배타적 집합(Disjoint-set)이라고도 합니다.▷ 여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.▷ 2가지 연산으로 이루어져 있습니다. ▶ Find : x가 어떤 집합에 포함되어 있는지 찾는 연산 ▶ Union : x와 y가 포함되어 있는 집합을 합치는 연산 ② 그림으로 보는 Union-Find 위와 같이, 모두 연결되지 않고 각자 자기 자신만을 집합의 원소로 가지고 있을 때, 모든 값이 자기 자신을 가리키도록 만듭니다.i : 노드번호, P[i] : 부모 노드 번호 를 의미하며, 즉 자기 자..

2018. 4. 23. 18:10
알고리즘/알고리즘 개념

[알고리즘] 너비 우선 탐색 (Breadth-first search, BFS)

너비 우선 탐색(Breadth-first search, BFS) ① 너비 우선 탐색이란? ▷ 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘입니다.▷ 프림의 최소 스패닝 트리 알고리즘 등이 너비 우선 탐색을 골격으로 하고 있습니다. ▷ 위의 그림을 너비 우선 탐색을 사용하면 H0(단계) -》 H1(단계) -》H2(단계) 순으로 방문합니다.▷ k단계에 방문하는 정점들은 시작점으로부터 최단거리가 k입니다. (H0(단계) : 0단계, H1(단계) : 1단계, H2(단계) : 2단계)▷ 최단거리는 이동하는 데 필요한 최소 개수의 간선으로 보면됩니다.▷ 각 정점을 방문할 때마다 모든 인접 정점들을 검사합니다. 이 중 처음 보는 정점을 발견하면 방문 예정이라고 기록해 둔 뒤, 모든 인접 정점을 검사한 후..

2018. 4. 12. 21:42
알고리즘/알고리즘 개념

[알고리즘] 깊이 우선 탐색 (depth-first search, DFS)

깊이 우선 탐색(depth-first search, DFS) ① 깊이 우선 탐색이란? ▷ 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법▷ 깊이 우선 탐색은 탐색의 각 과정에서 가능한 한 그래프 안으로 '깊이' 들어가려고 시도하며, 막힌 정점에 도달하지 않는 한 뒤로 돌아가지 않습니다.▷ 깊이 우선 탐색의 중요한 특성은 더 따라갈 간선이 없을 경우 이전으로 돌아간다는 점입니다.▶ 깊이 우선 탐색 구현할 경우 : 스택(Stack)의 성질 활용(방문하는 순서대로 정점을 스택에 쌓고, 방문이 끝나면 스택에서 pop하는 형태로 구현) ※ DFS : 스택(Stack), BFS : 큐(Queue) 를 사용합니다.▶ 알고리즘 해결할 경우 : '재귀 호출'을 이용해 해결 (재귀 호출한 함수가 종료하면 호출한..

2018. 4. 12. 13:47
알고리즘/알고리즘 개념

[알고리즘] 완전탐색

글에 앞서... 재귀적 호출에 대한 개념을 먼저 설명드릴까합니다. 그 이유는 알고리즘에서 해당 호출방식을 자주활용하기 때문입니다. 재귀함수의 기본적인 이해 ** 재귀함수란?: 함수 내에서 자기 자신을 다시 호출하는 함수: 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수 ** 재귀함수 호출방식12345void RecursiveFunction(void){ printf("Recursive function example1 \n"); RecursiveFunction();}Colored by Color Scriptercs ※ 기저 사례 (base case)▷ 더 이상 쪼개지지 않는 가장 작은 작업, 즉 최소한의 작업에 도달했을 때 답..

2018. 4. 11. 21:46
알고리즘/알고리즘 개념

[알고리즘] 기본 정렬 알고리즘 (Sorting Algorithm)

정렬 알고리즘 개요 Name Best Worst (Big-O) Stable Memory 선택정렬 n² n² False 1 버블정렬 n n² True 1 삽입정렬 n n² True 1 합병정렬 nlogn nlogn True n 힙 정렬 nlogn 1 퀵 정렬 nlogn nlogn False 1 1. 선택정렬(Selection Sort) ① 개요 한번 순회를 하면서 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다.최소 선택 정렬(Min-Selection Sort) : 오름차순으로 정렬최대 선택 정렬(Max-Selection Sort) : 내림차순으로 정렬② 기본 로직 정렬 되지 않은 인덱스의 맨 앞부터, 그 이후의 배열값 중 가장 작은 값을 찾아간다.가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔..

2018. 3. 21. 20:20
알고리즘/알고리즘 개념

[알고리즘] 빅오 표기법(Big-O Notation), 시간복잡도, 공간복잡도

시간복잡도와 공간복잡도 시간복잡도 ▷ 속도에 해당하는 알고리즘의 수행시간 분석결과 공간복잡도 ▷ 메모리 사용량에 대한 분석결과 ※ 일반적으로는 중요도는 실행속도가 메모리 사용량보다 중요하다.※ 알고리즘의 성능을 판단하는 데 있어서 중요한 것은 '최악의 경우'이다. 빅-오 표기법(Big-O Notation) ▷ 빅-오는 시간 복잡도 T(n) 에서 가장 영향력이 큰 부분을 따지는 것이다.▷ 데이터 수의 증가에 따른 연산횟수의 증가형태를 나타내는 표기법이다. ex) T( n² + 2n + 1 ) 일 경우 빅-오 표기법으로는 O( n²) 이 된다. 빅-오 표기법의 성능(수행시간, 연산횟수) O( 1) < O( log n)

2018. 2. 1. 15:28