[오독완 챌린지] 기술 면접 대비 CS 전공 핵심 요약집 (9일차)

오늘도 독서 완료!

 

대망의 알고리즘입니다. 알고리즘에 대해서 중요한 부분은 두 번씩 읽었네요.

내용 자체가 많지 않고 쉽게 설명되어 있어서 읽는데 부담은 전혀 없었습니다.

 

정렬 알고리즘에 대해서 학습을 했는데, 정렬 알고리즘은 비교하는 것과 비교하지 않는 것으로 분류가 됩니다.

그래서 비교는 버블, 선택, 삽입, 합병, 힙, 퀵 정렬 등이 있고, 비교하지 않는 정렬은 계수, 기수 정렬 등이 있습니다.

 

버블 정렬이란 양옆에 위치한 두 값을 비교하면서 크기 순으로 정렬하는 것을 말하는데요. 배열의 뒤에서 부터 정렬이 됩니다.

 

선택 정렬의 경우 배열을 순회하면서 배열의 앞부터 차례대로 각 인덱스에 들어갈 값을 선택하고 위치시킵니다. 

 

삽입 정렬은 배열을 앞에서부터 순회하면서 정렬된 부분의 적절한 위치에 값을 삽입하는 방식입니다.

 

가장 중요한게 합병, 퀵, 힙 정렬입니다.

 

합병 정렬은 재귀를 이용하는 분할 정복 알고리즘으로, 분할은 배열을 쪼개는 것이고, 정복은 분할한 배열을 정렬하면서 하나로 합병하는 것을 말합니다. 정렬하려는 배열의 크기가 0또는 1이 될때 까지 절반씩 분할한다고 합니다.

 

퀵 정렬은 pivot이라는 특정 값을 선택해 피봇보다 작은 값으로 구성된 배열과 피봇보다 큰 값으로 구성된 배열로 분할해 정렬하는 방식입니다. 따라서 피봇으로 어떤 값을 선택하느냐에 따라 퀵 정렬의 성능이 좌우된다고 볼 수 있습니다.

 

힙 정렬은 최대 힙이나 최소 힙 자료구조를 이용해 정렬을 수행하는 것입니다. 배열을 힙으로 만드는 과정을 수행하고, 최대 힙에서 삭제 연산을 이용해 정렬을 수행합니다.

 

이 외에도 정말 많은 알고리즘이 있지만 중요한 것을 가장 우선적으로 학습해야합니다.