Facts
-
패스트캠퍼스 자료구조 이론 강의를 모두 수강했습니다.
- 힙을 학습했습니다.
- 린ux 5,6장을 읽었습니다.
- 클린 아키텍처 읽기를 시작했습니다.
Feelings
- 백패킹 관련해서 인터넷이나 핸드폰을 자꾸 찾아보게 됩니다. 자꾸 정신 못차리고 빠져서 걱정입니다.
- 많이 집중하지 못 한 하루 같아 아쉽습니다.
- TIL을 매일 작성하기로 마음 먹었는데 쉽지 않습니다.ㅠㅠ
Findings
-
저번에 읽은 글이 유저 스토리에 대한 글이고 유스 케이스와 유저 스토리는 다른 것임을 알게 되었습니다.
- 안드로이드 애플리케이션을 만들면서 클린 아키텍처를 적용하고자 하는데 이해가 많이 부족한 것 같습니다.
-
힙 : 데이터 구조에서 최대/ 최소 값을 빠르게 찾기 위해 고안된 완전 이진트리
- 완전 이진트리 : 노드를 삽입할 때 왼쪽 노드부터 차례대로 삽입하는 트리
- 힙을 사용하는 이유 : 힙에 데이터를 넣고 최대 /최소 값을 찾으면 O(logn)의 시간 복잡도를 갖는다. -> 배열로 할 경우 O(n)의 시간 복잡도
- 힙의 종류
- 최대 힙 : 상위 노드(부모 노드)의 값이 항상 자식 노드의 값보다 크거나 같은 힘 -> 최대값을 구하기 위한 자료구조
- 최소 힙 : 상위 노드(부모 노드)의 값이 항상 자식 노드의 값보다 작거나 같은 힙 -> 최소값을 구하기 위한 자료구조
- 힙의 조건
- 완전 이진 트리 형태이다.
- 최소 힙 또는 최대 힙이다.
- 이진 탐색 트리와 힙의 비교 : 둘 다 모두 이진 트리 형태라는 공통점이 있지만 각 자료 구조의 목적과 조건이 다르기 때문에 차이점이 존재한다.
-
목적의 차이
- 이진 탐색 트리 : 탐색을 위한 자료구조
- 힙 : 최대 /최소 값 검색을 위한 자료구조
-
조건의 차이
- 이진 탐색 트리 : 부모 노드의 값보다 크면 오른쪽 자식, 작으면 왼쪽 자식으로 위치가 고정된다.
- 힘 : 무조건 부모 노드의 값이 자식 노드의 값보다 크면(또는 작은면)되기 때문에 자식의 위치는 어느쪽이든 상관없다.
- 힙의 동작
-
데이터 삽입
- 완전 이진 트리 형태에 맞게 데이터를 삽입한다.
- 삽입한 데이터의 값과 부모 노드의 값을 비교해서 위치를 바꾼다. -> 부모 노드의 값보다 작을 때까지 반복한다.
-
데이터 삭제 : 힙의 데이터 삭제(pop)은 root node를 삭제하기 때문에 새로운 root를 만들어줘야 한다.
- Root node의 값을 꺼낸다.(최대/ 최소 값을 꺼낸다.)
- 새로운 root node를 만들기 위해서 제일 마지막에 넣었던 데이터를 root node로 올린다.
- Root node와 자식 노드들 간에 값을 비교한다.
- 자식 노드가 클 경우 root node와 위치를 바꾼다.
-> 3-4번의 과정을 자식 노드가 없거나 작은 자식만 남아 있을 때까지 반복한다.
Future Action Plans
- 먼저 안드로이드 프로젝트를 만들어 놓고 리팩터링 하는 방향으로 안드로이드 공부를 진행해야겠습니다.
- 이번 주에는 공부했던 자료구조들을 정리해서 블로그에 글을 써야겠습니다.
- 사용자 스토리와 유스케이스에 대한 글을 꾸역꾸역 읽어야겠습니다.
- 제주도 가기 전까지 열공모드 가즈아!!