버블 정렬에 대해 설명해주세요
버블 정렬은 서로 인접한 두 원소를 비교하여 크기가 순서대로 되어있지 않으면 정렬하는 알고리즘
0번 인덱스부터 n-1번 인덱스까지 n번까지의 모든 인덱스를 비교하며 정렬. 시간복잡도는 O(n^2)
선택 정렬에 대해 설명해주세요
선택 정렬은 주어진 배열 중 최솟값을 찾아 그 값을 첫번째 값과 교체하고, 첫번째 값을 제외하고 나머지 리스트를 같은 방법으로 반복하는 정렬 알고리즘. 시간복잡도는 O(n^2)입니다.
삽입 정렬에 대해 설명해주세요
삽입 정렬은 두번째 값부터 시작해 그 앞에 존재하는 원소들과 비교하여 삽입할 위치를 찾아 삽입하는 알고리즘. 평균 시간복잡도는 O(n^2)이며, best case의 경우 O(n)까지 높아질 수 있음.
합병 정렬에 대해 설명해주세요
하나의 리스트를 두개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법임. 실제 정렬이 이루어지는 시점은 2개의 리스트를 합병하는 단계임 시간 복잡도는 O(nlogn)임
힙 정렬에 대해 설명해주세요
힙 정렬은 주어진 데이터를 힙 자료구조로 만들어 최댓값 또는 최솟값부터 하나씩 꺼내서 정렬하는 알고리즘. 힙 정렬이 가장 유용한 경우는 전체를 정렬하는 게 아니라 가장 큰 값 몇개만을 필요로 하는 경우임
퀵 정렬에 대해 설명해주세요
하나의 리스트를 피벗을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법임.
시간복잡도가 O(nlogn)임. 가장 빠름
셀 정렬에 대해 설명해주세요
삽입 정렬을 보완한 알고리즘. 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안. 삽입 정렬처럼 전체 리스트를 한번에 정렬하는게 아니라 일정한 기준으로 여러개의 부분 리스트를 만들고 각 부분 리스트를 삽입 정렬로 정렬.
퀵 정렬에서 최악의 복잡도 O(n^2)가 발생하는 경우를 설명하고 이를 개선할 수 있는 방법에 대해서도 추가적으로 설명해주세요
pivot을 가장 큰값이나 작은 값으로 잡는 경우 분할 과정에서 비대칭적인 파티션이 반복되면서 최악의 복잡도가 만들어지가 됨. 이 경우는 수행시간이 일반적인 경우보다 훨씬 길어지게 되는데 이를 개선하기 위해서는 난수를 발생시켜 피벗을 랜덤하게 뽑는 경우를 생각해봐야함.
피보나치 수열을 구현할 수 있는 알고리즘 3가지를 언급하고 각 시간 복잡도를 비교해주세요
피보나치 수열의 구현 방식에는 재귀, 반복, dp가 있음
재귀문으로 구현할 경우 시간복잡도는 O(2^n), 반복문과 dp 의 경우 O(n).
dp 를 사용하는 경우 한번 값을 구하고 나면 저장해두기 때문에 O(1) 만에 구할 수 있음.
재귀와 반복의 차이와 DP의 장점에 대해 설명해주세요
재귀는 함수 내에서 자기 자신을 반복하는 호출이고 반복은 조건이 참인 경우 계속하여 반복되는 명령어 블록임
dp는 작은 문제의 해를 여러 메모리에 저장해두기 때문에 동일한 계산의 반복을 줄일 수 있어 속도가 빠르다는 장점이 있음
정렬 알고리즘에 대해 설명해주세요
정렬 알고리즘은 말 그대로 어떠한 자료구조를 정렬하는 방법으로 대표적으로 퀵소트, 합병 소트, 버블 소트, 삽입 소트, 선택 소트 등이 있음
퀵 정렬과 합병 정렬을 비교해주세요
퀵 정렬은 pivot을 기준으로 나눠 정렬하는 기법이고, 합병 정렬은 자료구조를 분할 후에 합치면서 정렬하는 방법. 합병 정렬은 최악,평균,최선의 경우 모두 O(nlogn) 소요, 반면 퀵 정렬은 역순으로 정렬되어 있을 시 pivot의 효과를 볼 수 없어 최악의 경우 O(n^2) 소요
Stable Sort가 무엇이고, 어떤 정렬 알고리즘이 Stable한지 설명해주세요
stable sort란 중복된 값이 있을 시 이 순서가 변경되지 않는 정렬을 의미함. 삽입 정렬, 합병 정렬, 버블 정렬, 카운팅 정렬이 이에 해당함
정렬해야 하는 데이터는 50G 인데, 메모리가 4G라면, 어떤 방식으로 정렬을 진행할 수 있을까요?
- 4G만큼 데이터를 메모리에 읽어 일반적인 정렬 알고리즘 이용해 정렬
- 13개 파일 생성됨
- 280MB 씩 각 파일의 앞부분을 읽어옴( 280*13 = 3640) (남은 280은 출력을 위한 버퍼)
- 280MB씩 merge 수행, 출력버퍼에 작성. 출력 버퍼가 차면 파일에 쓰고 출력 버퍼를 비움
Buble,Selection,Insertion Sort의 속도를 비교해보세요
셋다 시간복잡도는 O(n^2)
(Insertion sort는 정렬되어있을 시 비교연산만 하기 때문 O(n)의 시간복잡도를 가짐)
