Quiz - 시간 복잡도, 정렬 Algorithm, Map/Set

1. 시간 복잡도가 무엇인지 설명해주세요.

• 시간 복잡도는 입력값의 크기가 증가함에 따른 알고리즘의 런타임 소요시간을 말합니다.

1.1 공간 복잡도가 무엇인지 설명해주세요.

• 공간 복잡도는 알고리즘 코드를 실행시키기 위해서 할당되어야 하는 메모리 크기를 말합니다.

1.2 Big O Notation이 무엇이고 왜 필요한가요?

• Big O Notation은 알고리즘의 연산 수와 런타임의 상관관계를 나타낸 것입니다. Big O Notation은 다른 접근 방법들을 비교했을때 어떤 방법이 더 나은지 알기 위해서 필요합니다.

2. 정렬 알고리즘에 대해서 아시는 대로 설명해주세요.

• Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Radix Sort가 있습니다.
• Bubble Sort는 두 값을 비교해서 더 큰 값이 뒤로 가도록 바꾸고 모든 값이 정렬될 때까지 반복하는 정렬 알고리즘입니다. Bubble Sort는 정렬된 데이터에서는 O(N), 정렬되지 않은 데이터에서는 O(N^2)의 시간 복잡도를 가집니다.
• Selection Sort는 두 값을 비교해서 더 작은 값이 앞으로 가도록 바꾸고 모든 값이 정렬될 때까지 반복하는 정렬 알고리즘입니다. Selection Sort는 O(N^2)의 시간복잡도를 가집니다.
• Insertion Sort는 한 번에 한 요소씩 정렬된 배열의 요소를 끝에서부터 비교해서 작은 값을 가진 요소 다음에 삽입하는 알고리즘입니다. Insertion Sort는 O(N^2)의 시간복잡도를 가집니다.
• Bubble Sort, Insertion Sort는 정렬된 데이터에서 적합하고, Selection Sort는 지속적으로 정렬해야 하는 실시간 데이터에 적합합니다.
• Merge Sort는 주어진 배열을 원소가 하나 남을 때까지 계속 둘로 쪼개고 다시 크기 순으로 재배열하면서 원래 크기의 배열로 합치는 정렬 알고리즘입니다. Merge Sort의 시간복잡도는 분할하는데 O(logN), 병합하는데 O(N)이 걸리므로 총 O(NlogN)이 걸립니다.
• Quick Sort는 주어진 배열에서 한 요소를 피벗으로 선택하여 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 쪼개고 쪼갠 배열들에 대해 이 과정을 반복하여 정렬하는 알고리즘입니다. Quick Sort의 시간복잡도는 평균적으로 O(NlogN), 최악의 경우 O(N^2)이 됩니다.
• Radix Sort는 낮은 자리수부터 비교하여 정렬해가는 정렬 알고리즘입니다. Radix Sort의 시간복잡도는 O(dN)을 가집니다. 여기서 d는 정렬할 숫자의 자릿수를 의미합니다.

2.1 사용해본 정렬 알고리즘과 장점에 대해 설명해주세요.

• 제가 사용해본 정렬 알고리즘은 Merge Sort입니다. 배열을 둘로 분할한 후 정렬하기 때문에 시간 복잡도가 O(NlogN)이어서 Bubble Sort, Selection Sort, Insertion Sort보다 빠르고, Quick Sort와 다르게 시간복잡도가 항상 O(NlogN)을 가지므로 기준값에 따라 성능이 달라지지 않는다는 장점을 가지고 있습니다.

3. Map과 Set에 대해서 설명해주세요.(차이점, 활용해 본 경험 등)

• Map은 키와 값의 쌍으로 데이터를 저장하는 자료구조인 반면에, Set은 중복되지 않은 데이터들을 값으로 저장하는 자료구조입니다.
• Map은 get 메서드를 통해 해당 키에 대한 값을 쉽게 얻을 수 있기 때문에 키와 값으로 이루어진 데이터를 다룰 때 주로 사용합니다.
• Set은 중복이 있는 데이터를 중복이 없는 데이터로 바꿀 때 주로 사용합니다.

3.1 Map과 객체의 차이점에 대해 설명해주세요.

• 객체는 키의 데이터 타입으로 문자열만 가질 수 있는 반면에, Map은 키의 데이터 타입으로 모든 타입이 올 수 있습니다.
• 객체는 데이터의 삽입 순서를 보장하지 않는 반면에, Map은 데이터의 삽입 순서를 보장합니다.