[Tech Interview] Part 4. Algorithm

💡 동적 계획법(DP, Dynamic Programming)에 대해 설명해주세요.

• 동적 계획법이란 주어진 문제를 풀기 위해, 문제를 여러 개의 하위 문제로 나누어 푸는 방법을 말합니다.
• 동적 계획법에서는 어떤 부분 문제가 다른 문제들을 해결하는데 사용될 수 있을 때, 답을 여러 번 계산하는 대신 한 번만 계산하고, 그 결과를 재활용하는 메모이제이션(Memoization)기법으로 속도를 향상시킬 수 있습니다.
  
  • 메모이제이션 : 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 재사용함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술

---

💡 동적 계획법(DP, Dynamic Programming)이 갖는 2가지 조건은 무엇인가요?

• 동적 계획법의 조건에는 중복되는 부분 문제와 최적 부분 구조가 있습니다.
• 중복되는 부분 문제란 나눠진 부분 문제가 중복되는 경우로, 메모이제이션 기법을 사용해 중복 계산을 없앨 수 있는 경우를 말합니다.
• 최적 부분 구조를 가진다는 것은 전체 문제의 최적해가 부분 문제의 최적해들로써 구성되는 경우를 말합니다.

---

💡 버블 정렬(Bubble Sort)에 대해 설명해주세요.

• 버블 정렬은 0번부터 n - 1번 인덱스까지 순회하며, 서로 인접한 두 원소를 비교하여 정렬하는 알고리즘으로, O(n^2)의 시간 복잡도를 갖습니다.

---

💡 선택 정렬(Selection Sort)에 대해 설명해주세요.

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

---

💡 삽입 정렬(Injection Sort)에 대해 설명해주세요.

• 삽입 정렬은 두 번째 값부터 시작해 그 앞에 존재하는 원소들과 비교하여 삽입할 위치를 찾아 삽입하는 정렬 알고리즘입니다.
• 평균 시간복잡도는 O(n^2)이며, Best Case의 경우 O(n)까지 빨라질 수 있습니다.

---

💡 힙 정렬(Heap Sort)에 대해 설명해주세요.

• 힙 정렬은 주어진 데이터를 힙 자료구조로 만들어 최댓값 또는 최솟값부터 하나씩 꺼내서 정렬하는 알고리즘으로, 시간 복잡도는 O(nlogn)입니다.
• 힙 정렬이 가장 유용한 경우는 전체를 정렬하는 것이 아니라 가장 큰 값 몇 개만을 필요로 하는 경우입니다.

---

💡 병합 정렬(Merge Sort)에 대해 설명해주세요.

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

---

💡 퀵 정렬(Quick Sort)에 대해 설명해주세요.

• 퀵 정렬은 빠른 정렬 속도를 자랑하는 분할 정복 알고리즘 중 하나로, 피봇을 설정하고 피봇보다 큰 값과 작은 값으로 분할하여 정렬합니다.
• 병합정렬과 달리 리스트를 비균등하게 분할합니다.
• 시간 복잡도는 O(nlogn)이며 worst case경우 O(n^2)까지 나빠질 수 있습니다.

---

💡 Big-O 표기법의 시간 복잡도 크기 순서를 말해주세요.

• O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N) < O(N!)

---

💡 재귀 알고리즘에 대해 설명해주세요.

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

---

💡 피보나치 규칙을 재귀를 통해 구현한 함수를 손코딩 해주세요.

private int fibonacci(int n) {
    if (n <= 2) {
    	return 1;
    }
    
    return fibonacci(n - 1) + fibonacci(n - 2);
}

---

💡 팩토리얼 규칙을 재귀를 통해 구현한 함수를 손코딩 해주세요.

private int factorial(int n) {
    if (n > 1) {
    	return n * factorial(n - 1);
    }
    
    return 1;
}

---

📌 References

• https://dev-coco.tistory.com/161