3시 M님 특강

명시적 가용 리스트.

가용 블록을 어떤 순서로 연결하느냐에 따라
세 가지로 구성할 수 있다.

• 주소 순서.
• free 순서. (free 한 순서)
• 크기 순서. (작은 것에서 큰 순서.)
  (삽입이 좀 까다롭지만, best fit 같은 효과가 가능.)

여기서 M님은 가장 단순한 free 순서로 진행.

이 때 명시적 가용 리스트를 만들 때 신경 쓸만한 것은
맨 앞에 가용 리스트의 시작 지점이 될
루트 노드가 필요하다는 점이다.

(어디서부터 free 리스트를 시작할 지 기준을 정해야하니까.)

그리고 free 블록 안에
탐색은 next만으로 가능하지만,
free 블록 삭제의 경우 앞 블록과 뒷 블록을 연결해줘야하므로
그냥 처음부터 prev를 같이 넣는 게 낫다.

그리고 M님은 명시 가용 리스트의 맨 끝과 루트를 연결해서
circle 형태로 만들었다고 하셨음.
(대신 탐색시 루트 노드를 또 마주칠 경우 멈추도록.)

이렇게 circle 형태로 하면
루트 다음에 삽입할지(LIFO)
루트 앞에 삽입할지 (FIFO)
선택하는게 손 쉬워진다는 것.

현 테스트 케이스로는 LIFO가 유리하다고 함.

그렇게
free_insert, free_delete만 잘 구현한다면

• malloc
  딱 맞는 블록 찾으면 free -1
  더 큰 블록을 찾으면 free -1 +1(place시)
  extend로 새로 할당했을때 free +1

• free(시 마다 연결시)
  앞 뒤 불가 +1
  뒤 비었음 -1 +1
  앞 비었음 -1 +1
  앞뒤 비었음 -1 -1 +1

• realloc
  padding 충분하면 내버려둠
  새로 할때 malloc 방식.
  더 작아진 블록 +1

.... 이다!

4시 반 코어

힙정렬 퀴즈 대비용.

J님.
힙의 성질 설명.
(부모의 대소 관계에 따라 최대 힙, 최소 힙이 갈린다.)
(형제의 대소 관계는 상관이 없다)

힙 정렬을 위해 가장 큰 값을 빼는데,
그러고 나면 다시 힙화를 거쳐야한다.

현재 지점에서
가장 오른쪽 끝 노드를 루트에 올리고
현재 노드의 자식들과만 비교하여
자기보다 큰 자식을 올리되,
자식 중 값이 더 큰 애를 올리는 과정.

우선순위 큐 등에서 쓰는데
시간 복잡도는 .....몇이었더라.

아무튼 in-place(추가 메모리 공간을 쓰지 않고
자신의 기존 배열에서 끝남)이고 stable 하지 않다.
(만약 같은 값 3, 3, 이 있다면 항상 동일한 순서로 정렬되지 않고
시도 때마다 다른 순서로 정렬 될 수 있음.)

나.
이 힙들을
배열에 넣어서 계산하는데
레벨 순으로 넣되
왼쪽부터 오른쪽까지 쭉 넣기때문에
일정한 공식이 성립.

부모 (i-1)//2
왼 (i*2)+1
오 (ix2)+2

....

T님.
C언어로 구현.

재귀로 했더니 시간 초과가 나는것같음.

left, right, parent를 찾아서...
어차피 완전히 자식이 전혀 없는 노드는 힙화를 거칠 필요가 없기때문에
n//2+1 의 노드부터 순차적으로 확인하면 된다.

• 이미 현재 노드가 조건을 충족한 경우(부모 대소관계 일치)
  왼, 오 자식이 자기보다 작다면 넘어간다.
• 현재 노드가 조건을 충족하고 있지 않는 경우(부모 대소관계 불일치)
  왼, 오 자식이 자기보다 크다?
  그럼 왼, 오 중 누가 더 큰지 확인한다.
  더 큰 쪽과 swap 한다.
  swap한 노드를 현재 함수에 도로 집어넣는다!

여기서 size를 써가지고
만약 내가 참조하려는 배열의 숫자가 존재하지 않는다면
(그러니까, arr[9]가 내 왼자식인데 arr 자체 크기가 8이라고 생각해봐라.)
(arr[9]를 참조하면 안 되지 않는가?)
값을 찾지 않도록 설정한다. (null을 싫어하는 C...)