728x90
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
728x90
'KraftonJungle2기 > Today I Learned' 카테고리의 다른 글
[TIL] CSAPP 11장 공부 - 네트워크 (2) | 2023.05.19 |
---|---|
[TIL] CASPP 9장 공부5 - 간단한 할당기3(segregated) (0) | 2023.05.17 |
[TIL] CSAPP 9장 공부4 - 간단한 할당기2(Explicit, first-fit) (1) | 2023.05.15 |
[TIL] CSAPP 9장 공부3 - next-fit (3) | 2023.05.14 |
[TIL] CSAPP 9장 공부3 - 간단한 할당기(Implicit, first-fit) (1) | 2023.05.14 |