[TIL]2024-05-11
오늘은
5월 13일, 16일, 17일에 하는 교육에 대해서 공부를 해보았다.
배열, 연결리스트, 큐, 우선순위 큐, 스택, 맵
dx-dy 테크닉, 누적합, 투 포인터, dp
[자료구조]
배열, 연결리스트, 큐, 스택은 객체지향설계 C++로도 해봤고, 자료구조 수업으로도 들었으니 설명은 나중에 더 자세히 정리하도록 하고, 일단 이전에 들었던 자료들을 토대로 공부를 완료.
우선순위 큐와 맵은 정리하자.
우선 순위 큐는 트리 구조를 이용하는데, 가장 높은 우선순위를 가진 항목에 대해서 접근 및 삭제가 이루어진다.
삽입 시 우선 순위에 따라 위치가 정해진다. (기준에 따라 정렬이 된다는 말씀.)
단순하게, 숫자를 기준으로 두어 우선순위를 설정한다고 하자. Min, Max Heap 에 따라 저장이 어떻게 이루어지는지 정해질 것이다.
(우선 순위 큐는 자료의 연상은 완전 이진 트리로 하고, 실질적인 구현은 배열로 한다.)
이렇게 완성이 되는데 위의 11개의 원소들을 어떤 순서대로 넣든 동일한 저장 결과가 나오는 것이 우선 순위 큐이며, 삽입된 뒤로는 삭제 및 접근은 제일 첫 원소인 1번 인덱스에서 이루어지게 된다.
또한 배열의 인덱스로 배열 A에 대해서, A[i]의 자식은 A[2i] , A[2i+1]의 형태를 갖게 되며 한 원소의 부모는 인덱스 나누기 2 한 정수 값이다.
삭제 및 삽입에서는 항상 완전 이진트리로 Heap이 되어야 하는데, (여기서는 Min heap)
삭제 시에는 Down heap이라는 과정으로 루트 노드가 사라졌을 시 다시 Heap을 구성시키기 위해서 하는 과정으로 자료구조를 최신화 하는 것이다. (위의 우선순위 큐의 특성을 다시 살리기 위해서 배열에서 삭제로 인한 공백 자리를 채우는 과정.)
즉, 제일 첫 원소인 10이 사라지면 원소들이 한 칸 씩 옮겨가야 하는데 단순하게 앞으로 옮기면 Heap이 깨지니까 Heap이 깨지지 않도록 배열을 다시 정리하는 것이다.
삽입 시에는 제일 마지막 원소에 삽입을 하고, Heap의 구조 및 우선 순위를 맞춰주기 위해 원소들을 비교하는 과정으로 삽입이 이루어지게 된다. (여기서는 간단하게 설명하자.)
맵?
맵 뭐냐 그냥 키랑 밸류 값이 있고, 키를 통해서 밸류 값 접근하는 거 아닌가? 암튼 쉬움
해시 테이블 및 해시 맵에 대해서 더 설명을 하면 되려나?
해시 함수에 키 값이 입력으로 주어지면 출력으로 저장할 위치의 주소가 나오는 구조이다. 이런 식으로 자료구조가 해시 함수를 통해 데이터가 저장되는 구조를 해시 맵, 테이블이라고 한다. 해시 맵과 해시 테이블의 차이에 대해서 궁금할 건데, 다음에 알아보도록 하자.
[알고리즘]
dx-dy