반응형 컴퓨터공학 기초/자료구조3 [자료구조] 해쉬(Hash)란? 해쉬(Hash) 란? - 데이터를 다루는 기법중에 하나로 검색과 저장이 아주 빠르다. - 데이터를 검색할 때 사용할 key와 실제 데이터의 값이 (value가) 한 쌍으로 존재 - key값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1)이 된다. 해시 함수 - 임의의 길이의 데이터를 입력받아 일정한 길이의 비트열로 반환 시켜주는 함수 - 결과로는 해쉬코드가 나온다. - 동일한 값이 입력되면 언제나 동일한 출력값을 보장한다. 좋은 해쉬함수 - 충돌을 최소하하는 방향으로 설계 - 키의 일부분보다는 전체를 참조하여 키 생성 충돌이란 ? - 해시함수를 통해서 결정된 key가 중복되는경우 충돌해결 Open Address 방식 - 충돌이 발생하면 다른 해시버킷에 데이터를 삽입하는 방.. 2020. 2. 15. [자료구조] 힙(Heap)이란 ? 힙(Heap)이란 ? 완전이진트리의 일종 완전이진트리와는 다르게 중복값을 허용한다. 최댓값이나 최솟값을 빠르게 찾아내기 위해 만들어진 자료구조 힙(Heap)의 종류 최대힙 : 루트의 값이 가장 큰 힙 최소힙 : 루트의 값이 가장 작은 힙 힙(Heap)의 사용사례 우선순위 큐 힙(Heap)의 구현 구현에는 보통 배열을 이용한다. 일반적으로 편하게 사용하기 위해서 0번째 인덱스는 비워둔다. 왼쪽자식의 인덱스 : 부모의 인덱스*2 오른쪽자식의 인덱스 : (부모의 인덱스*2) +1 부모의 인덱스 : 자식의 인덱스/2 public class MaxHeap { public static void main(String[] args) throws IOException{ BufferedReader reader = new .. 2020. 2. 11. [자료구조] 배열 vs List 비교하기 배열(Array) 이란 ? 여러 데이터를 하나의 이름으로 그룹핑해서 관리 하기 위한 자료구조 배열의 인덱스는 유일무이한 값 식별자 배열의 특징 크기가 정해져있다. 데이터를 메모리에 순차적으로 나열가능 인덱스를 활용하여 검색에 최적화 되어있다. 저장될 때 인접한 Memory 또는 Memory에 연이어 저장된다. Stack 영역에 메모리 할당 배열의 단점 크기를 수정할 수 없다. 배열은 인덱스에 따라 값이 유지되기때문에 엘레먼트가 삭제되어도 메모리는 차지한다. 삽입, 삭제시 비용이 많이 들 수 있다. List란 ? 빈틈없는 데이터의 적재라는 장점을 취한 데이터 스트럭쳐 List의 특징 데이터간의 순서가 존재한다. 인덱스는 몇번째 데이터인가 정도의 의미이다. 빈 엘레먼트를 허용하지 않는다. 크기가 정해져있지 .. 2020. 2. 10. 이전 1 다음
