[정글 WEEK02_알고리즘] 개발 일지 - 퀴즈

퀴즈

1. 해시 충돌이 발생하는 원인과 해시 충돌 해결법 중 체이닝에 대한 설명

2.  Merge Sort 구현

3. 링버퍼를 이용한 Queue 구현

4. 캐시 메모리 사용 시 컴퓨터 시스템 성능 향상의 이유를 '지역성' 개념으로 설명

5. 프로세스와 스레드의 차이점

---

 

퀴즈를 통해 보완한 점

1. 직접 구현해보면서 진짜로 이해하게 된 병합 정렬(Merge Sort)의 원리  

병합 정렬은 배열을 앞, 뒤 두 영역으로 나눠서 각각 정렬 후 병합하는 과정을 재귀적으로 수행하는 알고리즘이다. 

이러한 정의에 대한 암기를 넘어 직접 구현해보면서 이해도가 확 올라갔다. 

 

🔍 원리는 아래와 같다.

a 라는 배열을 병합 정렬할 때, 

① a의 절반을 임시 저장할 buffer 배열에 a 배열의 앞부분 절반을 삽입한다.  

② buffer의 요소와 a의 뒷부분 절반의 요소를 비교하면서 더 작은 요소를 a에 삽입하는 과정을 반복한다. 이 때, 두 배열은 미리 병합정렬되어있다.  

③ buffer에 남은 부분이 있다면 a의 마지막 부분에 삽입한다. 

 

Merge Sort 원리

 

⌨️ 코드는 아래와 같다.

def merge_sort(a):
    if len(a) <= 1:
        return a  # base case: 정렬 완료

    mid = len(a) // 2
    left = merge_sort(a[:mid])     # 위 설명에서 buffer에 해당
    right = merge_sort(a[mid:])    # 위 설명에서 a에 해당

    return merge(left, right)      
    
def merge(left, right):
    result = []
    i = j = 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 += left[i:]
    result += right[j:]
    return result

 

2. 링버퍼에 대한 개념 이해와 링버퍼를 이용한 Queue 구현 

📌 링버퍼는 배열 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조로,

링버퍼를 사용해 큐를 구현하면 deque()로 요소를 삭제해도 배열 안의 원소를 이동시키지 않을 수 있다.

코드는 아래와 같다. 

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 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():
            raise Exception
        self.que[self.rear] = x
        self.rear += 1
        self.no += 1
        if self.rear == self.capacity:
            self.rear = 0
    
    def deque(self) -> Any:
        if self.is_empty():
            raise Exception
        x = self.que[self.front]
        self.front += 1
        self.no -= 1
        if self.front == self.capacity:
            self.front = 0
        self.que[self.front]

 

 

3. 캐시 메모리의 공간 지역성과 시간 지역성에 대한 이해 

'지역성'은 프로그램이 메모리에 접근할 때 특정 부분을 집중적으로 사용하는 경향을 말한다. 

이 중 '공간 지역성'은 한 번 접근된 데이터의 주변 주소에 있는 데이터들이 곧 접근될 가능성이 높다는 개념으로, 대표적인 예로 '배열의 연속적인 메모리 블록'이 있다. 

'시간 지역성'은 한 번 접근된 데이터는 짧은 시간 내에 다시 접근될 가능성이 높다는 개념이고, 예시로 '루프 안에서 반복 사용되는 변수'가 있다.

CPU는 이러한 지역성 원리를 활용해, 자주 사용될 것으로 예상되는 데이터를 캐시 메모리에 미리 저장함으로써 메인 메모리와의 거리로 인한 오버헤드를 줄여 전체 프로그램 성능을 크게 향상시킬 수 있다.