STACK vs Queue
Stack과 Queue는 선형 자료구조의 일종이며, Array와 LinkedList로 구현할 수 있습니다.
Stack은 후입선출(LIFO)방식 즉, 나중에 들어간 원소가 먼저 나오는 구조이고
Queue는 선입선출(FIFO)방식 즉, 먼저 들어간 원소가 먼저 나오는 구조를 갖습니다.
TREE / HEAP
Tree는 스택과 큐와 같은 선형 구조가 아닌 비선형 자료구조이며, 계층적 관계를 표현하기에 적합합니다.
Heap은 최댓값 또는 최솟값을 찾아내는 연산을 쉽게 하기 위해 고안된 구조로,
각 노드의 키값이 자식의 키값보다 작지 않거나(최대힙) 그 자식의 키값보다 크지 않은(최소힙) 완전이진트리 입니다.
HashTable vs HashMap
동기화 지원 여부와 null 값 허용 여부의 차이가 있습니다.
해시 테이블(Hash Table)
병렬 처리를 할 때 (동기화를 고려해야 하는 상황) Thread-safe 하다.
Null 값을 허용하지 않는다.
해시 맵(Hash Map)
병렬 처리를 하지 않을 때 (동기화를 고려하지 않는 상황) Thread-safe하지 않는다.
Null 값을 허용한다.
우선순위 큐 구현방법
Priority Queue(우선순위 큐)에 대해 설명해주세요.
우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조입니다.
우선순위 큐 구현 방식에는 배열, 연결 리스트, 힙이 있고, 그중 힙 방식이 worst case라도 시간 복잡도 O(logN)을 보장하기 때문에 일반적으로 완전 이진트리 형태의 힙을 이용해 구현합니다.
힙은 완전이진트리를 통해서 구현되었기 때문에 우선순위 큐의 시간복잡도는 O(logn)입니다.
Array vs ArrayList
공통점 : 둘 다 중복되는 요소를 저장할 수 있다.
차이점 : Array는 크기가 고정적이고, ArrayList는 크기가 가변적입니다.
Array는 초기화 시 메모리에 할당되어 ArrayList보다 속도가 빠르고,
ArrayList는 데이터 추가 및 삭제 시 메모리를 재할당하기 때문에 속도가 Array보다 느립니다.
ArrayList vs LinkedList
ArrayList :Random Access, 바로 접근이 가능하다는 것은 곧 O(1)을 의미한다.
LinkedList : Sequential Access 순차 접근만 가능, O(n)이 걸리게 됩니다.
새로운 요소 삽입(중간에)
ArrayList는 해당 요소뒤의 요소들도 전부 옮겨야 합니다.
LinkedList는 앞 뒤 요소의 값만 바꾸어주면 됩니다.
요소 삭제(중간에)
ArrayList는 뒤의 요소들을 전부 앞으로 이동시켜야합니다.
LinkedList의 경우에는 앞 뒤 요소의 값만 바꾸어주면 됩니다.
간단히 정리하면,
Array는 검색이 빠르지만, 삽입, 삭제가 느리다.
LinkedList는 삽입, 삭제가 빠르지만, 검색이 느리다.
정렬
1) 퀵 정렬 : 퀵 정렬은 평균적으로 O(NlogN)의 시간복잡도를 가지는 정렬이며, 같은 시간복잡도의 다른 정렬 알고리즘보다 일반적으로 빠른 정렬 알고리즘입니다. 이는 퀵 정렬의 특성상 매 단계에서 적어도 1개의 원소가 자신의 자리를 찾게 되기 때문에, 단계를 거듭할수록 정렬할 개수가 줄어들기 때문입니다.
간단한 동작원리를 설명드리자면, 주어진 배열에서 하나의 값을 선택해 pivot이라 칭하고, 이를 기준으로 더 작은 값들과 더 큰 값들로 나누어 재귀적으로 정렬을 수행합니다.
하지만 이 경우, 이미 정렬되어있는 배열에서 맨 앞이나 뒤를 pivot으로 설정하게 되는 경우는 최악의 경우 O(n^2)의 시간복잡도를 가진다는 단점이 있습니다. (퀵 정렬은 빠른 정렬 속도를 자랑하는 분할 정복 알고리즘 중 하나로 피봇을 설정하고 피봇보다 큰 값과 작은 값으로 분할하여 정렬 합니다.)
2) 힙 정렬 : Heap Sort는 heap 자료구조를 기반으로 정렬을 수행하는 알고리즘입니다. 내림차순 정렬을 위해서는 최대 힙, 오름차순을 위해서는 최소 힙 자료구조를 사용할 수 있습니다. 주어진 배열의 n개의 요소를 Heap에 삽입하고, 하나씩 삭제하면서 이를 새로운 배열에 저장하는 방식으로 정렬을 수행할 수 있습니다. Heap 자료구조에서 삽입/삭제는 O(logN)의 시간복잡도로 수행되므로, n개의 요소들을 모두 삽입/삭제하는데에는 O(NlogN)의 시간복잡도로 수행됩니다.(힙 정렬은 주어진 데이터를 힙 자료구조로 만들어 최댓값 또는 최솟값부터 하나씩 꺼내서 정렬하는 알고리즘입니다.
힙 정렬이 가장 유용한 경우는 전체를 정렬하는 것이 아니라 가장 큰 값 몇개만을 필요로 하는 경우입니다.
시간 복잡도는 O(nlogn)입니다.)
3) 합병 정렬 = 병합정렬 (Merge Sort) : 합병 정렬은 분할 정복 알고리즘을 기반으로 한 정렬 알고리즘으로, 입력 배열을 같은 크기의 2개의 부분 배열로 분할하는데, 이 때 부분 배열의 크기가 최소가 될 때까지 재귀적으로 반복합니다. 그리고 정렬된 부분 배열을 합병하면서 정렬을 수행하며 배열을 완성시킵니다. 시간복잡도는 최선,평균,최악 모두 O(nlogn)입니다.
4) 삽입 정렬(Insert Sort) : 삽입 정렬은 추가적인 메모리 공간을 필요로 하지 않는 in-place 정렬(제자리 정렬) 알고리즘 중 하나로, 매 회전 마다 새로운 원소가 이미 정렬이 되어있는 앞의 배열에서 어느 위치에 들어갈지 계산하여 삽입하는 정렬 알고리즘입니다. 처음 key를 두번째 값으로 시작하여, 앞의 배열이 정렬되어 있기 때문에 뒤에서부터 key 값과의 비교를 통해 위치를 바꾸면서 정렬 기준에 맞도록 자신의 위치를 찾는 방법으로 정렬을 수행합니다. 시간복잡도는 O(n^2)입니다. (삽입 정렬은 두 번째 값부터 시작해 그 앞에 존재하는 원소들과 비교하여 삽입할 위치를 찾아 삽입하는 정렬 알고리즘입니다.
평균 시간복잡도는 O(n^2)이며, Best Case 의 경우 O(n)까지 높아질 수 있습니다.)
5) 선택 정렬 : 입력 배열 이외에 추가 메모리를 요구하지 않는 in-place sorting(제자리 정렬) 알고리즘 중 하나로, O(n^2)의 시간복잡도를 가지는 정렬 알고리즘입니다. 선택 정렬은 첫번째 index부터 해당 index를 기준으로 이후 index의 data와 비교하여 매 회전마다 최솟값을 초기 index 위치에 오도록 합니다. 이렇게 되면, 매 회전마다 가장 작은 값이 앞으로 오게 됩니다.
(선택 정렬은 첫 번째 값을 두번째 부터 마지막 값까지 차례대로 비교하여 최솟값을 찾아 첫 번째에 놓고,
두 번째 값을 세 번째 부터 마지막 값까지 비교하여 최솟값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬하는 알고리즘입니다. 시간복잡도는 O(n^2)입니다.)
6) 버블 정렬 : Bubble Sort는 정렬 알고리즘으로, 서로 인접한 원소를 비교하여 크기의 순서에 맞게 정렬을 수행하는 알고리즘입니다. 배열의 크기가 n일때, 0번 index부터 n-1번 index까지 모든 index를 순차적으로 비교하면서 정렬합니다.
(버블 정렬는 서로 인접한 두 원소를 비교하여 정렬하는 알고리즘입니다.
0번 인덱스부터 n-1번 인덱스까지 n번까지의 모든 인덱스를 비교하며 정렬합니다.)
매 회전마다 가장 큰 원소가 가장 뒤에 위치하게 되고, 이 원소는 다음 회전에서 정렬을 수행할 필요가 없어집니다. 시간복잡도는 O(n^2)입니다.
