[자료구조] CS 질문 & 답변 정리

질문

1. 배열과 연결 리스트의 차이

 

2. 각 자료구조의 시간복잡도 

시간복잡도	Array	Array list	Linked List	Doubly Linked List
삽입
삭제
조회
특징 및 장단점	1) 삽입/삭제 시 특징은? 2)최악의 경우를 고려한 시간복잡도는?	배열과의 차이점은?	최악의 경우를 고려한 시간복잡도는?	-

 

3. 연결리스트, 이중 연결리스트에서 삽입, 삭제, 조회의 시간복잡도가 O(1)이 나오려면 어떤 경우 인가?

 

4. 스택 & 큐의 형태에 대해 설명하시오

 

5. 이진 탐색 트리 탐색의 시간복잡도는?

 

6. 전위, 중위 후위에 대한 순서는?

 

전위: 

중위:

후위:

 

7. 우선순위 큐의 구조와 시간복잡도는?

 

8. 해시 테이블의 구조와, 조회가 빠른 이유는?

 

9. 해시 테이블의 충돌이 발생할때 분리 연결법(Seperate Chaning), 개방 주소법(Open Addressing)을 간략하게 설명

---

정답

1. 배열과 연결 리스트의 차이

배별은 정적인 자료구조로, 메모리가 고정적이어서 크기를 늘릴 수 없음, 데이터를 메모리의 순차적으로 저장함

리스트는 동적인 자료구조로, 메모리가 가변적, 저장된 데이터와 다음 데이터가 있는 메모리 주소를 가짐

 

 

2. 각 자료구조의 시간복잡도 

시간복잡도	Array	Array list	Linked List	Doubly Linked List
삽입	O(N)	O(N)	O(1)	O(1)
삭제	O(N)	O(N)	O(1)	O(1)
조회	O(1)	O(1)	O(N)	O(N)
특징 및 장단점	데이터가 메모리에 순차적으로 저장되어 있어, 삽입/삭제 시 위치에 따라 남은 데이터를 밀어줘야 됨	배열의 특징에 가변적인 성질만 추가됨	삽입/삭제 하려는 데이터가 맨 앞 이후라면, 모두 조회할 경우가 있어 최악의 경우 O(N)이 나올 수 있음 자신의 노드 위치를 알 경우 삽입은 1) 추가하려는 노드에 다음 주소값에 이전 노드의 주소값을 넣고, 2) 기존 노드에 추가하려는 노드를 넣으면 되서 O(1) 이지만, 삭제는 자신의 위치를 알아도 링크드 리스트에선 이전의 노드 위치를 모르기 때문에(앞에 위치만 앎) 이전 위치 노드에 대한 탐색을 위해 최악의 경우 O(N)이 됨	뒤에서 부터 접근이 가능해 접근이 가능해 조회 시 O(N/2) *Big O에서는 O(N)으로 표기됨

 

3. 이중 연결리스트에서 삽입, 삭제하는 시간복잡도가 O(1)이 나오려면 어떤 경우 인가?

노드의 위치를 알경우 해당 노드로 바로 접근해 삽입, 삭제를 O(1)로 할 수 있음

 

4. 스택 & 큐의 형태에 대해 설명하시오

Stack은 후입선출, 마지막에 들어온 값이 나가는 LIFO 구조  Ex.  1 2 3 4 5 6 <- pop하면 6이 나감

Queue는 선입선출, 먼저 들어온 값이 나가는 FIFO 구조 Ex. 1 2 3 4 5 6 <- pop하면 1이나감

 

5. 이진 탐색 트리 탐색의 시간복잡도는?

트리의 높이(Log2(N))으로 탐색시 빠르게 탐색가능

 

6. 전위, 중위 후위에 대한 순서는?

부모(Root)의 위치를 앞에 [전, 중, 후] 의 위치로 생각하자

전위 - 1. Root 방문   2. 왼쪽 방문    3. 오른쪽 방문 

중위 - 1. 왼쪽 방문   2. Root 방문    3. 오른쪽 방문

후위 - 1. 왼쪽 방문   2. 오른쪽 방문 3. Root 방문

 

 

7. 우선순위 큐의 구조와 시간복잡도는?

우선순위 큐는 우선순위가 높은 데이터를 먼저 꺼내기위해 고안되어서, 최대값, 최솟값을 찾아내는 이진 탐색 트리인 힙을 활용함 힙의 탐색 시간복잡도는 O(log2(N))

 

8. 해시 테이블의 구조와, 조회가 빠른 이유는?

해시테이블은 Key, Value 값으로 구성되어 있고, 데이터의 값이 배열에 저장되어 빠르게 탐색할 수 있음, 배열의 Idx를 키로 저장해둔 상태

 

9. 해시 테이블의 충돌이 발생할때 분리 연결법(Seperate Chaning), 개방 주소법(Open Addressing)을 간략하게 설명

분리 연결법은 배열(buckets)에 값에 메모리를 사용해 충돌된 주소값을 저장하는 방식

 

개방 주소법은 비어있는 해시 테이블의 공간을 활용하는 방식

 

 

참고자료

1. 리스트, 배열 https://m.blog.naver.com/raylee00/221944085465

2. 연결리스트, 이중연결리스트 https://yongkis.tistory.com/22

3. 트리 순회 https://yoongrammer.tistory.com/70

4. 해시테이블 https://mangkyu.tistory.com/102