[CS Study] Data Structures (자료구조)

1. 자료구조와 알고리즘의 개념에 대해 서술하세요.

• 자료구조: 데이터를 효율적으로 저장, 관리, 검색하기 위한 구조 → 예: 배열, 연결리스트, 해시테이블, 트리 등
• 알고리즘: 문제를 해결하기 위한 일련의 절차나 방법 → 예: 정렬, 탐색, 최단 경로 등

둘은 밀접한 관계: 좋은 알고리즘도 적절한 자료구조 없이는 비효율적일 수 있음

---

2. 그래프와 트리의 차이점에 대해 설명하세요.

항목 그래프 트리

루트 노드	없음	하나의 루트 존재
순환	가능	불가능 (비순환)
방향성	무방향 / 방향 가능	방향성 있음
연결성	부분 연결 가능	모든 노드가 연결되어야 함
구조	일반적 연결 관계	계층적 구조

---

3. 이진 탐색 트리에 대해 설명해주세요.

• 이진 탐색 트리(BST)는 이진 트리의 한 종류
• 노드의 왼쪽 자식 < 현재 노드 < 오른쪽 자식
• 중복된 값은 일반적으로 허용하지 않음
• 평균 시간 복잡도: O(log n), 최악: O(n)

---

4. AVL 트리에 대해 설명하세요. *

• 자기 균형 이진 탐색 트리
• 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이 ≤ 1
• 균형이 깨질 경우 회전 연산 수행 (LL, RR, LR, RL 회전)
• 항상 균형을 유지하여 탐색 성능 보장

---

5. 레드블랙 트리에 대해 설명해주세요. *

• 이진 탐색 트리 기반의 균형 이진 트리
• 각 노드는 빨강/검정으로 색칠
• 규칙을 통해 트리의 균형을 보장
  • 루트는 항상 검정
  • 빨강 노드가 연속으로 올 수 없음
  • 모든 경로에 검정 노드 수 동일
• AVL보다 느리지만 회전 횟수가 적어 실용적

---

6. 스택과 큐에 대해 설명하세요.

구조 스택 (Stack) 큐 (Queue)

동작 방식	LIFO (후입선출)	FIFO (선입선출)
주요 연산	push(), pop()	enqueue(), dequeue()
사용 예	함수 호출, 되돌리기	작업 대기열, BFS

---

7. Array 와 ArrayList 의 차이에 대해 설명하세요. *

• Array
  • 고정 크기
  • 타입 지정
  • 빠른 인덱스 접근
• ArrayList
  • 크기 동적 조절 가능
  • 내부적으로 배열 기반
  • 삽입/삭제 유연

---

8. 배열과 연결리스트의 장단점에 대해 설명하세요.

항목 배열 연결리스트

접근 속도	빠름 (인덱스로 O(1))	느림 (O(n))
삽입/삭제	느림 (복사 필요)	빠름 (포인터만 수정)
메모리	연속된 공간	비연속적 공간 사용 가능
메모리 낭비	적음	포인터로 메모리 추가 소모

---

9. 해시테이블(Hash Table)에 대해 설명하세요.

• Key에 해시 함수 적용 → Index → Value 저장
• 평균 시간 복잡도: O(1)
• 충돌 방지 기법 필요 (체이닝, 오픈 어드레싱 등)

---

10. list, set, map 의 차이에 대해 설명하세요.

자료형 설명

list	순서 유지, 중복 허용
set	순서 없음, 중복 불가
map (dict)	key-value 쌍 저장, 키 중복 불가

---

11. B+ Tree 가 무엇인지 설명해주세요. *

• 데이터베이스에서 사용되는 균형 트리
• 리프 노드에만 데이터 저장
• 내부 노드는 인덱스 역할
• 범위 검색과 순차 접근에 최적화

---

12. HashMap 은 어떤 식으로 동작하나요?

• Key → 해시 함수 적용 → 배열 인덱스 → Value 저장
• 충돌 시 LinkedList 또는 Tree 구조 사용 (Java 8 이후)

---

13. Hash 충돌이 발생하는 경우는 무엇인가요?

• 서로 다른 키가 같은 해시 값을 갖는 경우
• 해시 공간이 부족하거나 해시 함수가 불균형할 때

---

14. Hash 충돌 시에 내부 데이터 탐색은 어떻게 하나요?

• 체이닝: 동일 해시 값을 가진 요소를 연결 리스트로 저장
• 오픈 어드레싱: 빈 슬롯 탐색 (선형/제곱/이중 해시 방식)

---

15. 컬렉션에 대해서 설명해주세요. **

• 객체들을 효율적으로 다루기 위한 자료구조 모음
• Java 기준: List, Set, Map 등이 포함됨
• Collection Framework는 다양한 알고리즘과 구현체 제공

---

16. 쓰레드를 만들 때 어떤 자원을 많이 사용하게 되나요?

• 스택 메모리: 함수 호출, 지역 변수 저장
• CPU 스케줄링 자원: 문맥 전환 비용
• 동기화 비용: 락, 세마포어 등 사용 시

---

17. Thread 와 Process 의 차이는 무엇인가요? 어떤 상황에서 threading 을 해야 하고 어떤 상황에서 processing 을 해야하나요? **

항목 Thread Process

메모리 공유	O (같은 공간)	X (독립 공간)
생성/종료 비용	낮음	높음
독립성	낮음 (다른 쓰레드 영향 받음)	높음

• Threading: I/O 병렬 작업, 가벼운 작업 병렬 처리
• Processing: 독립적 작업, 리소스 충돌 위험이 있는 작업

---

18. Thrashing 이 무엇인가요?

• 페이지 부재(Page Fault)가 너무 자주 발생해 시스템이 페이지 교체만 하느라 실질 작업을 못하는 상태
• 원인: 프로세스 수 과다 + 메모리 부족

---

19. Mutex 와 Spinlock 의 차이는 무엇인가요?

항목 Mutex Spinlock

대기 방식	대기 중 sleep	계속 루프 돌며 대기 (busy waiting)
CPU 자원	적게 소모	많이 소모
사용 상황	일반적 동기화	짧은 잠금 예상 시 유리

---

20. 검색 자료구조로서 해쉬 테이블과 바이너리 서치 트리를 비교해주세요.

항목 해시테이블 이진 탐색 트리

평균 탐색 속도	O(1)	O(log n)
정렬	불가능	가능
충돌	있음	없음
범위 쿼리	비효율적	효율적

---

21. 컴파일러와 인터프리터를 비교해서 설명해주세요.

항목 컴파일러 인터프리터

실행 방식	전체 코드를 번역 후 실행	한 줄씩 해석하며 실행
실행 속도	빠름	느림
오류 감지	컴파일 시 전체 확인	실행 중 오류 발생 가능
예시 언어	C, C++	Python, JavaScript

---

22. 스택에서 다른 스택으로의 자원을 서로 공유할 수 있나요?

• 일반적으로 스택 메모리는 스레드마다 독립적
• 직접 공유는 불가능
• 공유하려면 Heap 영역 등을 사용해야 함

---

23. 최소 스패닝 트리란 무엇인가요?

• 가중치가 있는 그래프에서모든 정점을 최소 비용으로 연결하는 트리
• 대표 알고리즘: Kruskal, Prim

---

24. 메모이제이션을 적용할 수 있는 알고리즘에 대해서 설명하여 보세요.

• 중복되는 부분 문제가 있는 경우
• 탑다운 방식 + 결과를 캐시에 저장
• 예: 피보나치 수열, DP, DFS + 메모이제이션

---

25. 스레드를 통해 생성된 영역은 다른 스레드에 접근이 가능한가요?

• Stack 영역: 각 스레드 고유, 접근 불가
• Heap 영역: 공유 가능 → 전역 데이터 접근/변경 가능

---

26. 선형구조의 형태의 자료형에서 가산성과 동차성에 대해서 설명해보세요.

• 가산성(Additivity): 전체가 부분의 합으로 구성
• 동차성(Homogeneity): 동일한 성질/구조의 원소로 구성

---

27. 병렬 프로그래밍에 대해 설명해보세요. *

• 여러 작업을 동시에 수행하여 처리 속도 향상
• 멀티스레드, 멀티프로세싱, GPU 등으로 구현
• 고려 요소: 동기화, 자원 공유, Race Condition

---

28. 배열 안 중복제거를 위한 방법이 뭐가 있을까요?

• Set 자료형 사용
• 정렬 후 인접 원소 비교
• 해시 테이블 활용
• 리스트 컴프리헨션 + 조건문

---

29. Enum 사용해보셨나요? Enum 이란 무엇인가요?

• 열거형(Enumeration): 상수들의 집합
• 코드 가독성 향상, 타입 안정성 제공

30. char type 과 string type 으로 나뉘어져 있는 이유는 무엇인가요?

• char: 문자 하나 ('a'), 고정 크기
• string: 문자의 집합 ("abc"), 가변 크기
• 구분함으로써 메모리 최적화 및 유형 안정성 확보 가능