자료구조 - 기술면접준비(Section 4)

2023-08-03(목)

 

자료구조

• Stack과 Queue의 차이점은 무엇인가요?
• Tree와 Graph의 차이점은 무엇인가요?
• 이진 탐색 방법에 대해 설명할 수 있나요?

 

 

 

1. Stack과 Queue의 차이점은 무엇인가요?

Stack

쌓여있는 접시와 같다. 먼저들어온 자료가 나중에 나간다. FILO(First In Last Out.)

Stack은 접근성에 제한이 있는 자료구조. 오직 맨 위에 추가(push)할 수 있고, 맨 위에 것만 나갈(pop) 수 있다.

Queue

놀이공원에 줄 서있는 사람들과 같다. 먼저 온 사람이 먼저 나간다. FIFO(First In First Out.)
두가지 동작만 허용된 자료구조. Enqueue(들어옴)과 Dequeue(나감).

Enqueue는 queue의 가장 뒷 부분에 item을 추가하고,
Dequeue는 가장 앞부분의 item이 나가게 된다.

Stack과 Queue의 가장 큰 차이점은 item을 삭제할 때 있다.

아이템을 삭제할 때, Stack은 가장 마지막에 추가되 있던 item을 삭제하고, Queue는 가장 처음으로 들어와 있던 item을 삭제한다.

Stack과 Queue 모두 Peek을 사용할 수 있다. Peek operation은 자료구조의 변화를 주지않고, Pop이나, Dequeue를 할 때 리턴되는 아이템을 리턴 할 수 있다.

 

---

 

2. Tree와 Graph의 차이점은 무엇인가요?

- 트리는 그래프의 한 종류이다.
- 그래프 중에서 연결에 방향이 없고 또한 순환하는 사이클이 없는 그래프를 트리라고 정의한다.

- 컴퓨터 공학의 자료구조에서 트리는 수학의 트리와 기본적으로 동일하지만
- 자료구조에서의 트리는 노드간에 부모-자식 관계를 가지는 방향이 있는 연결을 가지고, 루트 노드를 가지고 있다.

그래프

- 노드와 노드간을 연결하는 간선으로 구성된 자료구조
- 즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 구조

- 그래프는 네트워크 모델이다
- 노드간에 2개 이상의 경로도 가능 하다
- 부모-자식 관계라는 개념이 없다
- 그래프는 순환 혹은 비순환 구조를 이룬다
- 그래프는 방향성이 있는 그래프와 방향성이 없는 그래프가 있다

 

트리

- 그래프와 같이 노드와 노드간을 연결하는 간선으로 구성된 자료구조

- 그래프의 한 종류이다
- 방향성이 있으며 사이클이 존재하지 않는다 (비순환 그래프)
- 부모-자식 관계라는 개념이 있으며 최상위에 루트 노드가 존재한다

 

즉 둘의 차이점은

>

Tree는 방향성이 있는 비순환 그래프이기 때문에 Cycle이 존재하지 않으나 Graphs는 노드와 노드를 연결하는 엣지(간선)로 구성되어 있는 자료구조이므로 순환, 비순환 모두 존재 가능합니다. (즉 Cycle이 있을 수도 있고 없을 수도 있습니다.) 또한 Tree는 방향 그래프만 존재하지만 Graph는 방향, 무방향 둘 다 존재합니다.

 

Tree는 Root Node라는 개념이 존재하고, 계층적 구조를 가지고 있기 때문에 부모-자식 관계가 존재하지만 Graph는 Root Node 개념 자체가 존재하지 않기 때문에 부모-자식 관계가 존재하지 않습니다.

 

---

3. 이진 탐색 방법에 대해 설명할 수 있나요?

이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘입니다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교하고, X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색합니다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교합니다. 이런 식으로 해당 값을 찾을 때까지 이 과정을 반복하는 방법입니다. (Ex. 업다운 게임)

 

*이진 탐색 트리에 대해 질문이 들어올 수 있습니다.

이진 탐색 트리란 이진 탐색(binary search)과 연결 리스트(linked list)를 결합한 이진트리를 말합니다. 이진 탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐습니다.