Algorithm/Base (8) 썸네일형 리스트형 Quick Sort 퀵 정렬 (C++) Quick Sort 퀵 정렬 (C++) Counting Sort란? 기준 데이터(Pivot)을 설정하고 그 기준 보다 큰 데이터와 작은 데이터의 위치를 바꾸어가며 정렬하는 알고리즘 분할 정복 기법을 활용한다 불안정 정렬 순서 1. 피봇의 위치를 설정한다. 2. 분할 : 피봇을 토대로 데이터를 정렬해나간다. 정렬이 끝나면 피봇의 앞은 피봇보다 작은 값들이, 피봇의 뒤는 피봇보다 큰 값들이 오게된다. 3. 2의 과정으로 쪼개진 영역에 대해 재귀적으로 다시 정렬을 수행한다. 이를 애니메이션으로 나타내면 다음과 같다. 시간복잡도 평균 시간 복잡도 : O(NlogN) 이미 정렬이 되어있는 상태일 때 최악의 경우가 되며, 이 때의 시간 복잡도는 O(N^2) Code #include using namespace st.. Counting Sort 계수 정렬 (C++) Counting Sort 계수 정렬 Counting Sort란? 정렬하는 숫자가 특정한 범위 내에 있을 때 별도의 리스트를 활용하여 원소가 등장한 횟수를 기록하고, 횟수만큼 해당 숫자를 출력해준다. 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능 메모리가 낭비될 수 있음 순서를 살펴보면 최대값을 담을 수 있도록 사이즈를 1 크게 잡고 리스트를 생성한다. 카운팅한다. 카운트 횟수 만큼 출력한다. 시간복잡도? O(N+K) , N은 데이터 개수 K는 최대값의 크기 Code #include #include #define ARRAYSIZE(A) sizeof(A)/sizeof((A)[0]) using namespace std; int main(void) { int arr[5] = { 4,.. 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.. Selection Sort 선택 정렬 (JAVA) Selection Sort 선택 정렬 선택 정렬이란? 원소들 중 가장 작은(혹은 큰) 원소를 찾아 맨 앞에서부터 교환하는 알고리즘 순서를 살펴보면, 주어진 리스트 중 최소값(혹은 최대값)을 찾는다. 그 값을 맨 앞(혹은 맨 뒤) 값과 교체한다. 맨 처음(혹은 맨 뒤) 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 이를 애니메이션으로 표현한다면 다음과 같다. 시간복잡도? O(N^2) 프로세스 선택 정렬이 어떤 프로세스로 이루어지는 지는 위에서 알아보았다. 그렇다면 단계 별로 진행되는 모습을 자세히 살펴보자. 다음과 같은 배열이 있다고 가정한다. 선택 정렬은 최소값을 기준 or 최대값을 기준 중 하나를 선택하면 된다. 여기서는 최대값을 기준으로 진행해보겠다. 가장 마지막 원소를 Last라고 한다면, L.. 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 클래스를 활용하여 삽입을 구현해보자 삽입을 하는 메소드 .. 이전 1 2 다음
