알고리즘/Do it 알고리즘 (35) 썸네일형 리스트형 오픈 주소법 지난 글 : [알고리즘/Do it 알고리즘] - 체인법 오픈 주소법 어제 배운 체인법과는 다른 해시법인 오픈 주소법(open addressing)은 충돌이 발생했을 때 재해시(rehashing)를 수행해 비어 있는 버킷을 찾아내는 방법으로, 닫힌 해시법(closed hashing)이라고도 한다. 요소의 검색, 삽입, 삭제 과정을 알아보자. 요소 삽입 새로운 값(18)을 삽입하고자 할 때 충돌이 발생한 경우(해시값 5에 5가 들어있는 경우) 사용하는 방법이 재해시다. 재해시할 때 해시 메서드는 자유롭게 결정할 수 있다. 예로 키값에 1을 더한 값을 요솟수로 나눈 나머지가 있다. 하지만 재해시를 한 번 수행했는데도 또 다시 충돌이 발생한다면 한 번 더 재해시를 할 수 있다. 이렇게 오픈 주소법은 빈 버킷을 .. 체인법 지난 글 : [알고리즘/Do it 알고리즘] - 해시법 체인법 체인법(chaining)은 해시값이 같은 데이터를 사슬(chain) 모양의 연결 리스트로 연결하는 방법으로, 오픈 해시법(open hashing)이라고도 한다. 해시값이 같은 데이터 저장 체인법은 해시값이 같은 데이터를 사슬 모양의 연결 리스트로 연결한다. 배열(해시 테이블)의 각 버킷에 저장하는 값은 그 인덱스를 해시값으로 하는 연결 리스트의 첫 번째 노드에 대한 참조다. 버킷용 클래스 Node 개별 버킷을 나타낸 것이 클래스 Node다. 이 클래스에는 아래 3가지 필드가 있다. - key : 키값(자료형 K는 임의의 자료형) - data : 데이터(자료형 V는 임의의 자료형) - next : 체인에서 다음 노드에 대한 참조(자료형은 Nod.. 해시법 지난 글 : [알고리즘/Do it 알고리즘] - Object 클래스 정렬된 배열에 새로운 값 추가 아래 배열 a를 보자. 요소가 13개인 배열에서 앞쪽 10개 요소에 오름차순으로 정렬된 데이터가 저장되어 있다. a 561420293437516975--- =================================================================================================== b 56142029343537516975-- //35를 추가 이 배열에 35를 추가하는 과정은 아래와 같다. 1. 삽입할 위치가 a[5]와 a[6] 사이임을 이진 검색법으로 조사한다. 2. 배열 b와 같이 a[6] 이후의 모든 요소를 하나씩 뒤로 이동한다. 3. a[6]에 35를.. Object 클래스 지난 글 : [알고리즘/Do it 알고리즘] - 이진트리와 이진검색트리 Object 클래스 이해하기 java의 모든 클래스에서 최상위 클래스인 Object에 대해 몇 가지 중요한 점을 이해하자. java.lang 패키지 Object 클래스는 java.lang 패키지에 속한다. 그러므로 자바의 모든 프로그램에서 명시적으로 형 import를 하지 않아도 간단한 이름으로 나타낼 수 있다. native 메서드 선언 getClass 등 몇 개의 메서드에 native를 붙여 선언하고 있다. 이렇게 선언하는 메서드는 윈도우, macOS, 리눅스 등의 플랫폼에 의존하는 부분을 구현하기 위한 특별한 메서드다. 일반적으로 자바 이외의 언어로 작성한다고 한다. hashCode 메서드와 해시값 모든 클래스형의 인스턴스는 해시.. 이진트리와 이진검색트리 지난 글 : [알고리즘/Do it 알고리즘] - 트리 이진트리란? 각 노드가 왼쪽 자식과 오른쪽 자식 둘을 갖는 트리를 이진트리(binary tree)라 한다. 이때 두 자식 가운데 한 쪽이 없거나 둘 다 없는 노드가 포함되어도 된다. 이진트리의 특징은 왼쪽 자식과 오른쪽 자식을 구분한다는 점이다. 완전이진트리란? 루트에서 아래쪽 레벨로 내려가는 노드가 빠짐없이 채워져 있고, 또 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 빠짐없이 채워져 있는 이진트리를 완전이진트리(complete binary tree)라 한다. 1. 마지막 레벨을 제외한 레벨은 노드를 빠짐없이 가득 채운다. 2. 마지막 레벨은 왼쪽부터 오른쪽 방향으로 노드를 빠짐없이 채우되, 반드시 끝가지 채울 필요는 없다. 높이가 k인 완전이진트리가.. 트리 지난 글 : [알고리즘/Do it 알고리즘] - 원형 이중 연결 리스트 만들기 지난 4일간 살펴본 리스트는 순서대로 데이터를 나열하는 자료구조다. 이제 배울 자료구조는 데이터 사이의 계층 관계를 나타내는 트리다. 트리 알아보기 트리(tree)와 트리 관련 용어를 알아보자. 트리를 구성하는 요소는 노드(node)와 가지(edge)이다. 각각의 노드는 가지로 연결되어 있다. 루트 트리의 가장 윗부분에 위치하는 노드를 루트(root)라 한다. 하나의 트리에는 하나의 루트만 있다. 리프 트리의 가장 아랫부분에 위치하는 노드를 리프(leaf)라 한다. 이때 '가장 아래에 위치한다'는 말은 물리적으로 가장 아랫부분에 위치한다는 것이 아닌 노드가 더 이상 뻗어 나가지 않는 마지막에 위치한다는 의미다. (리프를 끝 노.. 원형 이중 연결 리스트 만들기 지난 글 : [알고리즘/Do it 알고리즘] - 배열 커서로 연결 리스트 만들기 원형 리스트 살펴보기 head ↓ A → B → C → D → E → F ↑ ↓ ↑←←←←←←←←←←←←←←←←←←←← 위 그림처럼 꼬리 노드가 머리 노드를 가리키는 연결 리스트를 원형 리스트(circular list)라 한다. 원형 리스트는 고리 모양으로 나열된 데이터를 저장할 때 알맞은 자료구조다. 보통의 연결 리스트와 다른 점은 꼬리 노드의 다음 노드를 가리키는 포인터가 null이 아니라 머리 노드의 포인터라는 점이다. 개별 노드의 자료형은 보통의 연결 리스트와 같다. 이중 연결 리스트 살펴보기 연결 리스트의 가장 큰 단점은 다음 노드는 찾기 쉽지만 앞쪽 노드는 찾기 어렵다는 것이다. 이런 단점을 개선한 자료구조가 이중.. 배열 커서로 연결 리스트 만들기 지난 글 : [알고리즘/Do it 알고리즘] - 포인터로 연결 리스트 만들기 배열 커서로 연결 리스트 만들기 이전 글에서 배운 포인터를 이용한 연결 리스트는 '노드의 삽입, 삭제를 데이터 이동 없이 수행한다'는 장점이 있지만 삽입, 삭제를 수행할 때마다 노드용 객체를 위한 메모리 영역을 확보하고 해제하는 과정이 필요하다. 메모리 영역을 확보하고 해제하는 데 드는 비용은 절대 무시할 수 없다. 프로그램 실행 중 수가 크게 바뀌지 않는 경우, 또는 데이터 수의 최댓값을 미리 알 수 있는 경우 배열을 사용해 연결 리스트를 만들면 효율적으로 운용할 수 있다. 여기서 다음 노드를 가리키는 뒤쪽 포인터는 다음 노드에 대한 포인터가 아니라 당므 노드가 들어 있는 배열 요소의 인덱스다. 이 인덱스 포인터를 커서(cur.. 이전 1 2 3 4 5 다음
