퀵 정렬은 기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복하여 정렬하는 알고리즘 입니다. 기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미치고, 평균 시간복잠도는 O(nlogn)이며 최악의 경우 O(n²)이 됩니다. 정렬 과정 데이터를 분할하는 pivot을 설정(그림의 경우 가장 오른쪽 끝을 pivot로 설정) pivot을 기준으로 다음 과정을 거쳐 데이터를 2개의 집합으로 분리 start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start를 오른쪽으로 1칸 이동 end가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 end를 왼쪽으로 1칸 이동 start가 가리키는 데이터가 pivot이 가리키는 데이터보다 크고, end가 가리키는 데이터가 ..
삽입 정렬은 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방법입니다. 시간 복잡도는 O(n²)이지만 구현하기 쉽습니다. 정렬 과정 현재 index에 있는 데이터 값 선택 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치 탐색 삽인 위치부터 index에 있는 위치 까지 shift 연산 삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 선택할 데이터가 없을 때까지 반복 소스 코드 void insertionSort(int[] arr) { for(int index = 1 ; index = 0) && ( arr[aux]..
선택 정렬은 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법 입니다. 선택 정렬은 구현 방법이 복잡하고, 시간 복잡도 또한 O(n²)으로 효율적이지 않아 많이 사용하지 않습니다. 정렬 과정 남은 정렬 부분에서 최솟값 또는 최댓값 탐색 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터 swap 가장 앞에 있는 데이터의 위치를 변경해 남은 정렬 부분의 범위 축소 남은 정렬 부분이 없을 때까지 반복 소스 코드 void selectionSort(int[] list) { int indexMin, temp; for (int i = 0; i < list.length - 1; i++) { indexMin = i; for (int j = i + 1; j < list.lengt..
데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방법입니다. 시간 복잡도는 O(n²)으로 다른 정렬 알고리즘 보다 속도가 느린 편입니다. 정렬 과정 비교 연산이 필요한 루프 범위를 설정 인접한 데이터 값을 비교 swap 조건에 부합하면 swap 루프 범위가 끝날 때까지 2~3번 반복 정렬 영역을 설정. 다음 루프에서는 이미 정렬된 영역을 제외 비교대상이 없을 때까지 1~5를 반복 소스 코드 void bubbleSort(int[] arr) { int temp = 0; for(int i = 0; i < arr.length - 1; i++) { for(int j= 1 ; j < arr.length-i; j++) { if(arr[j]
스택(Stack) 스택은 삽입과 삭제 연산이 후입선출(LIFO : Last In First Out)로 이루어지는 자료구조입니다. 후입 선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있습니다. 그림을 보듯 새 값이 스택에 들어가면 top이 새 값을 가리킵니다. 스택에서 값을 빼낼 때 pop은 top이 가리키는 값을 스택에서 빼게 되어 있으며 결과적으로 가장 마지막에 넣었던 값이 나오게 됩니다. 용어 위치 top : 삽입과 삭제가 일어나는 위치 연산 push : top 위치에 새로운 데이터를 삽입하는 연산 pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산 peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산 스택은 깊이 우선 탐색(DFS : Depth First Search..
합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘입니다. 합 배열 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 합니다. 배열 A가 있을 때 합 배열 S는 다음과 같이 정의 합니다. S[i] = A[0] + A[1] + A[2] + ... + A[i] + A[i-1] // A[0] 부터 A[i]까지 합 Index 0 1 2 3 4 A 1 2 3 4 5 S 1 3 6 10 15 합 배열이 없이 A[i]부터 A[j]까지의 배열 합을 구하게 되면 최악의 경우 i = 0, j = n 이면 시간 복잡도는 O(N)입니다. 이런 경우 초기에 값을 입력할 때 합 배열을 함께 만들어 사용하면 O(1)시간으로 구할 수 있습니다. 합 배열을 만들 때는 S[i] = S[i -1] + A..
배열 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조이며 배열의 값은 인덱스를 통해 참조할 수 있습니다. Index 0 1 2 3 4 Value Value1 Value2 Value3 Value4 Value5 특징 인덱스를 사용하여 값에 바로 접근 가능 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입하거나 삭제하게되면 주변의 값을 이동하는 과정이 필요 배열의 크기는 선언할 때 지정할 수 있고 한 번 선언하면 크기를 늘리거나 줄일 수 없음 구조가 간단 리스트 값과 표인터를 묶은 노드를 포인터로 연결한 자료구조입니다. 특징 인덱스가 없기에 값에 접근하려면 Head 포인터부터 순서대로 접근해야함 → 접근속도가 느림 포인터로 연결되어 있으므로 데이터의 삽입과 삭제 연산 속도가 ..
시간 복잡도 시간복잡도는 문제를 해결하기 위한 연산 횟수를 말하고 일반적으로 수행시간은 1억번의 연산을 1초의 시간으로 간주하여 예측합니다. 시간 복잡도의 표기법은 아래와 같이 3가지 유형이 있습니다. 최상의 경우 : 빅-오메가 표기법 (Big-Ω Notation) : 최선일 때 평균의 경우 : 빅-세타 표기법 (Big-θ Notation) : 보통일 때 최악의 경우 : 빅-오 표기법 (Big-O Notation) : 최악일 때 1 ~ 10의 숫자가 무작위로 섞여있을 때 임의의 값을 하나 찾는 프로그램이 있다고 할 때 각 표기법의 시간 복잡도는 아래와 같습니다. 빅-오메가 표기법 (Big-Ω Notation) : 1 빅-세타 표기법 (Big-θ Notation) : 2 / N 빅-오 표기법 (Big-O ..
