[TIL] CSAPP 9장 공부5 - segregated list(개념 공부)

1. 아침 문제 풀이

1. 1057번 - 토너먼트

import sys

N, kim, im = map(int, sys.stdin.readline().split())

count = 0
flag = True
if N % 2 == 0 : #참가자가 홀수일 경우
    N += 1
    
while N > 0 :
    # 다음 경기에서의 번호 구하기
    if kim % 2 == 0 and im % 2 == 0:
        kim //= 2
        im //= 2
    elif kim % 2 != 0 and im % 2 == 0:
        kim = (kim+1) //2
        im //= 2
    elif kim % 2 == 0 and im % 2 != 0:
        kim //= 2
        im = (im+1) //2
    else :
        kim = (kim+1) //2
        im = (im+1) //2
    count += 1
    # 둘의 번호가 같다면 대결한다는 의미
    if kim == im :
        flag = False
        break
    N //= 2

if flag :
    print(-1)
else :
    print(count)

kim , im 의 모든 짝수, 홀수 경우의 수를 생각해서 현재 번호를 바꿔줬다.
그리고 둘의 번호가 같은면 만났다는 의미이므로 반복문을 탈출했다.

이때 주의할 점은 N이 홀수일 경우에는 count가 모자를 수도 있으므로 +1을 더해주고 시작한다.

---

2. 분리 가용 리스트

1. segregated storage

• 모든 가능한 블록 크기를 size class라고 하는 동일 클래스의 집합들로 분리
• 할당기
  • 가용리스트의 배열을 관리
  • size class마다 크기가 증가하는 순서로 한 개의 가용 리스트를 가진다.
• 간단한 방식
  • 장점
    • 블록을 할당하고 반환하는 것이 모두 빠른 상수시간 연산이다.
    •  각 메모리 블록 내의 동일한 크기, 분할 불가, 연결 불가 등이 연합해서 블록당 오버헤드가 거의 없다.
    • 할당된 한 개의 블록의 크기는 그 주소로부터 추정할 수 있다.
    • 할당된 블록들을 헤더에 할당/가용 태그가 필요하지 않다.
  • 단점
    • 단순한 분리 저장장치는 내부와 외부 단편화에 취약하다.
    • 내부 : 가용 블록들이 분할되지 않는다.
    • 외부 : 가용 블록들이 연결되지 않는다.

2. 분리 맞춤 방식

• 빠르고 메모리 관리가 효율적이다.
  • 전체 힙이 아니라 힙의 특정 부분에 제한된다.
• 분리 가용 리스트의 단순한 first-fit 검색이 전체 힙을 best-fit 검색하는 것을 단순화한 것이다.

---

현재 다른 자료들을 참고하면서 구현은 완료했다.

하루종일 오류를 찾는라 시간을 다써버렸다.

내일 다 정리해야겠다.

 

🤜 현재 malloc-lab 과제 진행상황 🤛

1. implicit (first-fit) 구현 완료 - 54점

2. implicit (next-fit) 구현 완료 - 83점

3. explicit (first-fit, LIFO) 구현 완료 - 82점

4. segregated (best-fit) 구현 완료 - 84점

---

< 참고 >

🔗 https://velog.io/@emplam27/CS-그림으로-알아보는-메모리-동적할당-Implicit-Explicit-Segregated-list-Allocator

🔗 https://velog.io/@piopiop/C-분리-가용-리스트를-이용한-동적-메모리-할당기-구현MALLOC-LAB-4

🔗 https://velog.io/@gitddabong/week06.-malloc-lab-Segregated-list