CS 전공지식 스터디 3기 [3주차] 자료구조와 알고리즘 미션

Q. 지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.

A.

버블 정렬 (Bubble Sort)

• 장점:

  • 구현이 매우 간단하고 직관적입니다.

  • 데이터가 거의 정렬되어 있으면 성능이 좋습니다.

  • 안정적인 정렬 알고리즘입니다.

• 단점:

  • 시간 복잡도가 O(n²)로, 대규모 데이터에 대해 비효율적입니다.

  • 최악의 경우에도 개선되지 않는 성능을 가집니다.

• 시간 복잡도:

  • 최선: O(n) (데이터가 이미 정렬된 경우)

  • 평균: O(n²)

  • 최악: O(n²)

  선택 정렬 (Selection Sort)

  • 장점:

    • 구현이 매우 간단하고 직관적입니다.

    • 추가적인 메모리 공간이 필요하지 않으며, 인플레이스 정렬입니다.

  • 단점:

    • 시간 복잡도가 O(n²)로, 대규모 데이터에 대해 비효율적입니다.

    • 안정적이지 않으며, 항상 일정한 성능을 보입니다.

  • 시간 복잡도:

    • 최선: O(n²)

    • 평균: O(n²)

    • 최악: O(n²)

삽입 정렬 (Insertion Sort)

• 장점:

  • 구현이 간단하고 직관적입니다.

  • 거의 정렬된 데이터에 대해 성능이 뛰어나며, 최선의 경우 시간 복잡도는 O(n)입니다.

  • 안정적인 정렬 알고리즘입니다.

• 단점:

  • 최악의 경우(역순 정렬) 시간 복잡도가 O(n²)로 비효율적입니다.

  • 데이터가 많을 경우 성능이 저하됩니다.

• 시간 복잡도:

  • 최선: O(n)

  • 평균: O(n²)

  • 최악: O(n²)

병합 정렬 (Merge Sort)

• 장점:

  • O(n log n)의 시간 복잡도로 안정적이고 빠릅니다.

  • 데이터의 양이 많을 때 일관된 성능을 제공합니다.

  • 안정적인 정렬 알고리즘입니다.

• 단점:

  • O(n)의 추가 공간을 필요로 하므로, 메모리 사용이 큽니다.

• 시간 복잡도:

  • 최선: O(n log n)

  • 평균: O(n log n)

  • 최악: O(n log n)

퀵 정렬 (Quick Sort)

• 장점:

  • 평균적으로 O(n log n)의 시간 복잡도를 가집니다.

  • 추가적인 공간이 거의 필요하지 않으며, 인플레이스 정렬입니다.

  • 대규모 데이터에서 빠른 성능을 보입니다.

• 단점:

  • 최악의 경우(이미 정렬된 데이터에 대해 피벗을 잘못 선택한 경우) O(n²)의 시간 복잡도를 가집니다.

  • 안정적이지 않습니다.

• 시간 복잡도:

  • 최선: O(n log n)

  • 평균: O(n log n)

  • 최악: O(n²)

Q. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.

A.

메모이제이션 (Memoization)과 타뷸레이션 (Tabulation)은 모두 동적 프로그래밍(Dynamic Programming)의 기법으로, 문제를 작은 부분 문제로 나누어 해결하고 그 결과를 저장하여 중복 계산을 피하는 방법입니다.

두 방법은 다음과 같은 차이점이 있습니다.

• 메모이제이션은 재귀적으로 해결하며, 각 부분 문제의 결과를 함수 호출 시점에 계산하고 저장합니다.

• 타뷸레이션은 반복문을 사용하여 부분 문제를 해결하고, 모든 하위 문제의 결과를 테이블에 저장합니다.

메모이제이션을 선택할 경우:

• 장점:

  • 문제의 일부만 계산하고 나머지는 재사용하는 방식으로, 필요한 부분만 계산하므로 메모리를 더 효율적으로 사용할 수 있습니다.

  • 직관적이고, 코드가 재귀적으로 작성되므로 구현이 간단할 수 있습니다.

• 단점:

  • 재귀 호출로 인한 스택 오버플로우 문제가 발생할 수 있습니다. 특히, 큰 문제에서 많은 재귀 호출이 일어날 때 문제가 될 수 있습니다.

타뷸레이션을 선택할 경우:

• 장점:

  • 반복문을 사용하므로 재귀 호출이 없고, 스택 오버플로우 문제가 발생하지 않습니다.

  • 문제를 bottom-up 방식으로 해결하기 때문에 결과가 모두 테이블에 저장되어 메모리 상에서의 효율성이 좋습니다.

• 단점:

  • 코드가 길어질 수 있고, 어떤 순서로 문제를 해결할지를 잘 계획해야 합니다.

메모이제이션과 타뷸레이션 중 선택하는 이유:

• 메모리가 부족한 시스템에서는 타뷸레이션을 선택하는 것이 더 바람직할 수 있습니다.

  • 타뷸레이션은 스택을 사용하지 않고, 반복문을 사용하여 문제를 해결하므로 재귀 호출로 인한 메모리 사용이 없습니다.

  • 메모리 오버헤드를 줄이기 위해, 메모이제이션처럼 깊은 재귀 호출을 피할 수 있습니다.

따라서 메모리가 부족한 시스템에서는 타뷸레이션을 사용하는 것이 더 적합할 수 있습니다.