Algorithm (5) 썸네일형 리스트형 Quick Sort 퀵 정렬 (C++) Quick Sort 퀵 정렬 (C++) Counting Sort란? 기준 데이터(Pivot)을 설정하고 그 기준 보다 큰 데이터와 작은 데이터의 위치를 바꾸어가며 정렬하는 알고리즘 분할 정복 기법을 활용한다 불안정 정렬 순서 1. 피봇의 위치를 설정한다. 2. 분할 : 피봇을 토대로 데이터를 정렬해나간다. 정렬이 끝나면 피봇의 앞은 피봇보다 작은 값들이, 피봇의 뒤는 피봇보다 큰 값들이 오게된다. 3. 2의 과정으로 쪼개진 영역에 대해 재귀적으로 다시 정렬을 수행한다. 이를 애니메이션으로 나타내면 다음과 같다. 시간복잡도 평균 시간 복잡도 : O(NlogN) 이미 정렬이 되어있는 상태일 때 최악의 경우가 되며, 이 때의 시간 복잡도는 O(N^2) Code #include using namespace st.. Selection Sort 삽입 정렬 (C++) Selection Sort 삽입 정렬 Selection Sort란? 2번째 원소부터 시작하여 앞쪽의 원소들과 비교하여 삽입 위치를 특정한 후, 원소를 뒤로 옮기고 지정된 자리에 삽입하는 알고리즘 선택 정렬에 비해 효율적이다(최선의 경우 O(N)) 제자리 정렬, 안정 정렬 기준 원소의 앞쪽은 이미 정렬되어 있다고 가정한다. 순서를 살펴보면, 2번째 위치의 값을 tmp에 저장한다. 앞쪽의 원소들과 비교하며 위치를 특정하고 삽입한다. 다음 위치 값을 tmp에 저장하고 반복한다. 이를 애니메이션으로 표현한다면 다음과 같다. 시간복잡도? 최악 - O(N^2) 최선 - O(N) Code #include using namespace std; int main(void) { int arr[5] = { 5,2,3,7,4 .. Bubble Sort 버블 정렬 (C++) Bubble Sort 버블 정렬 Bubble Sort란? 서로 인접한 두 원소의 대소를 비교 하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 안정 정렬(Stable sort) 배열 내부에서 swap이 발생하기 때문에 별도 메모리 공간 불필요 = 제자리 정렬(in-place sorting) 순서를 살펴보면 [ X 회전 ] 0번째 원소와 1번째 원소를 비교하며 큰수를 뒤로 보낸다. 이를 N-X번째 원소까지 반복한다. 1번을 수행하고 나면 가장 큰 값이 마지막 위치로 이동된다. 1,2를 반복한다. 이를 애니메이션으로 표현한다면 다음과 같다. 시간복잡도? O(N^2) Code #include using namespace std; int main(void) { int arr[5] = {19,2,4,1.. Queue 큐 ( JAVA ) Queue 큐 Queue 란 ? 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식을 말한다. 스택과는 반대되는 개념이다. 큐의 탐색에는 O(N) 만큼의 시간이 걸리고 삽입/삭제에는 O(1) 만큼의 시간이 소요된다. 구현 Queue를 직접 구현해본다. 배열과 리스트를 이용할 수 있는데 리스트로 큐의 삽입과 삭제를 구현해보겠다. 먼저 큐를 구현하기 위해 Node 클래스를 생성한다. static class Node{ int val; Node next; public Node(int val) { this.val = val; next = null; } } static Node head; 다음으로는 Node 클래스를 활용하여 삽입을 구현해보자 삽입을 하는 메소드 .. Stack 스택 (JAVA) 간단 개념 1. 스택은 가장 나중에 들어간 요소가 가장 먼저 나오게 되는 구조를 가진다(Last In First Out) 2. 배열, 리스트를 이용해서 구현할 수 있다. 구현 명세 [배열스택] 1. 삽입 2. 삭제 [링크드리스트스택] 1. 삽입 2. 삭제 구현 1. 배열 스택 Step 1. Push - 삽입하기 전에 스택 배열을 생성한다. static int[] arrStack; - top위치를 저장할 변수를 생성한다. - 배열의 인덱스가 0에서 시작하기 때문에 빈 스택을 나타내려면 -1로 한다. static int top = -1; // index 0부터라서 -1해야 빈 스택 - push 메소드를 작성한다. - 배열 스택은 크기가 한정되어 있어서 크기가 넘어가면 메시지를 출력하게 했다. - 삽입시 to.. 이전 1 다음
