1. 이진 탐색 트리의 시간 복잡도가 가장 나쁜 경우를 설명하고 이때 시간 복잡도를 제시하시오.
O(N)
한쪽으로만 치우친 편향트리가 되는 경우 트리의 높이가 V가 된다.
이를 탐색하게 되면 루트부터 리프까지 모든 노드를 확인해야하기 때문이다.2. 다음 인접 리스트 형태의 그래프에서 DFS의 방문 순서를 출력하시오. 시작 정점은 1임.
graph = {
1: [2, 3],
2: [4],
3: [],
4: []
}> 1 → 2 → 4 → 3
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(__________)> graph[node]
ex)
node = 1
graph[1] = [2, 3]
queue.extend(graph[node])
# -> queue.extend([2, 3])BFS의 핵심
노드 꺼내기 -> 방문처리 -> 노드의 이웃들을 큐에 넣기
4. 어떤 사람이 한 번에 1칸 또는 2칸을 올라갈 수 있는 계단이 있다. 계단의 총 개수 N이 주어졌을 때, 이 사람이 계단을 올라가는 서로 다른 방법의 수를 구하는 프로그램을 반복문과 DP를 이용하여 파이썬으로 작성하시오.
# 함수의 리턴 : 서로 다른 방법의 수
# n은 1 이상의 값으로 가정
def climb_stairs(n: int) -> int:
# DP 테이블 초기화
dp = [0] * (n + 1)
# 함수의 나머지를 작성
if n<=1:
return 1
if n==2:
return 2
dp[1]=1
dp[2]=2
for i in range(3,n+1):
dp[i]=dp[i-1]+dp[i-2]
return dp[n]5. 현대 컴퓨터 시스템에서 CPU와 메인 메모리 사이에 L1, L2, L3 캐시를 두는 이유를 프로세서와 메모리 간의 성능 격차 관점에서 설명하시오.
제출했던 답:
cpu는 빠르고 메인메모리는 느리다.
cpu에서 어떤 요청을 메모리에 보냈을때 cpu의 대기시간이 메모리가 일하는 시간에 따라 너무 느려지고 그만큼의 비는 시간이 생기게 된다.
이를 방지하기 위해 캐시를 둔다
지역성을 이용해 캐시에 최근에 사용한 데이터를 저장해두면 메인메모리까지 가는 시간보다 빠르게 원하는 값을 읽어올 수 있다
추가하면 좋을 것 같은 부분:
캐시는 작고 빠른 L1부터, 상대적으로 크지만 느린 L2와 L3까지 계층적으로 구성된다. 각 하위 메모리 계층은 상위 메모리의 캐시 역할을 하기 때문에 큰 캐시 메모리 하나를 사용할 때보다 계층적으로 접근함으로서 평균적으로 보다 빠르게 메모리를 읽어올 수 있다.
6. 유닉스(Unix) 계열 시스템은 POSIX라는 공통 표준을 따른다. 운영체제에 이러한 표준이 필요한 이유에 대해, 본인의 생각을 중심으로 서술하시오.
(표준의 역할, 개발자/사용자 관점, 시스템 호환성 등 다양한 측면에서 접근해도 좋습니다.)
제출한 답:
개발자는 다른 환경에서 개발을 해도 같은 표준을 따름으로서 다른 환경에서도 같은 프로그램의 테스트가 가능하고, 사용자의 경우에도 mac이나 window등으로 다른 사용 환경에서 프로그램을 실행하는 것에 구애받지 않을 수 있을 것 같다.
수정하면 좋을 것 같은 부분:
Windows는 기본적으로 POSIX 기반 Unix 계열 OS가 아님
POSIX가 주는 장점:
같은 API/인터페이스
→ 소스코드를 쉽게 이식
→ OS별 수정량 감소
정리하면,
POSIX와 같은 표준이 있으면 서로 다른 Unix 계열 운영체제에서도 공통된 시스템 인터페이스를 사용할 수 있다. 따라서 개발자는 운영체제마다 프로그램을 완전히 새로 작성할 필요가 없으며 프로그램의 이식성과 호환성이 높아진다. 사용자 입장에서도 특정 운영체제에 대한 의존성이 줄어드는 장점이 있다.
7. 브라우저에서 여러 개의 탭(또는 창)을 동시에 열 때, 멀티스레드와 멀티프로세스 중 어떤 방식이 더 유리하다고 생각하는가? 본인의 선택과 그 이유를 구체적으로 서술하시오. (성능, 안정성, 자원 관리 측면 등에서 고려할 것)
제출한 답:
멀티스레드
여러 탭을 사용하게 되면 그 탭들간의 지속적인 컨텍스트 스위칭이 필요할텐데, 커널이 여러 프로세스에 접근하는 것보다 하나의 프로세스를 다루고, 그 안에서 스레드들로 관리하는 차원이 비용적으로 더 나을 것 같다.
스레드
→ 같은 주소 공간 공유
→ 생성/전환 비용 상대적으로 작음
→ 자원 공유 쉬움+
브라우저에서는 일반적으로 멀티프로세스 방식 또는 멀티프로세스+멀티스레드 혼합 구조가 유리한 중요한 이유
ex)
[Browser]
│
├─ Tab A Process
├─ Tab B Process
└─ Tab C Process
-> Tab B가 죽더라도
Tab A ✅ ->
Tab B 💥 다른 탭이 살아 있을 수 있음
Tab C ✅ -> 반대로 하나의 프로세스에서 여러 스레드로만 처리
-> 같은 주소 공간을 공유하기 때문에 한 스레드의 심각한 오류가 전체 프로세스에 영향을 줄 가능성이 있음
