오늘의 배움 #93

2021.12.12 오늘의 배움

오늘 한 일.

• 자료구조 구현해보기. 이진트리, 이진탐색트리, 힙을 구현했다. 블로그에는 링크드 리스트까지만 정리
• 백준 한 문제를 풀었다.

오늘 새로 발견한 것.

• 역시 removeFirst는 믿으면 안된다. 우선순위 큐를 직접 구현해서 풀었을 때는 통과가 되는데, 소팅을 한번 하고 removeFirst를 반복했더니 시간초과가 난다.

• BST에서 삭제는 삭제할 노드의 자식 노드가 몇개인지에 따라 다르다. 리프 노드일 때는 그냥 없애고, 자식이 1개일 때는 자신의 부모와 자식을 연결시키고, 자식이 2개일 때는 successor로 불리는 오른쪽 서브트리의 최소값을 가진 노드(가장 왼쪽 리프노드)의 데이터를 삭제할 노드의 데이터로 덮어씌운 뒤에 successor를 삭제한다. 근데 이때 successor에 오른쪽 자식 노드가 딸려있으면 삭제하기전에 부모노드랑 자식노드랑 연결 시켜주어야 한다. 

오늘 느낀 것.

• 자료구조는 꽤 재밌다..
• 어제 몸이 너무 안좋아서 걱정했는데, 그냥 포항 내려오면서 부산도 들리고 너무 긴 여행을 해서 그런 것 같다. 잘 쉬니까 좀 괜찮은 듯

앞으로의 계획.

• 다음 주에 정리할 것: DS 나머지, OSTEP 남은 부분, ARC, Method Dispatch
• 해야하는 것: 이력서 보완하기, 자소서 작성하기 (화요일까지 무조건 끝내기)

오늘의 감사.

• 오래전에 배운 내용들을 다시 리마인드하면서 새롭게 배워가는 것들이 있게 해주심에 감사합니다.