[신입 CS 질문] 알고리즘

동적 계획법(DP)

• 주어진 문제를 풀기 위해, 문제를 여러 개의 하위 문제로 나누어 푸는 방법

버블 정렬

• 버블 정렬는 서로 인접한 두 원소를 비교하여 정렬하는 알고리즘입니다.
• 시간 복잡도는 O(n^2)입니다.

선택 정렬

• 선택 정렬은 첫 번째 값을 두번째 부터 마지막 값까지 차례대로 비교하여 최솟값을 찾아 첫 번째에 놓고, 두 번째 값을 세 번째 부터 마지막 값까지 비교하여 최솟값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬하는 알고리즘입니다.

• 시간복잡도는 O(n^2)입니다.

삽입 정렬

• 삽입 정렬은 두 번째 값부터 시작해 그 앞에 존재하는 원소들과 비교하여 삽입할 위치를 찾아 삽입하는 정렬 알고리즘입니다.

• 평균 시간복잡도는 O(n^2)이며, Best Case 의 경우 O(n)까지 높아질 수 있습니다.

힙정렬

• 힙 정렬은 주어진 데이터를 힙 자료구조로 만들어 최댓값 또는 최솟값부터 하나씩 꺼내서 정렬하는 알고리즘입니다.

• 시간 복잡도는 O(nlogn)입니다.

병합 정렬

• 병합 정렬은 주어진 배열을 크기가 1인 배열로 분할하고 합병하면서 정렬을 진행하는 분할/정복 알고리즘입니다.
• 시간 복잡도는 O(nlogn)입니다.

퀵 정렬

• 분할 정복 알고리즘 중 하나로 피봇을 설정하고 피봇보다 큰 값과 작은 값으로 분할하여 정렬 합니다.

• 시간 복잡도는 O(nlogn)이며 worst case 경우 O(n^2)까지 나빠질 수 있습니다.

재귀 알고리즘

• 재귀 알고리즘이란 함수 내부에서 함수가 자기 자신을 또 다시 호출하여 문제를 해결하는 알고리즘입니다.
• 반복을 중단할 조건이 반드시 필요합니다.

출처
https://dev-coco.tistory.com/160