250504 7일차

힙정렬 어제 잠깐 복기했던내용을 바탕으로 그냥 떠오르는데로 구현해봤음
1시간 정도안에 비재귀로 만들었다.
하지만 n^2 으로나와버렸는데
아무래도 자식대상으로 부모를 검사하는데다가 하나라도 검출되면 
다시처음부터 해서 그런것 같았다
지금생각해보니 최대힙을 만들고 끝으로 보내고 최대힙 구성을 n, n-1, n-2,...... 1 번을 반복한느낌?
그리고 스택메모리를 만들어서 썼는데
부모로만 해서 스택 안쓰고 해보려고 Try


점심을 먹고 스타트
계속 트라이해봐도 최대힙을 만들기가 생각보다 어려웠다
최상단에서 (idx 0) 쭉 돌면서 자식과 교환 
최하단에서 (idx max) 쭉 돌면서 부모와 교환
단순히 최대힙 구성이 O(n) 나온다길래 이렇게만 생각을 해봤다

하지만 된것 같아도 중간에 끊기는 경우가 많았음
완성해도 nLogn이 나와버림 으아ㅏㅏㅏㅏㅣㅣㅣㅣㅣㅣ
여기서 nlogn이 나오면 안된다고!!!!

그래서 다시 이론을 찾아봤음 (코드는 악에 받쳐서 절대 안보게 되버렸다)
1. 자식이 존재하는 마지막 부모부터 시작 
(존재하지 않는경우엔 자식이 없기에 해당 요소만 봤을땐 최대힙이기 때문)
<여기서부터가 Heapify로 분리했다> (도저히 하나의 함수로 하기엔 자꾸 헷갈려서 완전히 분리했음)
2. 자식중 큰걸 선택
3. 자식과 비교 후 자식이 크면 교환
4. 교환 했다면 자식 위치에서 반복

Heapify에다가 1번을 포함시키니 최대 힙완성.
Heap정렬은 너무쉬웠다
맨끝과 루트노드(최대값) 바꾸고 
길이줄인 맨끝을 Heapify반복하니 끝났다..


전체정렬 100만번 비교 

속도    느림   힙 < 병합 < 퀵   빠름
연산    많음   힙 < 퀵 < 병합   적음

여기서 재밌는점은 
여러번 실행해보니까 퀵, 힙은 C값이 변동이 없는데
병합은 C값이 계속 바뀌었는데
좀 더 분석해보니까 정렬이 되어있는 경우엔 연산이 더 줄어든다 
합치는 과정에서 한쪽 노드를 전부 소진하고 나면 비교하지 않고 나머지 노드를 소진하기 때문이다


저녁먹은후
병합정렬을 다시 해보았다
전부지우고 코드안보고 다시 그 흐름떠올리면서

핵심 : Slice / mid 값
재귀 없이 완료!!

그 뒤에 자료구조
7챕터 문자열검색
브루트 포스 / kmp / 보이어-무어
간단히 어떻게 하는건지 학습
나중에 핵심 내용 뽑아서 어떻게 구현해볼지 구상해보고 해보자

8챕터 리스트
너무많이 구현해봐서 대충 훑고 넘어간 내용이지만
재밌는 포인트가있었다
바로 커서를 이용한 리스트였는데
커서값을 이용해 인덱스를 통한 순차접근이었다
재밌는점은 배열이라서 삽입삭제시 단편화가 일어나는점인데
이걸 지워진 커서 dIndex 를 구성해서 하면 지워진 목록을 우선적으로 처리할수 있는점이었다.
그래도 리스트기에 접근이 느리긴 하지만 
뭔가 다른 구조랑 합치면 재밌는게 나올것 같은 느낌


이번주는 이렇게 마무리가 되었다
자료구조 책은 2권이지만 1권도 거의 마무리가 되가는상태
총읽어야하는 5권중 1.8권 정도 1주차에 마무리되었다.

앞으로 읽고 다시 복기하고 할게많지만
2주차에는 코딩실력 증진을위해 자료구조 핵심임 트리 그래프쪽을 파면서
코테 연습을 하면서 실습위주로 가야겠다 (자료구조 2권 다 읽긴해야함)

3주차부터 다시 컴퓨터구조운영체제 복기하면서, 코테심화버전 이때부터 슬슬 포폴준비를하고
4주차부터는 네트워크책을 같이보면서 주로 포트폴리오를 제작하고 운영체제 책을 완전 훑고 지나가보자.