[워밍업클럽4기-CS] 미션1 - 자료구조와 알고리즘

2025-06-01T12:09:33.181Z

아이디안해

문제

Python, JavaScript, C# 같은 언어는 가비지 컬렉터를 이용해 메모리를 자동으로 정리하는 매니지드 언어(Managed Language)에 속합니다. 매니지드 언어의 가비지 컬렉터는 개발자가 메모리를 요청하면 운영체제의 힙 영역에 할당하고, 더 이상 필요하지 않을 때 자동으로 해제하며 메모리를 관리합니다.

여러분이 속한 회사에서 새로운 매니지드 언어를 개발 중이며, 여러분은 가비지 컬렉터 개발을 담당하게 되었습니다. 특히 메모리 검색 부분을 맡게 되었는데, 사용자가 특정 크기(Byte)의 메모리를 요청하면 사용 가능한 메모리 중 가장 적절한 크기를 찾아 반환하는 GarbageCollector 클래스를 구현해보세요.(같은 크기의 메모리는 없다고 가정)

풀이

추상 자료형 정의
- 빈 메모리 삽입 : insertFreeMemory
- 적당한 크기의 메모리 검색 : searchFreeMemory
  - '적당한' 크기? : 요청된 사이즈보다 같거나 크면서 요청 사이즈와의 차이가 가장 적은 값
- 사용될 빈 메모리 제거 : releaseFreeMemory
insertFreeMemory
- gc에 새로운 노드 삽입 후 변환된 root 정보 반환
searchFreeMemory
- 변수 선언
  - currentNode : 현재 노드 정보
  - freeMemory : 반환될 메모리 사이즈에 해당하는 노드
- 검색(while)
  - 요청 사이즈와 동일한 사이즈의 메모리 존재 : freeMemory를 해당 노드로 업데이트 후 break
  - 요청 사이즈보다 현재 노드의 메모리 사이즈가 더 큰 경우
    - freeMemory != null이고, freeMemory가 현재 노드보다 더 작다면 대치 하지 않고 왼쪽 서브 트리 검색
    - freeMemory가 null이거나 현재 노드보다 더 크다면 freeMemory를 현재 노드로 대치 후 왼쪽 서브 트리 검색
  - 요청 사이즈보다 현재 노드의 메모리 사이즈가 더 작은 경우 : freeMemory를 대치하지 않고 오른쪽 서브 트리 검색
- 최종 freeMemory 값 반환
releaseFreeMemory
- 사용할 사이즈에 해당하는 노드를 제거

구현 코드


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

// 추상 자료형
// 빈 메모리 삽입 : insertFreeMemory
// 적당한 크기의 메모리 검색 : searchFreeMemory
// 사용될 빈 메모리 제거 : releaseFreeMemory

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

// 빈 메모리 삽입
insertFreeMemory(size){
    this.avlTree.root = this.avlTree.insert(this.avlTree.root, size);
}

// 적당한 크기의 메모리 검색
searchFreeMemory(size){
    let currentNode = this.avlTree.root;
    let freeMemory = null;

    while(currentNode != null){
        if(currentNode.getData() == size){ // 딱 맞는 사이즈인 경우
            freeMemory = currentNode;
            break;
        } else if(currentNode.getData() > size){ // 요청 사이즈보다 더 큰 경우
            if(freeMemory && freeMemory.getData < currentNode.getData()){
                // freeMemory가 null이 아니고, currentNode보다 값이 작으므로 대치 X
                currentNode = currentNode.getLeftSubTree(); 
            } else{ // freeMemory를 currentNode로 대치
                freeMemory = currentNode;
                currentNode = currentNode.getLeftSubTree();
            }
        } else{ // 요청 사이즈보다 더 작은 경우
            currentNode = currentNode.getRightSubTree();
        }
    }
    console.log('freeMemory', freeMemory.getData()); // 검색 결과 확인용
    return freeMemory;
}

// 사용될 빈 메모리 제거
releaseFreeMemory(size){
    this.avlTree.root = this.avlTree.remove(this.avlTree.root, size);
}

}

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바이트 삽입

gc.avlTree.root.inOrderTraversal(gc.avlTree.root); // 트리 확인

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);
}

실행 결과

========== 빈 메모리 영역 초기화 ==========
6
13
34
40
48
61
64
87
102
freeMemory 64
BinaryTree {
  data: 64,
  leftSubTree: BinaryTree {
    data: 34,
    leftSubTree: BinaryTree {
      data: 13,
      leftSubTree: [BinaryTree],
      rightSubTree: null,
      height: 2
    },
    rightSubTree: BinaryTree {
      data: 48,
      leftSubTree: [BinaryTree],
      rightSubTree: [BinaryTree],
      height: 2
    },
    height: 3
  },
  rightSubTree: BinaryTree {
    data: 87,
    leftSubTree: null,
    rightSubTree: BinaryTree {
      data: 102,
      leftSubTree: null,
      rightSubTree: null,
      height: 1
    },
    height: 2
  },
  height: 4
}
freeMemory 48
BinaryTree {
  data: 48,
  leftSubTree: BinaryTree {
    data: 40,
    leftSubTree: null,
    rightSubTree: null,
    height: 1
  },
  rightSubTree: null,
  height: 2
}

답변 0