헤맨 만큼 내 땅이다
week3 퀴즈 본문
이진 탐색 트리, DFS/BFS, DP, 캐시 계층, POSIX, 멀티스레드/프로세스까지 — 자료구조와 운영체제의 핵심 개념을 문제 풀이 형식으로 정리했습니다.
1. 이진 탐색 트리(BST)의 최악의 시간 복잡도
문제
이진 탐색 트리의 시간 복잡도가 가장 나쁜 경우를 설명하고 이때 시간 복잡도를 제시하시오.
정답
이진 탐색 트리에 데이터가 정렬된 순서(오름차순 또는 내림차순)로 삽입되면, 트리가 한쪽으로만 뻗어나가는 편향 트리(skewed tree) 형태가 됩니다. 이 경우 트리의 모양이 사실상 연결 리스트와 같아집니다.
시간 복잡도: O(n)
균형 잡힌 트리에서는 탐색/삽입/삭제가 O(log n)이지만, 편향된 트리는 트리의 높이만큼 비교 연산을 수행해야 하므로 최악의 경우 선형 시간이 걸립니다.
2. DFS 방문 순서
문제
graph = {
1: [2, 3],
2: [4],
3: [],
4: []
}
시작 정점이 1일 때 DFS 방문 순서는?
정답: 1 → 2 → 4 → 3
풀이 과정
- 1 방문 → 이웃 [2, 3] 중 첫 번째인 2로 이동
- 2 방문 → 이웃 [4]로 이동
- 4 방문 → 이웃이 없으므로 되돌아감(백트래킹)
- 2, 1로 돌아왔지만 남은 이웃이 없다가, 1에서 아직 방문 안 한 3이 남아있음
- 3 방문
DFS는 "한 갈래 길을 끝까지 파고든 뒤 막히면 되돌아가는" 방식이라, BFS(같은 레벨을 먼저 순회)와 방문 순서가 다릅니다.
3. BFS 코드 빈칸 채우기
문제
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
queue.extend(__________)
정답
queue.extend([n for n in graph[node] if n not in visited])
설명
graph[node]의 이웃 노드들 중 아직 방문하지 않은(not in visited) 노드만 골라 큐에 추가하는 코드입니다. 이미 방문한 노드를 다시 큐에 넣지 않도록 필터링하는 것이 핵심입니다.
4. 계단 오르기 DP
문제
한 번에 1칸 또는 2칸을 오를 수 있는 계단에서, N칸을 오르는 방법의 수를 반복문과 DP로 구하시오.
정답
def climb_stairs(n: int) -> int:
dp = [0] * (n + 1)
dp[0] = 1 # 0칸일 때 방법은 1가지 (아무것도 하지 않음)
if n >= 1:
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
원리
n번째 계단에 도달하는 방법의 수는 (n-1)번째 계단에서 1칸을 오르거나, (n-2)번째 계단에서 2칸을 오르는 경우의 합입니다. 이는 피보나치 수열과 동일한 점화식 구조를 가집니다.
5. CPU-메모리 성능 격차와 캐시 계층 구조
문제
현대 컴퓨터 시스템에서 CPU와 메인 메모리 사이에 L1, L2, L3 캐시를 두는 이유를 프로세서와 메모리 간의 성능 격차 관점에서 설명하시오.
정답
CPU의 처리 속도는 매년 빠르게 향상되어 온 반면, 메인 메모리(DRAM)의 속도 개선 속도는 그보다 훨씬 느려서 CPU와 메모리 간 성능 격차(memory wall)가 지속적으로 벌어져 왔습니다.
CPU가 매번 메인 메모리에 직접 접근하면 데이터를 기다리는 대기 시간이 길어져 전체 시스템 성능이 저하됩니다. 이를 완화하기 위해 CPU와 메모리 사이에 속도는 빠르지만 용량이 작고 비싼 캐시(SRAM)를 다음과 같이 계층적으로 배치합니다.
- L1: 가장 빠르고 용량이 작으며, 코어마다 전용으로 존재
- L2: L1보다 크고 다소 느리며, 코어별 또는 소수 코어가 공유
- L3: 여러 코어가 공유하는 상대적으로 크고 느린 캐시
이러한 계층 구조는 지역성 원리(자주 사용하는 데이터가 다시 사용될 가능성이 높다는 원리)를 활용해 메인 메모리 접근 횟수를 줄이고, 평균 메모리 접근 시간을 단축시켜 CPU-메모리 속도 격차로 인한 성능 손실을 최소화하는 역할을 합니다.
6. POSIX 표준이 필요한 이유
문제
유닉스 계열 시스템은 POSIX라는 공통 표준을 따른다. 운영체제에 이러한 표준이 필요한 이유를 서술하시오.
참고 논지
이 문제는 정해진 정답이 없는 서술형이지만, 아래와 같은 관점에서 접근할 수 있습니다.
- 개발자 관점: POSIX를 따르면 특정 OS 전용 API에 의존하지 않고 코드를 작성할 수 있어, Linux·macOS·BSD 등 여러 유닉스 계열 OS에서 재컴파일만으로 동작 가능 → 이식성(portability) 확보
- 사용자 관점: 어떤 유닉스 계열 시스템을 사용하든 셸 명령어와 파일 시스템 동작 방식이 유사하여 학습 비용이 감소
- 시스템 호환성: 벤더마다 제각각의 API와 명령어 체계를 만들면 생태계가 파편화되므로, 공통 표준이 상호운용성과 소프트웨어 생태계의 지속가능성을 보장
7. 브라우저 탭: 멀티스레드 vs 멀티프로세스
문제
브라우저에서 여러 탭을 동시에 열 때, 멀티스레드와 멀티프로세스 중 어떤 방식이 더 유리한가?
먼저, 두 개념의 차이
구분 멀티프로세스 멀티스레드
| 메모리 | 독립적 (공유하지 않음) | 같은 프로세스 내에서 공유 |
| 통신 방식 | IPC(프로세스 간 통신) 필요, 느림 | 메모리 공유로 직접 통신, 빠름 |
| 안정성 | 하나가 죽어도 나머지는 안전 | 하나가 죽으면 프로세스 전체에 영향 가능 |
| 생성 비용 | 큼 (메모리 공간을 새로 할당) | 작음 (메모리를 공유하므로 가벼움) |
| 보안/격리 | 강함 | 약함 (같은 메모리 공간 공유) |
비유: 멀티프로세스는 완전히 독립된 사무실 여러 개를 차리는 것이고, 멀티스레드는 하나의 사무실 안에 여러 직원이 함께 일하는 것과 같습니다. 사무실이 독립되어 있으면 한 곳에 불이 나도 다른 곳은 안전하지만, 서류를 주고받으려면 우편(IPC)을 거쳐야 해서 느립니다. 반대로 한 사무실을 공유하면 소통은 빠르지만, 불이 나면 사무실 전체가 위험해집니다.
참고 논지: 멀티프로세스가 유리한 이유
실제로 Chrome 등 현대 브라우저는 탭마다 별도 프로세스를 쓰는 멀티프로세스 구조를 채택하고 있습니다.
- 안정성: 한 탭이 크래시해도 다른 탭에는 영향이 없음. 스레드는 같은 메모리 공간을 공유하므로 하나가 죽으면 전체 프로세스가 죽을 위험이 있음
- 보안: 프로세스 간 메모리가 격리되어 있어, 한 탭의 악성 스크립트가 다른 탭의 데이터에 접근하기 어려움
- 자원 관리: OS 스케줄러가 프로세스 단위로 CPU 코어를 분배하기 용이함
단점(반론으로 활용 가능): 프로세스마다 독립된 메모리 공간을 가지므로 스레드보다 메모리 사용량이 크고, 프로세스 간 통신(IPC) 비용이 스레드 간 통신보다 높습니다.