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

자료구조와 알고리즘

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

버블정렬

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

• 앞에 있는 숫자와 옆에 있는 숫자를 비교해서 자리를 바꾸는 알고리즘

• 장점: 가장 쉽게 생각할 수 있는 정렬방법, 이해와 구현이 간단

• 단점: 성능이 ON제곱으로 별로 좋지 않음

선택정렬

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

• 배열의 정렬되지 않은 영역의 첫번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가져옴

• 장점: 이해하기 쉽고 구현하기 쉬움

• 단점: 성능이 좋지않음

삽입정렬

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

• 정렬되지 않은 영역에서 데이터를 하나씩 꺼내서 정렬된 영역 내에 적절한 위치에 삽입하는 알고리즘

• 장점: 이해하기 쉽고 구현하기 쉬움

• 단점: 성능이 좋지 않음

병합정렬

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

• 재귀로 정렬하는 알고리즘

• 장점: 성능이 훨씬 좋음

• 단점: 재기적인 기법으로 이해하기 어려움

퀵정렬

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

• 분할정복 알고리즘

• 장점: 성능이 훨씬 좋음

• 단점: 재기적인 기법으로 이해하기 어려움

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

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

타뷸레이션

상향식 계산 방식으로 계산에 필요하지 않을 수도 있는 값도 미리 계산해서 테이블에 저장해 둠, 이렇게 계산되어 저장된 값을 필요할 떄 사용해 빠르게 계산, 메모리도 절약하고 속도도 빠르게 해결할 수 있음