1. Algorithm 과목 소개

빅오(Big-O) 표기법과 시간 복잡도의 의미와 필요성

안녕하세요. Readerr입니다. 자료구조, 알고리즘 등 많은 부분에서 반드시 알아야 할 것이, "그래서 시간 복잡도는 얼마인가?"입니다. 면접에서 어떤 자료구조의 시간 복잡도는 어떻게 되는지 물어보는 경우도 많고, 알고리즘 문제를 풀 때도 특정 시간 복잡도 내에 풀어야 하는 경우가 많죠. 그렇다면 이 '시간 복잡도'가 무엇이냐. 말 그대로 "특정 작업을 하는데에 얼마만큼 시간이 걸리느냐"입니다. 그러나 일반적으로 '몇 회의 작업을 하느냐'라는 의미로 보는 것이 더 쉽겠네요. 빅오 표기법 시간 복잡도에 사용되는 대표적인 개념은 바로 빅오(Big-O) 표기법이에요. 어렵게 생각하실 거 없이, 변수들 중 최고차항만 계산하겠다는 겁니다. 예를 들어 'x² * 2x * 3'이라는 계산식이 있다고 가정했을 때, ..

알고리즘] 퀵 정렬(Quick Sort)에 대한 이해

소개 정렬 알고리즘 중 대표적인 알고리즘인 퀵 정렬을 소개하고자 한다. 퀵 정렬을 소개하기에 앞서, 대표적인 알고리즘들의 시간/공간 복잡도 표를 확인하면 다음과 같다. 평균 최악 메모리 버블 정렬 n^2 n^2 1 선택 정렬 n^2 n^2 1 삽입 정렬 n^2 n^2 1 퀵 정렬 n log n n^2 n log n 병합 정렬 n log n n log n n 힙 정렬 n log n n log n 1 퀵 정렬은 이름 그대로 '빠른 알고리즘'이라는 의미인데, 실제로 위 알고리즘들 중에서는 일반적으로 가장 빠른 알고리즘이라고 한다. 여기서 약간 의아할 수 있는 부분이 '병합, 힙 정렬이 최악의 경우에 퀵 정렬보다 시간 복잡도가 높은데, 어떻게 가장 빠른 알고리즘이지?'라는 생각이 들 수 있는데, 그 이유는 다음..

버블 정렬

-버블 정렬이란 정렬하려는 배열의 값들이 5, 4, 9, 1, 7이고 오름차순으로 정렬하려고 가정했을 때, 1. 처음 인덱스에 있는 값부터 시작하여 끝 인덱스 -1까지 바로 다음에 있는 값과 비교하여 오른쪽에 있는 값이 더 크다면 두 값을 교환한다. 2. 이를 배열에 들어있는 값의 개수만큼 반복한다. 그리고 그림과 같이 값을 교환할 때 나오는 화살표들이 거품이 보글보글 일어나는 것과 비슷하게 생겼다고 하여 버블 정렬이라고 한다. -버블 정렬의 시간 복잡도 버블 정렬은 처음 인덱스부터 끝 인덱스까지 순환(n)하며 값을 교환하고, 이를 다시 배열에 들어있는 값의 길이만큼 돌리는(n) 정렬 알고리즘이기 때문에 n * n = n^2이라는 시간 복잡도가 나온다. -코드(C++)