알고리즘의 시간 복잡도와 공간 복잡도의 개념, 빅오 표기법에 대해 설명해주세요.

[kmh5038]

• 자주 사용되는 정렬 알고리즘(예: 퀵 정렬, 병합 정렬)의 동작 원리와 시간 복잡도를 설명해주세요.
• 이진 탐색의 원리와 시간 복잡도에 대해 설명해주세요.
• 다이나믹 프로그래밍(Dynamic Programming)의 개념을 설명해주세요.

[kmh5038]

1. 정렬 알고리즘

정렬 알고리즘이란 주어진 데이터를 특정한 기준에 따라 순서대로 나열하는 알고리즘 입니다. 정렬 알고리즘은 여러가지 종류의 알고리즘이 있는데 각각 시간복잡도와 공간복잡도가 다르다.

위에서 언급한 시간 복잡도와 공간복잡도는 정렬 알고리즘에서 반드시 알아야하는 개념입니다.

우선 시간 복잡도는 특정 알고리즘이 문제상황을 해결하는데 걸리는 시간을 의미합니다. 같은 결과를 가져오는

코드라면 시간 복잡도가 작을수록 더 효율적인 알고리즘입니다.

공간 복잡도는 작성한 프로그램이 얼마나 많은 메모리를 차지하는지 분석하는 방법입니다. 최근 컴퓨터 성능의

비약적인 발전으로 중요성이 예전보다 많이 떨어졌지만, 빅데이터 분야는 아직도 중요하게 사용됩니다.

1-1. 시간복잡도 표기법

시간복잡도는 크게 3가지 표기법이 있는데 최선의 경우인 오메가(Big-Ω) 표기법, 평균의 경우인

세타 표기법(Big-θ), 최악의 경우인 빅오(Big-O) 표기법이 있습니다.

이 중 빅오(Big-O) 표기법이 가장 많이 사용되는데 그 이유는 “최소 특정 시간 이상이 걸린다” 보다 “이 정도

시간까지 걸릴 수 있다”를 고려해야 그에 맞는 대응이 가능하기 때문이다.

1-2. 빅오(Big-O)표기법의 종류

빠른 시간 복잡도 별로 정리를 해보겠습니다.

• O(1) - 상수 시간(Contant time) : 입력 크기(n)에 상관없이 일정한 연산을 수행하는 시간복잡도 이다.

• O(log n) - 로그 시간(Logarithmic time) : 입력 크기(n)이 커지면 연산 횟수가 log₂ n 에 비례해서 증가하는 시간복잡도 이다.

• O(n) - 선형 시간(Linear time) : 입력크기(n)이 커지면 연산 횟수가 n에 비례해서 증가하는 시간복잡도이다.

• O(n²) - 2차 시간(Quadratic time) : 입력크기(n)이 커지면 연산 횟수가 n²에 비례해서 증가하는 시간복잡도이다.

• O(2ⁿ) - 지수 시간(Expotential time) : 입력 크기(n)가 커지면 연산 횟수가 2ⁿ에 비례해서 증가하는 시간복잡도이다.

1-3. 정렬 알고리즘의 종류

2-1. 선택 정렬(Selection Sort)

선택정렬은 `주어진 배열에서 가장 작은 값을 찾아 첫 번째 원소와 교환한 후, 그 다음으로 작은 값을 두번째 원소와 교환하는 방식`을 반복하여 정렬을 수행합니다.  시간 복잡도 : `O(n²) 최선, 평균, 최악 모두 동일`합니다.

2-1. 삽입 정렬(Insertion Sort)

삽입 정렬은 `배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 첫 번째 원소를 정렬된 부분에 적절한 위치에 삽입하는 방식`으로 정렬을 수행합니다. 시간 복잡도 : `O(n²)`이며 `최악과 평균은 동일`하지만 `모두 정렬이 되어 있는 경우 한 번씩밖에 비교를 안하므로최선의 경우 O(n)`의 시간 복잡도를 가지게됩니다. 

2-3. 버블 정렬(Bubble Sort)

버블 정렬은 `인접한 두 원소를 비교하고 더 작은 값을 앞으로 보내는` 정렬을 수행합니다. 시간 복잡도는 선택 삽입 정렬과 같지만 `연산 수가 많아 정렬 알고리즘 중 가장 느리고 효율이 떨어집니다.` 시간 복잡도 : `정렬이 되어있던 안되어있던, 2개의 원소를 비교하기 때문에 최선,평균,최악 모두 O(n²)`입니다. 

2-4. 퀵 정렬(Quick Sort)

퀵 정렬은 데이터 중 `임의의 기준값을 정해서 두 부분 집합으로 나눕니다. 이때 기준 값 왼쪽은 작은 값` `오른쪽은 큰 값을 배치`하고 `더 이상 집합을 나눌 수 없을때까지 재귀적 실행`을 합니다. 시간 복잡도 : `O(n log n)`이며 `최선, 평균은 동일`하고 `최악의 경우 O(n²)`입니다. 삽입 정렬과 반대로 퀵 정렬은 `이미 정렬된 데이터라면 매우 비효율적으로 작용`합니다. 

2-5. 병합 정렬(Merge Sort)

병합 정렬은 비교 기반 알고리즘으로 `‘분할,정렬,결합’`순으로 진행되는데 데이터 배열을 `2개 이상의 부분 배열로 분할하고 부분 배열에서 정렬을 한 뒤 결합하여 다시 정렬`을 진행합니다. 시간 복잡도 : `O(n log n)`이며, `최선, 평균, 최악의 경우 모두 동일`합니다. `데이터를 정확히 반으로 나누고 정렬하기 때문에 항상 일정한 시간 복잡도를 유지하므로 퀵 정렬의 한계점을 보완`할 수 있지만 다른 정렬과 비교했을때 `배열이 더 필요하기 때문에 0(n) 수준의 메모리가 추가로 필요한 단점`이 있습니다. 퀵 정렬과 차이점 - 퀵 정렬 : 우선 기준점을 통해 정렬 → 영역을 쪼갬 - 병합 정렬 : 영역을 쪼갤 수 있을 만큼 쪼갬 → 정렬 

2-6. 힙 정렬(Heap Sort)

힙 정렬은 `완전 이진트리 기반`으로 최대 힙 or 최소 힙 트리를 구성해 정렬을 수행합니다. `내림차순 정렬`은 `최대힙`을 구성하고 `오름차순 정렬`은 `최소힙`을 구성하면됩니다. 시간 복잡도 : `O(n log n)이며, 최선, 평균, 최악의 경우 모두 동일`하다. 

2-7. 기수 정렬(Radix Sort)

기수 정렬은 `낮은 자릿수부터 비교하여 완성하는 정렬`입니다. 기수 정렬은 `비교 연산을 하지 않으며 정렬 속도가 빠른 편이지만 데이터 전체 크기에 기수 테이블의 크기만 한 메모리가 더 필요한 단점`이 있습니다. 시간 복잡도 : `O(dN)이며 d는 자릿수`입니다. 

2. 이진탐색

이진 탐색이란 정렬되어 있는 데이터에서 특정한 값을 찾아내는 알고리즘입니다. 탐색 범위를 반으로 나누어 찾는 값을 포함하는 범위를 좁혀가는 방식으로 동작합니다. 이해가 쉬운 예시로 일상에서 우리가 나이를 맞추는 게임을 할때 Up,Down 게임을 하는데 비슷한 방식입니다.

2-1 . 이진 탐색 동작방식

1. 정렬된 배열에서 중간 인덱스를 찾는다.
2. 찾으려는 값과 중간 값을 비교한다.
3. 찾으려는 값이 중간 값보다 작으면 중간 인덱스를 기준으로 왼쪽 부분 배열을 탐색한다. 찾으려는 값이 중간 값보다 크면 중간 인덱스를 기준으로 오른쪽 부분 배열을 탐색한다.
4. 탐색 범위를 반으로 줄인다.
5. 탐색 범위가 더 이상 없을 때까지 위 과정을 반복한다.

2-2. 이진탐색의 장단점

장점

• 검색속도가 빠르다 : 검색 대상의 크기와 상관없이 빠른 검색 속도를 제공한다는 것으로, 검색 대상이 매우 큰 경우에도 탐색 시간이 빠르기 때문에, 대량의 데이터를 다루는 알고리즘에서 많이 사용된다.
• O(log n)의 검색 속도를 보장한다 : 검색 대상이 정렬되어 있다는 가정하에 이론적으로 최악의 경우에도 O(log n)의 검색 속도를 보장한다. 즉, 검색 대상의 크기가 커져도 검색 시간이 늘어나는 속도가 상대적으로 느리기 때문에 가능하다.

단점

• 반드시 특정구조가 필요하다 : 가장 큰 단점은 배열이나 이진탐색 트리와 같이 정렬된 구조에서만 사용할 수 있다는 것입니다.
• 만약 데이터가 정렬되어 있지 않은 경우에는 이진탐색을 사용할 수 없다.

이진 탐색의 시간 복잡도는 O(log n)으로, 배열의 크기에 비례하여 실행 시간이 결정됩니다. 대용량 데이터에서 특정 값의 위치를 찾는데 용이하게 사용됩니다.

3. 다이나믹 프로그래밍(동적 계획법)

다이나믹 프로그래밍 또한 알고리즘의 한 종류입니다. 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방식을 말합니다. 더 자세히 설명드리면 상향 접근법이라는 방법으로 가장 작은 부분의 해답을 구한 후, 이를 저장하여, 저장한 값을 이용해 상위 문제를 풀어가는 방식입니다.

3-1. 다이나믹 프로그래밍 조건

다이나믹 프로그래밍을 적용하기 위해서는 두가지 속성을 만족시켜야합니다.

• 부분 반복 문제(Overlapping Subproblem)

  다이나믹 프로그래밍의 등장은 피보나치 수열이라고한다. 그래서 대표적인 예시로 피보나치 수열이 나온다.피보나치 수열은 하나의 값을 도출하기위해 함수내부에서 또 함수가 호출되는 대표적인 재귀함수입니다. 그래서 이러한 반복적인 연산을 부분 반복 문제라고 합니다.

• 최적 부분 구조(Optimal Substructure)

  최적 부분 구조는 어찌 생각해보면 당연한 구조입니다. 큰 문제의 최적의 답을 구하려면 작은 문제의 최적의 답을 합쳐서 만들어야합니다. 작은 문제의 답이 효율적이지 않으면 효율적이지 않은것들이 모여 효율적이지 않은 큰 문제의 답이 될것입니다. 효율의 가장 간단한 방법은 중복연산을 줄이는것인데, 이 방법으로 나온것이 메모이제이션(Memoization) 개념입니다.

3-2. 메모이제이션(Memoizetion)

메모이제이션이란 컴퓨터 프로그램이 동일한 계산을 반복해야할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술입니다.

3-3. 다이나믹 프로그래밍의 2가지 접근 방법

다이나믹 프로그래밍으로 문제를 해결하려 할 때, 두가지 접근 방법이 존재합니다.

• Bottom - Up

  말 그대로 아래에서 위로 접근하는 방식으로 부분 문제에서부터 문제를 해결하여 점차 큰 문제를 풀어가는 방식입니다.

• Top - Down

  말 그대로 위에서 아래로 접근하는 방식으로 큰 문제에서 부분 문제로 쪼개가면서 재귀 호출을 통해 문제를 푸는 방식입니다.