기술면접 준비 : 알고리즘, 코딩 테스트 편

정렬

버블 소트

• 요약 : 인접한 두 원소를 비교하여 정렬 O(n2).
• 예시 :
  

힙 소트

• 요약 : 힙 자료구조로 데이터를 만들어 최대값 또는 최소값부터 하나씩 꺼내서 정렬.
• 추천 : 전체 정렬이 아니라 가장 큰 값 몇개만 필요로 할 때 유용.
• 시간 : O(nlog2n)
• 예시 :
  

머지 소트(병합 정렬)

• 요약 : 배열을 길이가 1인 배열로 분할 후 합침->정렬을 반복함
• 시간 : O(nlog2n)
• 예시 :
  

퀵 소트

• 요약 : 배열을 불균형하게 분할, 피봇을 설정해 피봇보다 큰값과 작은 값으로 분할 후 정렬.
• 추천 : n개의 배열에서 k 번째로 큰 수를 찾는 문제.
• 시간 : O(nlog2n) ~ O(n2)
• 예시 :
  

코테 주 해결 방법

DP

• 정의 : 문제를 하위 문제로 나눌 수 있을 때, 하위 문제가 기하급수적으로 증가할 때, 하위 문제의 해를 memoization해 결합하여 최적해를 구하는 방법

• 판단 팁: 어떤 항을 구하기 위한 전 항들을 완벽히 구할 수 있고, 그 항들을 이용하여 정의에 맞는 현재 항이 깔끔하게 정의가 되는가?

• 접근 방법

1. 점화식을 만들 수 있으면 사용.
2. 재귀 호출이 필요한데 이전의 값이 필요하면 필요한 것만 넘김.

그리디

• 정의 : 각 단계마다 당장 가장 좋은 방법(해)를 선택하는 방법.

• 판단 팁 : 각 단계에서 항상 최적의 선택만을 했을 때, 전체 최적해를 구할 수 있는가?

• 접근 방법

1. 과정을 조각으로 나눈다
2. 조각 마다 우선순위 규칙을 만들어 결정 ( 직접 손으로 해보는거 추천)