justgo_developer

위상정렬: 그래프를 정렬하는 것/ 정렬기준은 진입 차수의 비 내림차순 순서즉, 진입차수가 0개->N개 순으로 탐색하고정렬하면서 진입차수가 0인 노드들은 제거하고, 진입차수가 0이 아닌 노드들은 0으로 수정한 뒤 제거해가며 정렬진입차수란? 해당 노드로 들어오는 간선의 개수 위상정렬은 DAG그래프여야 한다.DAG란 Directed Acyclic Graph 방향성이 있고 사이클이 없는 그래프위상정렬은 DFS 방법과 진입차수(Indegree)를 이용한 방법이 있다.

힙 정렬(Heap Sort): 힙 자료구조를 이용한 정렬 방법: 힙에서 항상 가장 큰 원소가 루트노드가 되고 삭제 연산을 수행하면 항상 루트노드의 원소를 삭제하여 반환 힙 정렬 수행 방법1. 정렬한 원소들을 입력하여 최대 힙 구성2. 힙에 대하여 삭제 연산을 수행하여 얻은 원소를 마지막 자리에 배치3. 나머지 원소에 대해서 다시 최대 힙으로 재구성 (원소의 개수만큼 반복 수행) 정렬되지 않은 [69,10,30,2,16,8,31,22]의 자료들을 힙정렬-> 정렬할 원소가 8개 이므로 노드가 8개인 완전 이진 트리를 만들고 최대 힙으로 구성1. 힙에 삭제 연산을 수행하여 루트 노드의 원소 69를 구해서 배열의 마지막 자리에 저장한다. 그리고 나머지 원소들에 대해서 최대 힙으로 재구성 평균 시간복잡도 : O(..

배열의 경우, 인덱스나 주소값을 통해서 한번에 해당값에 접근할수있다.대신에 길이가 가변적이지 못하다. 링크드리스트의 경우, 길이가 고정되지 않는 대신 원하는 값을 찾기 위해 각 노드를 일일이 순회해야 한다. 최악의 경우 O(n) 해시 테이블(hash table): 키 값의 연산에 의해 직접 접근이 가능한 구조: 데이터의 해시 값을 테이블 내의 주소로 이용하는 궁금의 탐색 알고리즘-> 탐색 성능이 향상됐지만 공간은 희생함 해싱(hashing): 해시테이블을 이용한 탐색: 자료를 검색할 때, 탐색이나 첨자가 아닌 내용에 의해 필요한 자료에 도달하는 기법 자료를 찾아주는 함수를 해싱함수라고 한다.서로 다른 자료가 해싱 함수에 의해 같은 값을 생성하는 경우 충돌(Collision)이라고 한다.탐색시간이 O(1)..