공학/자료구조&알고리즘9 해시테이블 해시테이블데이터의 해시 값을 테이블 내의 주소로 이용하는 알고리즘 !!기본 개념!!데이터를 담을 테이블을 미리 크게 확보한 후입력받은 데이터를 해시하여 테이블 내의 주소를 계산하고이 주소에 데이터를 담는 것 해시 함수입력 값에서 테이블 내의 주소를 계산해 내는 함수- 나눗셈법 주소 = 입력 값 % 테이블 크기- 자릿수 접기 각 자릿수를 더하기 하지만 충돌 발생!!!충돌이 뭐냐고? 충돌해시 함수가 서로 다른 입력 값에 대해 동일한 해시 테이블 주소를 반환하는 것 다른 입력인데 주소는 똑같으면 충돌@_@ 그럼 충돌의 해결 방법은? - 개방 해싱해시 테이블의 주소 바깥에 새로운 공간을 할당하여 문제를 수습- 폐쇄 해싱주어진 해시 테이블의 공간 안에서 문제를 해결 - 체이닝 (개방 해싱 종류) 각 데이터를 해당.. 2014. 12. 2. 우선순위 큐 & 힙 우선순위 큐?데이터의 입출력 때 최소한의 비용으로 최우선순위의 데이터를 Head에 위치시키는 알고리즘의 효율을 고민해보쟝!! - 일단 큐와 같지만 '우선순위' 속성을 갖는 데이터를 다룸!! 그 우선순위는 프로그래머 마음!- 연산도 큐 처럼 삽입/삭제 * 힙 Heap- 자유 저장소의 힙은 아니래!ㅋㅋ- 힙 순서 속성을 만족하는 완전 이진 트리! (모든 깊이의 노드들이 완전히 채워져 있는 이진 트리)- 힙 순서 속성 : 트리 내 모든 노드가 부모 노드보다 커야 함!- 힙에서 루트 노드는 가장 작은 데이터를 갖는 노드!!!!!- 연산 : 노드 삽입 / 최소값 삭제(루트 삭제) 항상 연산 후에는 힙 순서 속성을 유지하도록!!!! 힙의 구현은 배열을 이용해서!!!=> 각 노드의 위치나 부모/자식 관계 등을 배열의.. 2014. 11. 21. 탐색 탐색!데이터를 찾고자 한다!! * 순차 탐색- 처음부터 끝까지 차례대로 모든 요소 비교- 처음부터 끝으로 한 방향으로만 탐색하므로 선형 탐색- 장점 : 구현이 간단해 버그의 가능성이 적음 / 정렬되지 않은 데이터 중 원하는 데이터를 찾을 수 있는 방법 => 높은 성능이 필요없거나 데이터 집합의 크기가 작은 곳에서 사용 * 자기 구성 순차 탐색- 자주 사용되는 항목을 데이터 집합의 앞쪽에 배치해 순차 탐색의 검색 효율을 증가시키는 방법- 전진 이동법 : 한번 탐색되면 그 항목을 데이터 집합의 가장 앞(링크드 리스트의 Head)으로 위치- 전위법 : 탐색된 항목을 바로 이전 항목과 교환- 빈도 계수법 : 탐색된 횟수를 별도의 공간에 저장, 탐색된 횟수의 높은 순으로 집합을 재구성 * 이진 탐색- 탐색 범위를.. 2014. 11. 21. 정렬 알고리즘의 의미: 문제를 해결하기 위한 일련의 명령이나 반복되는 절차 정렬 알고리즘찾고자 하는 데이터를 빠르고 쉽게 찾을 수 있게 하는 것이 목적 * 버블 정렬- 데이터 집합 내의 이웃 요소들끼리의 교환을 통해 정렬 수행이웃 요소들끼리 비교 비교 비교.... 마지막 까지 가서 마지막 요소는 제외하고 다시 반복!!!- 버블 정렬의 비교 횟수 : n(n-1)/2 * 삽입 정렬- 데이터 집합을 돌면서 정렬이 필요한 요소를 뽑아내 이를 적당한 곳에 삽입해 나감like 카드 정리 하기ㅋㅋ비교 범위를 늘려가면서 정렬이 필요한 아이를 적당한 위치로 이동시킴- 삽입 정렬의 비교 횟수 : n(n-1)/2- 데이터 집합이 정렬이 되어 있으면 비교를 하지 않음!! => 평균적으로 삽입 정렬이 더 나은 성능을 보임ㅋ + 메모.. 2014. 11. 21. 이전 1 2 3 다음