Computer Science/Algorithm4 정렬 알고리즘 - 퀵 정렬(Quick Sort) 수많은 정렬 알고리즘 중 Quick Sort에 대해서 알아보려고 합니다. 순서는 다음과 같습니다. 특징 동작 방식 구현(Java) 장단점 특징 Quick Sort의 핵심 요소는 2가지로 pivot과 분할 정복입니다. * 분할 정복: 큰 문제를 작은 2개의 문제로 분리하여 각각 해결하고, 병합하여 원래의 큰 문제를 해결하는 방법 Quick Sort는 불안정 정렬에 속합니다. 분할 정복을 활용하는 Merge Sort와는 다르게 배열을 비균등하게 분할합니다.(pivot을 활용하기 때문) 동작 방식 배열에서 임의의 위치에서 pivot(사용자가 선택한 임의의 값)을 선택. 선택된 pivot을 기준으로 앞쪽에는 pivot보다 작은 숫자들이, 뒷쪽에는 pivot보다 큰 숫자들이 오도록 변경해주고, 배열을 둘로 분할... 2021. 10. 2. 탐색 알고리즘 - DFS(깊이 우선 탐색) DFS는 Depth First Search의 줄임말로 BFS의 반대 개념이라고 생각하면 된다 (BFS 설명) Tree, Graph에서 한 개 가지의 leaf node까지 탐색하고 다시 돌아가 다른 가지를 탐색하는 방식이다. 대표적으로 백트래킹 기법에 사용된다 아래 Tree 구조에서의 탐색을 예로 들면 root node(최상단의 node)부터 시작하여 가장 좌측의 가지를 끝까지 탐색하고(3번 노드까지) 돌아온 후 중앙의 가지를 동일한 방식으로 탐색한다 구현 방식에는 주로 재귀 호출이 사용되고 스택 자료구조를 사용할 수 도 있다 재귀 호출을 활용한 구현은 node를 하나씩 지나갈 때마다 새로운 DFS를 다시 시작하는 것이고 스택을 활용한 구현은 현재 위치 node와 연결된 node를 stack에 넣고 진행하.. 2020. 11. 8. 탐색 알고리즘 - BFS(넓이 우선 탐색) 다양한 탐색 알고리즘 중 하나인 BFS를 알아보자 BFS는 Breadth First Search의 줄임말로 DFS의 반대 개념이라고 생각하면 된다 (DFS 설명) 아래 트리구조를 보자 DFS가 root node(최상단의 node)부터 시작하여 좌측 끝 3번 노드까지 탐색하고 중앙 4번 노드를 탐색한다반면 BFS는 root node에 바로 맞닿아있는 2,3,4번 노드를 순차적으로 탐색한다 탐색 순서를 알아봤으니 BFS 구현의 특징을 살펴보자 1. 자료구조 Queue를 사용한다 -> 1번 node와 맞닿아있는 2,3,4번 노드를 모두 큐에 넣은 후 큐에서 2번 노드를 뽑고 2번의 자식 노드들을 큐에 담는다 이런 간단한 로직을 반복하면 된다. 2. 재귀문을 사용할 필요 없이 반복문 하나로 탐색이 가능하다. w.. 2020. 9. 15. 에라토스테네스의 체 - 소수 구하기 먼저 소수(Prime Number)에 대해 이해하고 넘어가야겠다. 소수는 1을 제외한 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 즉, 13은 1 X 13 말고는 성립하는 식이 없기 때문에 소수이다. 이 소수를 구하는 가장 최적화된 방법으로 알려진 것이 바로 에라토스테네스의 체이다. 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수 판정법이다. 쉽고 빠른 이해를 위해 간단한 예시와 함께 알아보자. Q) 120까지의 자연수 중 소수를 구하라. 알고리즘은 아주 간단하다. 2부터 120까지 순차적으로 탐색하며 자신의 1,2,3..... 배인 수들을 삭제한다. 이때 이미 삭제된 숫자는 탐색할 필요가 없다. 즉, 아래 그램처럼 탐색 순서는 2,3,5,7,11.... 2020. 8. 23. 이전 1 다음
