CS 기술 면접 - 알고리즘

📍 정렬 알고리즘

 

• 삽입 정렬(Insertion Sort)
  • 두 번째 값부터 시작해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식
  • 평균 시간복잡도 : O(n²)
  • 최선의 경우 시간복잡도 : O(n) ⇒ 데이터가 거의 정렬되어 있는 경우
• 선택 정렬(Selection Sort)
  • 남은 정렬 부분에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식
  • 평균 시간복잡도 : O(n²)
• 버블 정렬(Bubble Sort)
  • 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식
  • 평균 시간복잡도 : O(n²)

• 퀵 정렬(Quick Sort)
  • pivot을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 방식
  • 평균 시간복잡도 : O(nlogn)
  • 최악의 경우 시간복잡도 : O(n²) ⇒ 데이터가 거의 정렬되어 있는 경우
• 힙 정렬(Heap Sort)
  • 주어진 데이터를 힙 자료구조로 만들어 최대값 또는 최솟값부터 하나씩 꺼내서 정렬하는 방식
  • 평균 시간복잡도 : O(nlogn)
• 병합 정렬(Merge Sort)
  • 분할 정복(Divide and Conquer) 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 방식
  • 평균 시간복잡도 : O(nlogn)

 

 

📍 동적 프로그래밍

 

• 동적 프로그래밍(Dynamic Programming) : 한 번 해결된 부분 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 문제 해결 기법
• 동적 프로그래밍의 조건
  • 큰 문제를 작은 문제로 나눌 수 있어야 한다.
  • 작은 문제들이 반복돼 나타나고 사용되며, 이 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일해야 한다. 
• 메모이제이션(Memoization) 기법 : 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법으로, 속도를 향상시킬 수 있다.

 

 

📍 재귀 알고리즘

 

• 재귀 알고리즘 : 함수 내부에서 함수가 자기 자신을 또 다시 호출하여 문제를 해결하는 알고리즘