Stack과 Queue의 차이점
Stack은 “쌓다"라는 의미를 가진 자료구조입니다. 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근 자료구조이며 먼저 들어간 데이터는 제일 나중에 나오는 LIFO(Last In First Out)의 구조를 가지고 있습니다. Queue는 Stack과 반대되는 개념으로, 먼저 들어간 데이터(data)가 먼저 나오는 FIFO(First In First Out) 을 특징으로 가지고 있습니다. 티켓을 사려고 줄을 서서 기다리는 모습과 흡사한 이 자료구조는 입력과 출력의 방향이 고정되어 있으며, 두 곳으로 접근이 가능합니다.
Tree와 Graph의 차이점
Tree는 방향성이 있는 비순환 그래프이기 때문에 Cycle이 존재하지 않으나 Graphs는 노드와 노드를 연결하는 엣지로 구성되어 있는 자료구조이므로 순환, 비순환 모두 존재 가능합니다. (즉 Cycle이 있을 수도 있고 없을 수도 있습니다.) 또한 Tree는 방향 그래프만 존재하지만 Graph는 방향, 무방향 둘 다 존재합니다.
Tree는 Root Node라는 개념이 존재하고, 계층적 구조를 가지고 있기 때문에 부모-자식 관계가 존재하지만 Graph는 Root Node 개념 자체가 존재하지 않기 때문에 부모-자식 관계가 존재하지 않습니다.
이진 탐색 방법에 대해 설명
이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘입니다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교하고, X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색합니다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교합니다. 이런 식으로 해당 값을 찾을 때까지 이 과정을 반복하는 방법입니다. (Ex. 업다운 게임)
*이진 탐색 트리에 대해 질문이 들어올 수 있습니다.
이진 탐색 트리란 이진 탐색(binary search)과 연결 리스트(linked list)를 결합한 이진트리를 말합니다. 이진 탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐습니다.
