WEEK 02 퀴즈 오답노트

Week02 퀴즈 오답노트

1. 해시 충돌이란 무엇이며 그것이 발생하는 원인과 해결하기 위한 다양한 방법들 중, 체이닝을 설명하세요.
   해시 충돌: 두 개 이상의 아이템이 동일한 저장공간에 지정되는 현상입니다.
   이는 해시 함수의 특정상 제한된 크기의 해시 테이블에 무한한 수의 가능한 키들을 매핑해야 하기 때문에 발생합니다. 즉, 다양한 키들이 동일한 해시 값을 가질 수 있기 때문에 충돌이 발생합니다.
   체이닝: 각 버킷에 연결 리스트(linked list)를 사용하여 여러 키-값 쌍을 저장하는 방법입니다.
   체이닝 장점: 해시 테이블의 크기에 영향을 받지 않고, 일정한 성능을 유지할 수 있다.
   체이닝 단점: 연결 리스트를 위한 추가 메모리가 필요하다. 연결 리스트가 길어지면, 해시
   테이블의 값을 찾는데 시간이 많이 소요될 수 있다.

2. 아래 코드는 분할 정복을 활용하여 병합 정렬(머지 소트)을 구현하는 코드 입니다. 비어있는
   merge 함수를 구현해 보세요.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)
    
### 답안 ###
def merge(left, right):
    result = []
    i, j = 0, 0 # 두 배열의 인덱스
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1 # 인덱스 증가
            
        else:
            result.append(right[j])
            j += 1 # 인덱스 증가
            
            # 남은 요소 추가(해당부분 추가)
            result.extend(left[i:])
            result.extend(right[j:])
        return result

3. 아래 코드는 링버퍼를 이용해서 큐를 구현한 예시입니다. 비어 있는 enque와 deque 함수를
   구현하세요.

from typing import Any
class FixedQueue:
 def __init__(self, capacity: int) -> None:
     self.no = 0 # 현재 데이터 개수
     self.front = 0 # 맨 앞 원소 커서
     self.rear = 0 # 맨 끝 원소 커서
     self.capacity = capacity # 큐의 크기
     self.que = [None] * capacity # 큐의 본체
     
     def __len__(self) -> int:
         return self.no
     def is_empty(self) -> bool:
         return self.no <= 0
     def is_full(self) -> bool:
         return self.no >= self.capacity
         
### 답안 ###
def enque(self, x: Any) -> None:
    if self.is_full():
        return
    self.que[self.rear] = x
    self.rear += 1
    self.no += 1
    
    if self.rear == self.capacity:
        self.rear = 0
        # 데이터를 큐에서 삭제
    
def deque(self) -> None:
    if self.is_empty():
        return
    x = self.que[self.front]
    self.front += 1
    self.no -= 1
    if self.front == self.capacity:
        self.front = 0
        return x

4. 캐시 메모리를 사용하면 컴퓨터 시스템의 성능이 왜 향상되는지 지역성(locality) 개념을
   포함하여 설명하세요.
   지역성은 프로그램이 메모리를 접근할 때 특정 부분을 집중적으로 사용하는 경향을
   나타냅니다. 이는 두 가지 형태로 나타납니다:

• 시간적 지역성(Temporal Locality): 한 번 접근된 데이터는 가까운 미래에 다시
  접근될 가능성이 높다는 원리입니다. 예를 들어, 루프 내에서 반복적으로 사용되는
  변수는 시간적 지역성의 좋은 예입니다.
• 공간적 지역성(Spatial Locality): 메모리의 특정 주소에 접근한 후, 그 주변 주소에
  있는 데이터에 접근될 가능성이 높다는 원리입니다. 이는 배열이나 연속적인 메모리
  블록에 접근할 때 종종 발생합니다.

캐시 메모리는 이러한 지역성 원리를 활용하여 자주 사용되거나 연속적으로 사용될
가능성이 높은 데이터를 미리 캐시에 저장합니다. 이로 인해 CPU는 필요한 데이터를
캐시에서 빠르게 찾을 수 있습니다.

5. 프로세스와 쓰레드의 차이를 설명하세요.
   [개념]
   프로세스: 독립적으로 실행되는 프로그램의 인스턴스로, 자체적인 주소 공간,
   메모리, 데이터 스택 및 다른 시스템 자원을 갖습니다.
   쓰레드: 프로세스 내부의 실행 흐름 단위로, 프로세스의 자원과 주소 공간을
   공유하면서 실행됩니다.
   [자원 공유 방식]
   프로세스: 각 프로세스는 독립적인 메모리 공간과 시스템 자원을 가지므로,
   프로세스간 자원 공유는 IPC (Inter-Process Communication) 메커니즘을 통해
   이루어집니다.
   쓰레드: 같은 프로세스 내의 쓰레드들은 코드, 데이터 및 시스템 자원을 공유합니다.