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

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

• 버블정렬

  • 시간복잡도: O(n²)

  • 장점 구현이 쉽고 단순해서 이해하기 편함

  • 단점 속도 느림

• 선택정렬

  • 시간복잡도: O(n²)

  • 장점 구현이 쉽고 단순해서 이해하기 편함

  • 단점 속도 느림

• 삽입정렬

  • 시간복잡도: O(n²)

  • 장점 구현이 쉽고 단순해서 이해하기 편함

  • 단점 속도 느림

• 병합정렬

  • 시간복잡도: O(n logn)

  • 장점 속도 빠름

  • 단점 어렵다

• 퀵정렬

  • 시간복잡도: O(n logn)

  • 장점 속도 빠름

  • 단점 어렵다

메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다.

여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.

타뷸레이션(상향식) 방식이 더 적합하다.

• 메모이제이션은 재귀 호출을 하는 하향식 방식이기 때문에 스택 메모리를 사용해야 한다

• 타뷸레이션은 반복문만 사용해서 추가 메모리를 사용하지 않는다