짱아의 개발 기록장

힙 정렬은 개인적으로 heap구조를 구현해야하기 때문에 어려운? 알고리즘 중 하나라고 생각한다. 혼자서 짜보려고 노력해봤지만.. 한계를 느껴 다른 분의 해설을 보고 구현해보았다. 나는 주어진 배열을 힙의 형태로 만들어주는 방식으로 정렬을 했다. *핵심 포인트* 1) 주어진 배열을 위->아래 순으로 자식이 부모보다 큰 경우를 처리해준다. 2) 아래->위로 각 배열의 원소들을 루트 노드로 올려 자식들 중 큰 값이랑 교한해주는 힙 구조로 정렬을 해나갔다. *시간 복잡도* Best Avg Worst O(nlog(n)) O(nlog(n)) O(nlog(n)) 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 ..

합병정렬의 핵심은 left, mid, right값을 잡고 분할(divide)+정복(conquer)+합병(combine)해주는 과정이다. 분할(divide)는 merge_sort()함수로 구현해줬고 정복(conquer)는 merge()함수를 통해 구현했습니다. *시간복잡도* Best Avg Worst O(nlog(n)) O(nlog(n)) O(nlog(n)) 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 // 합병 정렬 구현(오름차순) #include using..

삽입정렬은 idx기준으로 더 이전의 idx값들과 비교하면서, 기준값들보다 더 큰 값이 있다면 자리를 바꿔주는 형태로 진행된다. 삽입정렬은 최선의 경우에 n번만 비교를 하게 되므로 ex) 1, 2, 3, 4 ,5 -> O(n)의 시간복잡도를 가진다. O(n^2)의 시간복잡도를 가지는 sorting algorithm 중에서는 가장 빠르다. *시간복잡도* Best Avg Worst O(n) O(n^2) O(n^2) 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 // 삽입 정렬 구현(오름차순) #include using namespace std; int arr[5] = {8, 5, 6, 2, 4}; void ..

idx값을 기준으로, idx+1부터 배열 끝까지 중 가장 작은 값과 idx값을 비교하여 기준값이 더 크다면 위치를 바꿔주면 된다. 즉, idx값을 저장해놓고 바꾸는 식으로 진행된다. *시간복잡도* Best Avg Worst O(n^2) O(n^2) O(n^2) 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 // 선택 정렬 구현(오름차순) #include #include using namespace std; // 초기 배열 상태 int arr[5] = {9, 6, 7, 3, 5}; void selection_sort(int arr[], int size) {..

0~n-1까지 인접한 값들을 비교하면서, 크기가 더 큰 원소를 뒤로 보내주는 연산을 (원소의 개수-1)만큼 반복해주면 된다. 왜? (원소의 개수-1)만큼 반복해주나? 5, 4, 3, 2, 1 처럼 모든 원소의 자리를 바꿔야 하는 경우에는 총 4번을 연산하면 1, 2, 3, 4, 5와 같은 형태로 바꿀 수 있다. 즉, 최악의 경우까지 고려하여 (원소의 개수-1)만큼 반복 연산해주면 오름차순으로 정렬할 수 있다. *시간복잡도* Best Avg Worst O(n^2) O(n^2) O(n^2) 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 // 버블 정렬 구현(오름차순) #include using namespace..

일반적인 큐처럼 동작하는 코드를 오직 배열만을 사용하여 구현해보았다. insert, del, empty, print함수로 나누어 구현했다. 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 // 큐 구현하기 #include using namespace std; int queue[100] = {0, }; int n = 100; // 최대 크기 int front = -1, rear = -1; void insert(int data) { if(rear == n-1){ // queue배열이 꽉 찬 경우 ..

일반적인 스택처럼 동작하는 코드를 오직 배열만을 사용하여 구현해보았다. push, pop, empty, top함수로 나누어 구현했다. 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 // 스택 구현하기 /* 일반적인 스택을 구현하시오. (push(), pop(), empty() 함수 구현) ex) 1, 2, 3, 4 -> 4, 3, 2, 1 */ #include using namespace std; int n, m; int stack[10002] = {0, }; int top = -1; // 가장 위에 부분을 가리키고 있는 변수 bool e..

큐를 이용하여 스택을 구현해보려고 합니다. 앞서 포스팅한 '스택으로 큐 구현하기'와 마찬가지로 https://jungahshin.tistory.com/24?category=830625 스택으로 큐 구현하기(c++) 오늘은 스택으로 큐를 구현해보려고 합니다. 총 2개의 스택을 사용하여 큐를 구현할 수 있습니다. 저는 이해를 위해 다음 블로그를 참조하였고 따로 c++로 코드를 작성해보았습니다. https://tdm1223. jungahshin.tistory.com 총 2개의 큐를 사용하여 스택을 구현할 수 있습니다. 이해를 위해 다음 블로그를 참고하였고 따로 c++코드를 작성해보았습니다. push, pop, isEmpty함수를 구현했습니다. 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 13 1..