정리하고기록하자

그래프 ( Graph ) 그래프란 정점 ( Vertex ) 과 간선 ( Edge ) 으로 이루어진 자료구조 이다. 정확히는 정점 ( Vertex ) 간의 관계를 표현하는 조직도라고 볼 수 있다. 이러한 면에서 트리는 그래프의 일종인 셈이다. 그래프와 트리의 차이점 그래프와 관련된 용어 정점 ( Vertex ) : 노드 ( Node ) 라고도 하며 정점에는 데이터가 저장된다. 간선 ( Edge ) : 정점 ( 노드 ) 를 연결하는 선으로 link, brach 라고도 부른다. 인접 정점 ( adjacent Vertex ) : 간선에 의해 직접 연결된 정점 ( 0과 2는 인접정점 ) 단순 경로 ( simple path ) : 경로 중에서 반복되는 정점이 없는 경우, 한붓그리기와 같이 같은 간선을 지나가지 않는..

HashTable 과 HashMap 자바에서 제공하는 HashMap과 HashTable 은 Map 인터페이스를 상속받아 구현되고 Key, Value 로 관리하는 자료 구조이다. 특징은 Key가 데이터를 추출할 때 구분자로 활용하는 방식을 취하는데 이는 리스트 인터페이스와 같은 자료구조보다 탐색에 있어 더 높은 효율을 기대 할 수 있다. HashTable 과 HashMap 의 차이점 1. 동기화 HashMap의 경우 동기화를 지원하지 않는다.반면 *멀티 스레드 환경에서 HashTable은 동기화를 지원하지 않기 때문에 실행 환경에 따라 구분하여 사용하면 된다. 속도 면에서 HashTable은 동기화 처리라는 비용 때문에 HashMap에 비해 더 느리다. * 동기화 : 시스템을 동시에 작동시키기 위해 여러 ..

HashMap 1. HashMap 은 Map 인터페이스에 속해 있는 컬렉션이다. 2. Map 인터페이스의 기본 기능등을 전부 구현할 수 있다. 3. 데이터들은 모두 ( 키, 값 )의 1:1 구조로 되어 있는 Entry로 되어있다. 4. 같은 키의 값을 삽입하려고하면 해당 키의 값이 변경이 된다. 5. 키는 중복이 되지 않지만 값은 중복이 될 수 있다. 6. 다른 특징은 HashTable과 유사하지만 동기화가 되지 않고 Null값도 저장이 가능하다. HashMap 선언 import java.util.HashMap; public class main { public static void main(String[] args) { HashMap hashMap = new HashMap(); // 타입 설정 x , O..

해쉬 테이블 ( Hashtable ) 해쉬 테이블은 Key , Value 를 저장하는 데이터 구조이다. 해쉬 테이블은 *해쉬함수를 사용하여 키를 해쉬값으로 매핑하고, 이 해쉬값을 인덱스 또는 주소삼아 데이터를 key와 함께 저장하는 자료구조 이다. 단순하게 key - value 로 이루어진 자료구조라고 생각하면 된다 *해쉬 함수 ( Hash Function ) 해쉬와 해쉬테이블을 알기전에 Hash Function(해쉬함수) 라는 것을 알아야 한다. 데이터를 최대한 빠르게 찾기 위해서는 저장하는 위치도 잘 생각해서 저장해야 한다 해쉬 함수의 정의는 key를 고정된 길이 hash로 변경해주는 역할을 한다. 이 과정을 hasing 이라고 한다 key를 해쉬함수라는 함수에 input으로 넣어서 Output으로 ..

트리 (Tree) 트리란 *계층적인 구조를 표현하기 위한 일상적으로 사용하는 구조이다 ( *비선형 자료구조 ) * 계층적 구조는 일반적으로 조직도를 나타내는 경우이다. * 비선형이란 일직선으로 나타내지 못하는 방식이다. 트리 값 저장 1. 데이터와 연결 상태를 저장할 클래스 생성 ( 노드 ) 2. 각각의 노드들에 값 저장 3. 노드 간 연결 상태 정의 1. 데이터와 연결 상태를 저장할 클래스 생성 ( 노드 ) Node 라는 클래스를 만들고, 저장할 값 변수 ( value ) , 왼쪽 연결 노드 ( left ) , 오른쪽 연결 노드 ( right ) 에 대한 정보를 저장할 변수를 생성한다. 2. 각각의 노드들에 값 저장 3개의 Node를 생성하고, 우선 leftNode와 rightNode에 대한 정보를 n..

큐(Queue) 큐란 컴퓨터의 기본적인 자료구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO ( First In First Out ) 구조로 저장하는 형식이다. ex ) 줄서기와 같이 처음 선 사람이 처음 통과하는 것처럼, 가장 먼저 넣은 데이터를 가장 먼저 꺼낼수 있는 구조. 큐의 선언 import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String[] args){ Queue que = new LinkedList(); que.add("Hello"); que.add("World"); System.out.print(que); } } 주요 메소드 기능 Throws excep..

힙 ( Heap ) 힙이란 완전이진트리의 형태로 만들어진 자료구조 이다. *이진트리란 컴퓨터 응용에서 가장 많이 활용되는 트리구조이다. 힙의 종류 - 최대 힙 : ( 완전 이진 트리 ) + ( 부모 노드 > 자식 노드 ) 최대 힙은 완전 이진 트리이면서 부모 노드가 자식 노드보다 큰 트리를 말한다. - 최소 힙 : ( 완전 이진 트리 ) + ( 부모 노드 < 자식 노드 ) 최소 힙은 완전 이진 트리이면서 부모 노드가 자식 노드보다 작은 크리를 말한다. *보통 힙이라고 하면 일반적으로 최대 힙을 의미한다. 힙의 활용 힙은 최댓값 혹은 최솟값을 빠르게 찾아내기 유리한 자료구조이다. 1. 우선순위 큐를 구현할 때 쓰이기도 한다. 2. 허프만 코드를 구현할 때도 쓰이기도 한다. 3. 힙 정렬을 구현 할 때도 쓰..