Tech Interview 준비

📌 ArrayList VS LinkedList

• ArrayList
  내부적으로 배열을 사용하여 데이터를 관리한다.
  인덱스를 가지고 있어 데이터 검색에 적합하고 속도가 빠르다 O(1)
  데이터 삽입, 삭제 시 모든 데이터를 임시 배열을 생성해 복사하므로 느려진다. O(n)
• LinkedList
  데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태만 알고 있으면 된다.
  데이터 검색 시 처음부터 노드를 순회하기 때문에 오래걸린다. O(n)
  데이터 삽입, 삭제 시 불필요한 데이터의 복사가 없어 유리하다. O(1)

📌 트리 순회

• 중위 순회 (In-order Traversal) : 왼쪽 자식 ➜ 루트 ➜ 오른쪽 자식
  이진 탐색 트리를 중위 순회하면 정렬된 결과를 얻을 수 있다.
• 전위 순회 (Pre-order Traversal) : 루트 ➜ 왼쪽 자식 ➜ 오른쪽 자식
• 후위 순회 (Post-order Traversal) : 왼쪽 자식 ➜ 오른쪽 자식 ➜루트
• 레벨 순서 순회 (Level-order Traversal) : 너비 우선 순회 (BFS) 라고도 한다. 위의 세 가지 방법은 스택을 활용하여 구현할 수 있는 반면, 레벨 순서 순회는 큐를 활용해 구현한다.

📌 BFS VS DFS

• DFS (깊이 우선 탐색)
  루트 노드에서 시작해서 해당 branch를 완벽하게 탐색한 후 다음 branch를 탐색하는 방법이다. 스택을 이용하여 구현한다.
• BFS (너비 우선 탐색)
  루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 큐를 이용하여 구현한다.

📌 Sorting Algorithm

1. 선택 정렬(Selection Sort)

➜ 장점 : 비교 횟수는 많으나 교환 횟수가 적기 때문에 교환이 많이 이루어지는 상태에서는 효율적으로 사용될 수 있다. 역순 정렬의 상태에서 가장 효율적이다.
➜ 단점 : 정렬을 위한 비교 횟수가 많기 때문에 이미 정렬된 상태에서 소수의 자료가 추가되면 재정렬할 때 최악의 처리 속도를 보인다.

• 시간복잡도 : O(n^2) ➜ 배열 전체를 비교하기 때문에
• 공간복잡도 : O(n) ➜ 단 하나의 배열에서 진행하기 때문에
• Best : 오름차순 정렬된 배열
• Worst : 내림차순 정렬된 배열

1. 인덱스의 맨 앞에서부터, 이를 포함한 그 이후 배열값 중 가장 작은 값을 찾아간다.
2. 가장 작은 값을 찾으면, 그 값을 현재 인덱스 값과 바꿔준다.
3. 다음 인덱스에서 위 과정을 반복한다.

2. 삽입 정렬(Insertion Sort)

➜ 장점 : 버블정렬의 비교횟수를 줄이기 위해 고안된 정렬이기 때문에 크기가 적은 데이터 집합을 정렬하는 알고리즘에서 효율이 좋다.
➜ 단점 : 최악의 경우 O(n^2)이라는 시간복잡도를 가지게 된다. 데이터의 상태와 크기에 따라 성능의 편차가 큰 정렬 방법이다.

• 시간복잡도 : 최악의 경우 - O(n^2) 이미 정렬된 경우 - O(n)
• 공간복잡도 : O(n) ➜ 단 하나의 배열에서 진행하기 때문에
• Best : 오름차순 정렬된 배열
• Worst : 내림차순 정렬된 배열

1. 두번째 인덱스부터 시작한다. 현재 인덱스는 별도의 변수에 저장하고, 비교 인덱스를 현재 인덱스 -1로 잡는다.
2. 별도로 지정해 둔 삽입을 위한 변수와, 비교 인덱스의 배열 값을 비교한다.
3. 삽입 변수의 값이 더 작으면 현재 인덱스로 비교 인덱스의 값을 지정해주고, 비교 인덱스를 -1하여 비교를 반복한다.
4. 만약 삽입 변수가 더 크면, 비교 인덱스+1에 삽입 변수를 저장한다.

3. 버블 정렬(Bubble Sort)

➜ 장점 : 구현이 쉬우며, 코드가 직관적이다.
➜ 단점 : 최선이든 최악이든 O(n^2)이라는 시간복잡도를 가지게 된다. 원소의 개수가 많아지면 성능이 저하된다.

• 시간복잡도 : O(n^2) ➜ 배열 전체를 비교하기 때문에
• 공간복잡도 : O(n) ➜ 단 하나의 배열에서 진행하기 때문에
• Best : 오름차순 정렬된 배열
• Worst : 내림차순 정렬된 배열

1. 두번째 인덱스부터 시작한다. 현재 인덱스 값과, 바로 이전의 인덱스 값을 비교한다.
2. 만약 이전 인덱스가 더 크면, 현재 인덱스와 바꿔준다.
3. 현재 인덱스가 더 크면, 교환하지 않고 다음 연속된 배열 값을 비교한다.
4. 이를 (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 반복한다.

4. 합병 정렬(Merge Sort)

➜ 장점 : 퀵 정렬과 달리 기준값이 없이 절반으로 분할하기 때문에 기준값에 따라 성능이 달라지는 경우가 없다.
➜ 단점 : 임시 배열에 원본 배열을 옮겨주며 정렬하기 때문에 추가적인 메모리가 필요하다.

• 시간복잡도 : O(nlogn)
• 공간복잡도 : 2n ➜ 배열을 하나 더 생성하기 때문에
• Best : 오름차순 정렬된 배열
• Worst : 내림차순 정렬된 배열

1. 현재 배열을 반으로 쪼갠다.
   1. 두 배열 A, B의 크기를 비교한다. 각각의 배열의 현재 인덱스를 i, j로 가정한다.
   2. i에는 A배열의 시작 인덱스를, j에는 B배열의 시작 인덱스를 저장한다.
   3. A[i] B[j]를 비교한다. 이 중에 작은 값을 새 배열 C에 저장한다.
   4. 이를 i나 j 둘 중 하나가 각자 배열의 끝에 도달할 때 까지 반복한다.
   5. 끝까지 저장하지 못한 배열 값을, 순서대로 C에 저장한다.
   6. C배열을 원래의 배열에 저장한다.
2. 배열의 크기가 0이거나 1일때까지 반복한다.

5. 퀵 정렬(Quick Sort)

• Quick sort는 Divide-and-Conquer paradigm을 이용해 정렬을 수행하는 정렬 알고리즘이며 그중에서도 Partitioning이라는 아이디어를 이용한다.
• Partitioning이란 Pivot element를 기준으로 왼쪽은 Pivot보다 작거나 같은 것을 모아주고 오른쪽은 Pivot보다 크거나 같은것을 모아주는 것을 말한다.
• Partitioning을 재귀적으로 진행하다보면 정렬이 완료된다.

➜ 장점 : 기준값(Pivot)에 의한 분할을 통해 구현하는 정렬 방법으로, 분할 과정에서 logN이라는 시간이 소요된다.
➜ 단점 : 기준값에 따라 시간 복잡도가 크게 달라진다.(안정성이 없다.) 기준값을 이상적인 값으로 선택했다면 NlogN의 시간 복잡도를 가지지만, 최악의 기준값을 선택한 경우에는 O(N^2)라는 시간 복잡도를 갖게 된다.

• 시간복잡도 : O(nlogn)
• 공간복잡도 : O(nlogn)
• Best : 오름차순 정렬된 배열
• Worst : 내림차순 정렬된 배열

💡 피봇을 선택하는 방법

1. 첫 번째 값이나 마지막 값을 선택
   ➜ 최악의 경우를 만날 수 있음
2. 첫 번째 마지막 가운데 세 개 중에서 중간 값을 선택
3. 피봇을 랜덤하게 선택하는 방법
   ➜ 운 나쁘면 계속 최솟값 선택할 수도 있음

Sorting Algorithm에서 stable 하다는 것은?

➜ 동일한 Element가 있을 때 정렬 전의 순서와 정렬 후의 순서가 동일함을 보장하는 것

Sorting Algorithm의 가짓수가 많은 이유?

➜ Sorting Algorithm 마다 시간복잡도와 공간복잡도가 다르기 때문에
예를 들면 Merge Sort는 실행 속도는 빠르지만 삽입 정렬이나 선택 정렬에 비해 추가 메모리 공간이 필요하기 때문에 공간복잡도는 좋지 않다.

📌 자료구조

• Stack
  ➜ 원소들의 삽입과 삭제가 리스트의 한쪽 끝에서만 수행되는 자료구조로 후입선출, LIFO 방식이다.

• Queue
  ➜ 리스트의 한쪽 끝에서는 원소들이 삭제되고, 반대쪽 끝에서는 삽입되는 자료구조로 선입선출, FIFO 방식이다.

• Heap
  ➜ 이진트리의 일종으로, 최대 힙 트리, 최소 힙 트리로 나뉜다.