CS 전공지식 스터디 3기 [3주차] 자료구조와 알고리즘 미션
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 방식으로 해결하기 때문에 결과가 모두 테이블에 저장되어 메모리 상에서의 효율성이 좋습니다.
단점:
코드가 길어질 수 있고, 어떤 순서로 문제를 해결할지를 잘 계획해야 합니다.
메모이제이션과 타뷸레이션 중 선택하는 이유:
메모리가 부족한 시스템에서는 타뷸레이션을 선택하는 것이 더 바람직할 수 있습니다.
타뷸레이션은 스택을 사용하지 않고, 반복문을 사용하여 문제를 해결하므로 재귀 호출로 인한 메모리 사용이 없습니다.
메모리 오버헤드를 줄이기 위해, 메모이제이션처럼 깊은 재귀 호출을 피할 수 있습니다.
따라서 메모리가 부족한 시스템에서는 타뷸레이션을 사용하는 것이 더 적합할 수 있습니다.
답변 0