시간 복잡도

1. 시간 복잡도 vs 공간 복잡도

   시간 복잡도란 특정 크기의 입력을 기준으로 할 때 필요한 연산의 횟수를 나타낸다.

   이름은 시간 복잡도이지만 실행 시간이 아닌 연산 횟수를 세는 이유는 다음과 같다.

   • 모든 OS, IDE, 플랫폼에서 동일한 결과가 나오지 않는다.
   • 실행 시간 측정을 위한 또다른 방법이 필요하다.

   공간 복잡도란 프로그램 실행과 완료에 얼마나 많은 공간(메모리)가 필요한지를 나타낸다.

   알고리즘을 실행시키기 위해 필요한 공간(space)는 두 가지로 나눌 수 있다.

   1. 알고리즘과 무관한 공간, 즉 고정 공간
      • 코드가 저장되는 공간, 알고리즘 실행을 위해 시스템이 필요로 하는 공간 등
   2. 알고리즘과 밀접한 공간, 즉 가변 공간
      • 문제를 해결하기 위해 알고리즘이 필요로 하는 공간. 변수를 저장하는 공간, 순환 프로그램일 경우 순환 스택(recursion stack) 등

2. 시간 복잡도는 실제 수행 시간과 어떤 관계?

   실제 수행 시간은 실행되는 컴퓨터의 환경에 따라 달라지며 입력되는 데이터에 따라서도 상이합니다. 그래서 보통 입력값이 커질수록 반복문이 수행시간을 지배하기 때문에, 알고리즘의 수행시간을 반복문이 수행되는 횟수로 측정합니다.

3. 시간 복잡도가 작은 알고리즘은 무조건 빠른가?

   시간복잡도가 작다고 해서 무조건 그 알고리즘이 빠르지는 않습니다. 왜냐하면 시간복잡도의 경우에는 보통 최악의 수행시간을 나타내기 때문입니다. 구체적인 예로 퀵소트의 시간 복잡도는 최악의 경우 O(n^2)이지만, 거의 정렬된 데이터의 경우에는 O(n)에 가까운 시간복잡도를 보여 다른 정렬 알고리즘 보다 나은 빠른 성능을 보입니다.

4. 최악의 복잡도는 나쁘지만 실제로는 자주 사용되는 알고리즘을 나열하시오

   퀵소트의 시간 복잡도는 최악일 때 O(n^2)이지만, 거의 정렬된 데이터의 경우에는 O(n)에 가까운 시간복잡도를 보여 다른 정렬알고리즘 보다 나은 빠른 성능을 보입니다. 그래서 python, java와 같은 언어의 내장정렬 함수에서 사용됩니다. 해쉬테이블의 경우 충돌이 발생했을 경우에 O(n)의 시간복잡도를 보이지만, 평균적으로 충돌없이 잘 구현된 경우 O(1)만에 탐색이 가능하여 자주 사용됩니다.

5. 빅오 표기법에 대해서 설명해주세요.

   빅오 표기법(Big-O notation)은 복잡도를 나타내는 점근 표기법 중 가장 많이 사용되는 표기법이다.

   빅오 표기법이 가장 많이 사용되는 이유는 알고리즘 효율성을 상한선 기준으로 표기하기 때문이다.

   다시 말해 최악의 경우를 고려하는 데 가장 좋은 표기법이다! (알고리즘 효율성은 값이 클수록, 즉 그래프가 위로 향할수록 비효율적임을 의미)

정렬

1. 버블 정렬에 대해 설명해주세요

   버블 정렬는 서로 인접한 두 원소를 비교하여 정렬하는 알고리즘입니다. 0번 인덱스부터 n-1번 인덱스까지 n번까지의 모든 인덱스를 비교하며 정렬합니다. 시간 복잡도는 O(n^2)입니다.

   

2. 선택 정렬에 대해 설명해주세요

   선택 정렬은 첫 번째 값을 두번째 부터 마지막 값까지 차례대로 비교하여 최솟값을 찾아 첫 번째에 놓고,두 번째 값을 세 번째 부터 마지막 값까지 비교하여 최솟값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬하는 알고리즘입니다. 시간복잡도는 O(n^2)입니다.

   

3. 삽입 정렬에 대해 설명해주세요

   삽입 정렬은 두 번째 값부터 시작해 그 앞에 존재하는 원소들과 비교하여 삽입할 위치를 찾아 삽입하는 정렬 알고리즘입니다.평균 시간복잡도는 O(n^2)이며, Best Case 의 경우 O(n)까지 높아질 수 있습니다.

   

4. 힙 정렬에 대해 설명해주세요

   힙 정렬은 주어진 데이터를 힙 자료구조로 만들어 최댓값 또는 최솟값부터 하나씩 꺼내서 정렬하는 알고리즘입니다.힙 정렬이 가장 유용한 경우는 전체를 정렬하는 것이 아니라 가장 큰 값 몇개만을 필요로 하는 경우입니다.시간 복잡도는 O(nlogn)입니다.

   

5. 병합 정렬에 대해 설명해주세요

   병합 정렬은 주어진 배열을 크기가 1인 배열로 분할하고 합병하면서 정렬을 진행하는 분할/정복 알고리즘입니다.시간 복잡도는 O(nlogn)입니다.

   

6. 퀵 정렬에 대해 설명해주세요

   퀵 정렬은 빠른 정렬 속도를 자랑하는 분할 정복 알고리즘 중 하나로 피봇을 설정하고 피봇보다 큰 값과 작은 값으로 분할하여 정렬 합니다.병합정렬과 달리 리스트를 비균등하게 분할합니다.시간 복잡도는 O(nlogn)이며 worst case(이미 정렬이 된 경우) 경우 O(n^2)까지 나빠질 수 있습니다.

   (피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다)

   • 시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
   • 퀵 정렬이 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문이다.

   

7. 셸 정렬에 대해 설명해주세요

   셸 정렬(Shell Sort)은 삽입 정렬(Insertion Sort)을 개선한 정렬 알고리즘입니다. 삽입 정렬은 데이터가 거의 정렬된 상태에 가까울수록 효율적이지만, 데이터가 무작위로 배치된 경우에는 비효율적일 수 있습니다. 이러한 삽입 정렬의 한계를 극복하기 위해 셸 정렬은 먼저 배열을 일정한 간격으로 나누어 부분적으로 정렬한 후, 점차 간격을 줄여가며 최종적으로 전체 배열을 정렬하는 방식입니다.

   

8. 이분 탐색에 대해 설명해주세요

   이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다. 시간 복잡도는 O(logN) 이다.

9. 정렬 알고리즘 시간 복잡도를 비교하라

   

10. 위상정렬

알고리즘