[인프런 워밍업 클럽 4기 - CS] - 1주차 미션 (자료구조와 알고리즘 심화)

[인프런 워밍업 클럽 4기 - CS] - 1주차 미션 (자료구조와 알고리즘 심화)

강동훈 4개월 전

문제

Python, JavaScript, C# 같은 언어는 가비지 컬렉터를 이용해 메모리를 자동으로 정리하는 매니지드 언어(Managed Language)에 속합니다.

매니지드 언어의 가비지 컬렉터는 개발자가 메모리를 요청하면 운영체제의 힙 영역에 할당하고, 더 이상 필요하지 않을 때 자동으로 해제하며 메모리를 관리합니다.

여러분이 속한 회사에서 새로운 매니지드 언어를 개발 중이며, 여러분은 가비지 컬렉터 개발을 담당하게 되었습니다.

특히 메모리 검색 부분을 맡게 되었는데, 사용자가 특정 크기(Byte)의 메모리를 요청하면 사용 가능한 메모리 중 가장 적절한 크기를 찾아 반환하는 GarbageCollector 클래스를 구현해보세요.(같은 크기의 메모리는 없다고 가정)

import { AVLTree } from "./avlTree.mjs"

class GabageCollector{
  
}

const gc = new GabageCollector();
console.log("========== 빈 메모리 영역 초기화 ==========");
gc.insertFreeMemory(64); // 빈 64바이트 삽입
gc.insertFreeMemory(48); // 빈 48바이트 삽입
gc.insertFreeMemory(87); // 빈 87바이트 삽입
gc.insertFreeMemory(13); // 빈 13바이트 삽입
gc.insertFreeMemory(102); // 빈 102바이트 삽입
gc.insertFreeMemory(34); // 빈 34바이트 삽입
gc.insertFreeMemory(61); // 빈 61바이트 삽입
gc.insertFreeMemory(40); // 빈 40바이트 삽입
gc.insertFreeMemory(6); // 빈 6바이트 삽입

let freeMemory1 = gc.searchFreeMemory(64); // 64바이트 메모리
console.log(freeMemory1);
if(freeMemory1){
    gc.releaseFreeMemory(freeMemory1.data);
}

let freeMemory2 = gc.searchFreeMemory(42); // 48바이트 메모리 획득
console.log(freeMemory2);
if(freeMemory2){
    gc.releaseFreeMemory(freeMemory2.data);
}

 

풀이

import { AVLTree } from "./avlTree.mjs";

class GabageCollector {
    constructor() {
        this.tree = new AVLTree();
    }

    // 노드 추가
    insertFreeMemory(data) {
        this.tree.root = this.tree.insert(this.tree.root, data);
    }

    // 가장 인근의 노드 찾기
    searchFreeMemory(data) {
        if (this.tree.root === null) {
            return null;
        }

        let currentNode = this.tree.root;
        let parentNode = null;

        while (currentNode !== null) {
            // 현재 노드가 찾고자 하는 데이터보다 작을 경우 오른쪽 서브트리로 이동
            if (currentNode.getData() < data) {
                currentNode = currentNode.getRightSubTree();
            } else {
                // 찾고자 하는 데이터보다 큰 노드를 발견할 경우 부모 노드에 저장 후 왼쪽 서브트리로 이동
                parentNode = currentNode;
                currentNode = currentNode.getLeftSubTree();
            }
        }

        return parentNode ? parentNode : null;
    }

    // 노드 제거
    releaseFreeMemory(data) {
        this.tree.root = this.tree.remove(this.tree.root, data);
    }
}

const gc = new GabageCollector();
console.log("========== 빈 메모리 영역 초기화 ==========");
gc.insertFreeMemory(64); // 빈 64바이트 삽입
gc.insertFreeMemory(48); // 빈 48바이트 삽입
gc.insertFreeMemory(87); // 빈 87바이트 삽입
gc.insertFreeMemory(13); // 빈 13바이트 삽입
gc.insertFreeMemory(102); // 빈 102바이트 삽입
gc.insertFreeMemory(34); // 빈 34바이트 삽입
gc.insertFreeMemory(61); // 빈 61바이트 삽입
gc.insertFreeMemory(40); // 빈 40바이트 삽입
gc.insertFreeMemory(6); // 빈 6바이트 삽입

console.log("========== 삽입된 메모리 중위 순회 ==========");
gc.tree.root.inOrderTraversal(gc.tree.root);

console.log("========== 메모리 제거 1 ==========");
let freeMemory1 = gc.searchFreeMemory(64); // 64바이트 메모리
console.log(freeMemory1 ? freeMemory1.getData() : "매모리를 추가할 수 없습니다.");
if (freeMemory1) {
    gc.releaseFreeMemory(freeMemory1.data);
}
console.log("========== 메모리 제거 2 ==========");
let freeMemory2 = gc.searchFreeMemory(42); // 48바이트 메모리 획득
console.log(freeMemory2 ? freeMemory2.getData() : "매모리를 추가할 수 없습니다.");
if (freeMemory2) {
    gc.releaseFreeMemory(freeMemory2.data);
}

console.log("========== 변경된 메모리 중위 순회 ==========");
gc.tree.root.inOrderTraversal(gc.tree.root);

문제에서는 총 세 가지 메서드를 구현하여야 했다.

  1. insertFreeMemory: 빈 메모리를 삽입할 수 있는 기능

  2. searchFreeMemory: 데이터를 할당할 수 있는 최소의 메모리 공간을 검색하는 기능
    3. releaseFreeMemory: 해당 메모리를 삭제할 수 있는 기능

우선적으로 GarbaceCollector에서 메모리 영역은 하나의 AVL 트리로 다뤄진다고 생각을 하여서 this.tree 속성으로 AVL 트리를 생성해주었다.

 

insertFreeMemory의 경우, AVL Tree에서 제공해주는 insert 메서드를 통해 트리의 root를 설정해주고 그 하위에 적절한 위치를 찾아서 각 노드를 삽입해주었다.

 

releaseFreeMemory의 경우, 동일하게 AVL Tree에서 제공하는 remove 메서드를 통해 데이터를 찾아가며 해당 노드를 삭제하고 각 노드의 height나 unbalance한 노드의 균형을 잡아주었다.

 

searchFreeMemory는 새롭게 기능을 추가하여야 하였다. 처음에는 단순하게 매개변수의 데이터 값과 일치하는 노드만 반환하면 될 줄 알았지만 문제에서 '사용 가능한 메모리 중 가장 적절한 크기' 를 반환해야 한다고 적혀있듯 매개변수로 받는 데이터 이상의 노드들 중 최소값을 가진 노드를 반환해야 했다.

메서드를 작성하기 전에 먼저 예외처리를 하였다.

  1. AVL Tree의 루트 노드가 없을 경우

  2. 매개변수로 받는 데이터가 모든 노드의 값보다 클 경우

두 가지 경우에는 null을 반환하고 "매모리를 추가할 수 없습니다."라고 로그를 찍어주었다.

그 외의 경우에는 이제 while문을 통해 가장 인접한 값의 노드로 이동을 시켜주었다.

만약 현재 위치한 노드의 값이 찾으려는 데이터보다 작다면 우측 서브트리로 이동해주고,

데이터보다 큰 노드를 발견하게 된다면 부모 노드를 미리 저장해주고 좌측 서브트리로 이동해주었다.

  • 부모노드를 저장해주는 이유는 좌측 서브트리의 노드를 데이터보다 작을 수도 있기에 반환해줄 수 있는 노드 변수를 만들어주었다.

그렇게 while 문을 반복하다보면 현재 위치의 노드가 null이 나오게 되고 기저 조건을 벗어나서 결국 부모 노드에 저장된 노드값이 사용 가능한 메모리 중 가장 적절한 크기가 되며 부모 노드가 null이라면 아까처리한 예외 조건에 의해 로그가 찍히게 된다.

 

저번 기수보다 더 어려운 문제를 미션으로 출제하신다는 코치님의 말씀에 겁을 먹었었지만 막상 이렇게 실용적인 예제와 직접 구현을 해보면서 미션을 진행하다보니 기존에 배웠던 AVL Tree에 대해 더 자세히 익히게 되고 동작 방식이나 해당 자료구조에 대한 특징을 몸소 체험해볼 수 있었던 것 같다.

댓글을 작성해보세요.

채널톡 아이콘