[인프런 워밍업 클럽 3기 - CS] - 3주차 미션 (자료구조와 알고리즘)

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

• 버블정렬

  • 인접한 두 수를 비교하여 차례대로 자리를 바꿔나가며 정렬하는 방식

  • 시간복잡도: O(n^2)

• 선택정렬

  • 선택된 정렬 영역에 정렬되지 않은 영역의 최솟값을 삽입

  • 시간복잡도: O(n^2)

• 삽입정렬

  • 정렬되지 않은 영역의 첫 원소를 정렬된 원소들과 비교하여 올바른 위치에 삽입

  • 시간복잡도: O(n^2)

• 병합정렬

  • 배열을 더 이상 나눌 수 없을 때까지 쪼개고(분할)

  • 다시 정렬된 상태로 병합(정복)

  • 재귀를 통해서 구현이 가능

  • 시간 복잡도 O(nlogn)

• 퀵정렬

  • 배열 중 하나를 pivot으로 설정하고

  • 배열의 시작과 끝에서부터 pivot과 비교해가며 좌, 우로 정렬하고

  • 두 인덱스가 교차되면 pivot을 교차점이랑 교체

  • 재귀를 통해서 반복

  • 시간 복잡도 O(nlogn) - 최악의 경우 O(n^2)

  • 하지만 최악의 경우가 나올 확률이 거의 없고, 병합정렬보다 메모리 사용이 적기 때문에 더 좋은 알고리즘이라고 판단

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

메모리제이션이란 알고리즘 계산 과정에서 동일한 계산이 반복되어 실행되는 경우, 함수를 실행해가며 계산 값을 저장해두고 동일한 계산 실행 시 저장된 결과 값을 불러오며 계산하는 방식을 의미한다. 이 방법은 하향식 계산을 하며 중복되는 계산을 제거할 수 있기에 연산 속도는 빠르고 하향식 접근 문제에 대해 빠르게 풀이할 수 있다는 장점이 있지만 계산에 필요한 결과를 저장해두어야 함으로 메모리의 사용량이 크다는 단점이 있다.

타뷸레이션은 상향식 계산 방식으로 모든 값을 자료구조에 저장해두고 계산에 필요한 결과 값을 불러오며 계산하는 방식을 의미한다. 반복적인 함수 호출이 없기 때문에 메모리에 큰 부담이 없으며 상향식 접근이 필요한 문제에 사용될 수 있다는 장점이 있지만 미리 모든 연산을 진행하여 저장해야 하기 때문에 불필요한 연산이 발생할 수 있다는 단점이 있다.

'메모리가 부족한' 시스템에서 '재귀로 쉽게' 구현이 가능한 상황에서 문제를 해결하기 위해서는 타뷸레이션을 사용할 것 같다. 메모이제이션은 재귀로 쉽게 구현이 가능한 문제에 대해 이점을 발휘하지만 메모리의 사용이 크다는 단점으로 인해, 결국 메모리가 부족한 시스템에서 구현이 완료되어도 실행이 안된다면 의미가 없다고 판단하였다. 반면 타뷸레이션은 재귀로 문제를 푸는 것에 이점은 없지만 쉽지 않더라도 재귀가 아닌 상향식으로 문제를 접근하여 풀이할 수 있을 것이라고 생각한다.

📒 회고

 미션을 통해서 강의를 통해서 공부했던 내용들을 전체적으로 복습해볼 수 있었으며 이번에도 실무적인 환경에서 실제로 고민해볼만한 주제를 받고 이에 대해 생각해볼 수 있는 시간을 가져서 좋았다. 아직 기초 수준의 자료구조와 알고리즘에 대해서 공부를 하였지만 꾸준히 문제를 풀어가면서 심화 알고리즘에 접근하며 실력을 키워나가고 싶다.