힘내 지지마: 백엔드 개발일지

지금까지 배운 정렬 알고리즘 중 비교적 빠른 정렬 알고리즘은 O(N*logN)으로 아래 세 가지가 있었다. -퀵 정렬(Worst Case -> N*N) -병합 정렬 -힙 정렬 하지만, 더 빠르게 정렬해야한다면?? 그래서 나온 것이 계수정렬(Counting Sort)이다. 하지만, 이 계수 정렬도 한계점이 존재한다. 특징 데이터의 크기가 제한적으로 '범위 조건'이 있는 경우에 한해서 사용 가능 O(N) 지난 정렬 알고리즘들 처럼 swap을 하는 것이 아닌, 데이터의 크기를 기준으로 Counting하는 방식 사용 -> O(N)의 이유 매우 간단. 6이하의(범위 조건) 자연수 데이터들을 오름차순으로 정렬할 것 1 2 3 6 2 1 3 2 1 6 5 2 3 1 2 3 2 1 3 6 5 2 1 3 2 5 1 3 ..

Heap Sort는 Merge Sort와 Quick Sort만큼 빠른 정렬 알고리즘입니다. 특징 힙 트리 구조(Heap Tree Structure)을 이용하는 정렬 방법 항상 O(N*logN)만족. tree구조를 사용하는 heap특성상 logN. 병합 정렬과 달리 별도의 추가적인 배열 필요X -> 메모리 측면에서 효율적 이론 적으로는 퀵,병합 정렬보다 우위. 하지만, 단순히 속도만 비교 시 퀵 정렬이 평균적으로 더 빠름 때문에 힙 정렬이 일반적으로 많이 사용되지는 않음. 힙 정렬(Heap Sort)의 메커니즘은 힙(Heap)을 이용해 데이터를 정렬해보자! 필요한 선행 지식 이진 트리(Binary Tree)란? 완전 이진 트리(Complete Binary Tree)란? 힙(Heap)이란? 이진 트리(Bin..

지금 까지 배운 정렬을 되짚어보자, -Selection Sort -Bubble Sort -Insertion Sort 위 3 가지 정렬은 모두 O(N*N)이다. 그래서 조금 더 특정 케이스에 대해서 강력한 시간복잡도를 가지는 -Quick Sort 를 배웠다. 퀵정렬은 O(N*logN)의 시간복잡도를 가진다. logN이라는 시간은 '분할정복'이라는 이점에서 나온 시간 복잡도이다. 하지만, 이러한 퀵정렬도 worst case가 존재했다. 이는 Pivot값에 따라 분할이 편향될 수 있어 '분할의 이점'을 사용하지 못할 수도 있으며, 이미 정렬이 완료된 데이터에 대해서는 결코 '분할의 이점'이 적용될 수 없다. 즉, 최악의 경우 O(N*N)의 시간복잡도를 가진다. 결과적으로, Merge Sort 알고리즘은 O(N..

더보기 ※알고리즘 공부는 '동빈나' 님의 유투브 https://www.youtube.com/watch?v=gBcUO_6JXIA&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=6 를 통해 학습합니다. 동빈나님이 설명해주시는 개념을 듣고, 구현 코드를 보며 따라치고 원리를 익히고 있는 중이에요. 그런데, 이번 퀵 정렬을 실습하면서 문제가 발생했습니다. 위 유투브 실습 강의는 C언어로 진행이 되는데, C언어에서는 메모리에 쓰레기 값(ex. -4697468) 대충 이런식..이 있어서 배열의 인덱스가 넘어가도 쓰레기 값을 참조하여 정상적으로 돌아가는 반면에 저는 JAVA로 알고리즘 공부를 하고 있는 중이기에 ArrayIndexOutOfBoundsException 발생하더라고요...

지난 시간까지 학습했던 선택 정렬과 버블 정렬을 다시 한 번 떠올려 봅시다. 선택 정렬의 메커니즘은 "가장 작은 것을 맨 앞으로 보내면 어떨까?" 버블 정렬의 메커니즘은 "옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내면 어떨까?" 두 정렬 알고리즘 모두 O(N*N)의 시간복잡도를 가졌고, 실제 속도는 버블정렬이 더 느린 것을 배웠습니다. 그렇다면, 삽입 정렬(Insertion Sort)는 어떨까요? 결론부터 말하자면, 두 정렬 알고리즘과 똑같이 O(N*N)의 시간 복잡도를 가집니다. 하지만, 특정한 상황에서는 정렬 알고리즘 중에서도 가장 빠른 정렬 알고리즘이라고 할 수도 있습니다. 서론이 길었네요. 1 10 5 8 7 6 4 3 2 9 를 오름 차순으로 정렬하는 프로그램을 작성하시오. 삽입 정렬(I..

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요. 1 5 2 6 3 4 7 8 9 10 위 문제에 대해서 정렬 알고리즘 중 "버블정렬(Bubble Sort)"를 사용하여 1 5 2 6 3 4 7 8 9 10 -> 1 2 3 4 5 6 7 8 9 10 으로 정렬을 해보자. 앞서 언급했던, 선택정렬(Selection Sort) 문제와 동일한 문제이다. 버블 정렬(Bubble Sort)는 쉽게 말해서, 인접해 있는 값과 비교해서 더 작은 값을 앞으로 보내는 것!!! 위 사진처럼 인접한 두 요소 값을 비교하고 i > i+1 의 대소관계를 가지면, 작은 값이 앞에 위치하도록 교체한다. 선택 정렬(Selection Sort)은 0번째 인덱스부터 작은 수가 먼저 차례대로 정렬되었다면, 버블 정렬(Bubbl..

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요. 1 5 2 6 3 4 7 8 9 10 위 문제에 대해서 정렬 알고리즘 중 "선택정렬(Selection Sort)"를 사용하여 1 5 2 6 3 4 7 8 9 10 -> 1 2 3 4 5 6 7 8 9 10 으로 정렬을 해보자. 선택 정렬은 쉽게 생각해서, 가장 작은 수를 선택해서 맨 앞으로 보내는 것! package sort; public class Selection_Sort { public static void main(String[] args) { int i,j,min,index=0,temp; int[] array = {1, 5, 2, 6, 3, 4, 7, 8, 9, 10}; for (i = 0; i < 10; ++i) { min = 999..