오늘 하루 요약

✏️오늘의 한 일

• CSAPP 9.9
• JS algorithm - 1978.소수찾기

🌈오늘의 성장!

Malloc LAB 기본구조

CSAPP 9.9

가용 블록 관리 방식 3가지

1) 묵시적 가용 리스트 (Implicit Free List)

• 특징:

  • 모든 블록(할당된 블록 + 가용 블록)을 순서대로 탐색.
  • 블록의 헤더에 저장된 크기와 할당 여부를 통해 블록 상태를 확인.
  • 가용 블록끼리 따로 연결 X, 전체 힙을 순회하면서 찾음.

• 장점:

  • 구조가 단순하고 구현이 쉬움.
  • 블록 관리 포인터가 필요 없어 공간 절약.

• 단점:

  • 탐색 속도 느림 → O(n), 힙 전체를 확인해야 할 수도 있음.
  • 블록 수가 많아지면 성능 급격히 저하.

• 적합한 경우:

  • 간단한 할당기 구현할 때 사용.
  • 성능보다 구조 단순성이 우선일 때.

---

2) 명시적 가용 리스트 (Explicit Free List)

• 특징:

  • 가용 블록끼리만 포인터로 연결 → 이중 연결 리스트 사용.
  • 각 가용 블록 내부에 이전/다음 가용 블록 포인터 포함.
  • 할당된 블록은 리스트에서 제외되므로 탐색 범위가 줄어듦.

• 장점:

  • 탐색 속도 빠름 → O(free blocks), 가용 블록만 보므로 효율적.
  • 블록 삽입/삭제가 빠름 (O(1) 가능).

• 단점:

  • 블록마다 추가 포인터 공간 필요 → 오버헤드 증가.
  • 리스트 관리 복잡도 증가 (삽입/삭제 시 포인터 갱신 필요).

• 적합한 경우:

  • 성능이 중요한 상황.
  • 가용 블록이 많고, 빠른 할당/반환이 필요한 경우.

---

3) 분리 저장 리스트 (Segregated Free List)

• 특징:

  • 블록 크기별로 여러 개의 가용 리스트를 따로 유지.
  • 비슷한 크기의 블록들끼리 분리해서 관리.
  • 예: 8바이트, 16바이트, 32바이트, ..., 1024바이트 이상 등으로 구분.

• 장점:

  • 탐색 속도 매우 빠름 → 해당 크기 리스트만 탐색하면 됨.
  • 메모리 활용도 높음 → 블록 쪼개기, 병합이 효율적.
  • First-Fit처럼 빠르면서도 Best-Fit에 가까운 효율 제공.

• 단점:

  • 리스트가 여러 개라 구조가 복잡해짐.
  • 작은 블록의 경우 내부 단편화 가능성 ↑.

• 적합한 경우:

  • 실무에서 많이 사용되는 고성능 할당기.
  • 다양한 크기의 메모리 요청을 빠르게 처리해야 할 때.
  • 실제 glibc malloc도 이 방식 기반.

---

정리 비교

구분	묵시적 가용 리스트	명시적 가용 리스트	분리 저장 리스트
구조	모든 블록 순차 탐색	가용 블록만 포인터로 연결	크기별로 다수의 리스트 유지
탐색 속도	느림 (O(n))	빠름 (O(가용 블록 수))	매우 빠름 (리스트 하나만 탐색)
공간 효율	포인터 공간 없음	포인터 공간 필요	포인터 + 다수 리스트 공간 필요
구현 난이도	쉬움	중간	어려움
단편화 대응	낮음	중간	높음
사용 사례	간단한 할당기	성능 요구되는 시스템	고성능 할당기, 실무용 (glibc 등)

JS - 1978. 소수 찾기

https://www.acmicpc.net/problem/1978

• 제곱근 활용
  • flag 변수를 함수 안으로 집어넣어 이전 판별 결과의 영향이 가지 않게 하자...!

const fs = require("fs");
const input = fs.readFileSync("input.txt").toString().split('\n');

// 1. 입력받기
let N = parseInt(input[0]);
let arr = input[1].split(' ').map(Number);
let answer = 0;
// 2. 소수 판별 함수

function is_sosu(num) {
  let is_sqrt = true;
  if (num == 1) {
    is_sqrt = false;
    return;
  }

  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i == 0) {
      is_sqrt = false;
      break;
    }
  }
  if (is_sqrt) {
    answer++;
  }
}

arr.forEach(num => is_sosu(num));

console.log(answer);

• 에라토스테네스의 체

모든 수를 소수라고 가정하고 시작.
2부터 시작해서 그 수가 소수이면, 그 수의 배수는 모두 소수가 아님으로 처리

예: 2는 소수니까 4, 6, 8, 10, ... 이런 애들은 전부 소수 아님.
다음 3 → 소수니까 6, 9, 12, ... 전부 제거.

이 과정을 √N까지 반복하면, √N 이상의 수의 배수는 이미 제거되었기 때문에 더 이상 볼 필요 없음.

const fs = require("fs");
const input = fs.readFileSync("input.txt").toString().split('\n');

// 1. 입력받기
let N = parseInt(input[0]);
let arr = input[1].split(' ').map(Number);

// 2. 최대값을 구해서 그까지 체 만들기
let maxNum = Math.max(...arr);
let isPrime = new Array(maxNum + 1).fill(true);
isPrime[0] = false;
isPrime[1] = false;

// 3. 에라토스테네스의 체
for (let i = 2; i <= Math.sqrt(maxNum); i++) {
  if (isPrime[i]) {
    for (let j = i * i; j <= maxNum; j += i) {
      isPrime[j] = false;
    }
  }
}

// 4. 입력받은 숫자 중 소수인 것만 카운트
let answer = 0;
arr.forEach(num => {
  if (isPrime[num]) answer++;
});

console.log(answer);

⛏오늘의 삽질

오랜만에 하려니 입력받기부터 힘드네^^