💡 Array(List)의 가장 큰 특징과 그로 인해 발생하는 장점과 단점에 대해 설명해주세요.
Array의 가장 큰 특징은 데이터를 순차적으로 저장한다는 점이다. 장점 - index를 사용해 특정 요소를 찾고 조작이 가능하다. 단점 - 요소가 삽입되거나 삭제되는 경우 그 뒤의 모든 요소를 한 칸씩 뒤로 밀거나 당겨줘야함 - 정보가 자주 바뀌는 데이터를 담기에는 적절하지 않음
💡 Stack, Queue / Tree, Heap의 구조에 대해 설명해주세요
Stack과 Queue는 선형 자료구조, Array와 LinkedList로 구현 가능 Stack: 후입선출(LIFO) Queue: 선입선출(FIFO)
Tree는 비선형 자료 구조, 계층적 관계를 표현하기에 적합 Heap은 최대, 최소값을 찾아내는 연산을 쉽게 하기 위해 고안된 구조
💡 Priority Queue에 대해 설명해주세요
append한 순서에 상관없이 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조 구현 방식: Array, Linkedlist, Heap heap 방식이 시간 복잡도 O(logN)을 보장하기 때문에 일반적으로 이진트리 형태의 힙을 이용해 구현
💡 Array와 ArrayList의 차이점에 대해 설명해주세요
Array: 크기가 고정적, 초기화 시 메모리에 할당됨 ArrayList: 크기가 가변적, 데이터 추가 및 삭제 시 메모리 재할당 따라서 Array가 ArrayList보다 속도가 빠르다.
💡 Array와 LinkedList의 장/단점에 대해 설명해주세요.
Array 장점: 원소의 인덱스 값을 알고 있으면 해당 원소로 접근 가능, RandomAccess가 가능해 검색 속도가 빠름 단점: 삽입, 삭제 과정에서 원소들을 shift 해줘야해서 시간 복잡도가 O(n)
LinkedList 장점: 원소가 있는 부분만 다른 값으로 바꿔주면 삽입과 삭제를 O(1)로 해결 가능 단점: 검색이 느리다.
💡 Hash Table의 시간복잡도에 대해 설명해주세요
해시테이블은 (Key, Value)로 데이터를 저장하는 자료구조로 빠르게 데이터를 검색할 수 있다. 빠른 이유는 내부적으로 배열을 사용하여 데이터를 저장하기 때문이다. Key 값은 고유한 index를 가지게 되어 바로 접근 가능하므로 O(1)의 시간복잡도를 가진다 하지만 index 충돌이 발생한 경우 연결된 리스트들까지 검색해야하므로 시간복잡도가 O(N)까지 증가할 수 있다.
💡 Hash Map과 Hash Table의 차이점에 대해 설명해주세요
Hash Map - 병렬 처리를 하지 않을 때(동기화 고려 x) thread-safe하지 않다. - null값 허용
Hash Table - 병렬 처리를 할 때(동기화 고려) thread-safe 하다 - null 값을 허용하지 않는다.
💡 Binary Search Tree와 Binary Tree에 대해 설명해주세요
Binary Tree - 자식 노드가 최대 두개인 노드들로 구성된 트리
Binary Search Tree - 이진 탐색과 연결 리스트를 결합한 자료구조 - 이진 탐색의 효율적인 탐색 능력을 유지하면서, 자료 입력과 삭제가 쉬움 - 왼쪽 트리의 모든 값은 반드시 부모 노드보다 작아야 하고, 오른쪽 트리의 값은 부모 노드보다 커야 함 - 높이가 h일 때 시간 복잡도 : O(h) - Worst Case: 트리의 균형이 한쪽으로 치우쳐진 경우(O(n)