자료구조란
프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러 구현방법들
효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨
자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있음
여러 자료 구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 하므로 자료구조에 대한 이해가 중요
이진 트리 : 부모노드에 자식 노드가 두 개 이하인 트리
힙 : 우선순위 큐를 구현
보모노드가 자식보다 항상 크거나 작은 트리
힙정렬에 활용가능
왼쪽부터 채워진 이진트리를 완전 이진트리 층이 전부 다 차면 풀 완전 이진트리?
이진 검색 트리는
중복을 허용하지 않으며 왼쪽에는 자신보다 작은 수들만 오른쪽 자식에는 큰 수들만
TreeSet TreeMap은 이진 검색트리인 레드블랙트리
그래프
정점과 간선들의 유한 집합 G = (V, E)
정점 (vertex) : 여러 특성을 가지는 객체, 노드
간선 (edge) : 이 객체들을 연결 관계를 나타냄, 링크 (link)
간선은 방향성이 있는 경우와 없는 경우가 있음
그래프를 구현하는 방법 : 인접 행렬(adjacency matrix), 인접 리스트 (adjacency list)
그래프를 탐색하는 방법 : BFS, DFS
해싱
자료를 검색하기 위한 자료 구조
검색을 위한 자료구조
키(key)에 대한 자료를 검색하기 위한 사전개념의 자료 구조
key는 유일하고 이에 대한 value를 쌍으로 저장
index = h(key) : 해시 함수가 key에 대한 인덱스를 반환해줌 해당 인덱스 위치에 자료를 저장하거나 검색하게 됨
해시 함수에 의해 인덱스 연산이 산술적으로 가능 O(1)
저장되는 메모리 구조를 해시테이블이라 함
jdk 클래스 HashMap , Properties
해시테이블 75퍼정도 차면 재구성
제네릭 (Java 1.5)
제네릭 자료형 정의
클래스에서 사용하는 변수의 자료형이 여러개 일 수 있고, 그 기능(메서드)은 동일한 경우 클래스의 자료형을 특정하지 않고 추후 해당 클래스를 사용할 때 지정할 수 있도록 선언
. 실제 사용되는 자료형의 변환은 컴파일러에 의해 검증되므로 안정적인 프로그래밍 방식
. 컬렉션 프레임워크에서 많이 사용되고 있음
. 제네릭 타입을 사용하지 않는 예
예전에는 Object로 받아서 범용적으로 사용하였지만
사용범위가 Object로 한정적이고 다운캐스팅을 할 경우 instance 체크를 많이 해야했따.
public class GenericPrinter<T> {
private T material
public void setMaterial(T material) {
this.material = material;
}
public T getMaterial() {
return material;
}
public String toString() {
return material.toSTring();
}
}
자료형 매개변수 T (Type parameter) : 이 클래스를 사용하는 시점에 실제 사용할 자료형을 지정, static 변수는 사용할 수 없음
GenericPrinter : 제네릭 자료형
E : element, K : key, V : value 등 의미에 따라 사용가능 기능은 같아
사용하는 부분에서는
Powder powder = new Powder();
GenericPrinter<Powder> powderPrinter = new GenericPrinter<>(); 뒤에 <>는 컴파일러가 채워줘
<T>에 자료형 넣어서 사용
Object와의 차이는 형변환을 하지 않아도 된다.
다이아몬드 연산자 <>
Java 에서 <>를 다이아몬드 연산자라 한다.
ArrayList list = new ArrayList<>(); 다이아몬드 연산자 내부에서 자료형은 생략가능 하다
(ArrayList 뒤에는 다이아몬드 연산자 왜 안 붙지..) 오브젝트로 지정된다네
제네릭에서 자료형 추론 (자바 10부터)
ArrayList list = new ArrayList() => var list = new ArrayList(); (지역변수 타입추론)
<T extends 클래스> 사용하기
상위 클래스의 필요성
T 자료형의 범위를 제한 할 수 있음
상위 클래스에서 선언하거나 정의하는 메서드를 활용할 수 있음
상속을 받지 않는 경우 T는 Object로 변환되어 Object 클래스가 기본으로 제공하는 메서드만 사용가능
T extends 를 사용한 프로그래밍
GenericPrinter 에 material 변수의 자료형을 상속받아 구현
T에 무작위 클래스가 들어갈 수 없게 Marerial 클래스를 상속받은 클래스로 한정
public class GenericPrinter<T extends Super> {
private T material
public void setMaterial(T material) {
this.material = material;
}
public T getMaterial() {
return material;
}
public String toString() {
return material.toSTring();
}
}
제네릭 메서드
자료형 매개변수를 메서드의 매개변수나 반환 값으로 가지는 메서드는
자료형 매개 변수가 하나 이상인 경우도 있음
제네릭 클래스가 아니어도 내부에 제네릭 메서드는 구현하여 사용할 수 있다.
public <자료형 매개변수> 반환형 메서드 이름 (자료형 매개변수..) {}
제네릭 메서드의 활용 예
두 점(top, bottom)을 기준으로 사각형을 만들 때 사각형의 너비를 구하는 메서드를 만들어보자
JCF
컬렉션 프레임워크
프로그램 구현에 필요한 자료구조를 구현해 놓은 JDK 라이브러리
java.util 패키지에 구현되어 있음
개발에 소요되는 시간을 절약하면서 최적화 된 알고리즘을 사용할 수 있음
여러 구현 클래스와 인터페이스의 활용에 대한 이해가 필요함
Collection 클래스를 상속 받는 List, Set
List를 상속 받는 ArrayList, Vector, LinkedList
Set을 상속 받는 HashSet, TreeSet
Map클래스를 상속 받는 Hashtable, HashMap, TreeMap
Hashtable클래스를 상속 받는 Properties
List는 순서가 정해져있다. 첫번쨰 두번째
Set 집합 , 중복을 허용하지 않으며 중복을 허용하지 않는다.
Iterator
요소의 순회
컬렉션 프레임 워크에 저장된 요소들을 하나씩 차례로 참조하는 것
순서가 있는 List 인터페이스의 경우 Iterator 없이 get(i)로 접근 가능
Set 인터페이스의 경우 get(i) 메서드가 제공되지 않아 iterator를 활용하여 객체를 순회한다.
boolean hasNext() : 이후에 요소가 더 있는지를 체크하는 메서드, 요소가 있다면 true를 반환
E next() : 다음에 있는 요소를 반환
HashSet 클래스
Set 인터페이스를 구현한 클래스와
멤버의 중복 여부를 체크하기 위해 인스턴스의 동일성을 확인해야 함
동일성 구현을 위해 필요에 따라 equals()와 hashCode()메서드를 재정의함
TreeSet 클래스 활용
객체의 정렬에 사용하는 클래스
Set 인터페이스를 구현하여 중복을 허용하지 않고, 오름차순이나 내림차순으로 객체를 정렬할 수 있음
내부적으로 이진검색 트리로 구현됨
이진검색트리에 저장하기 위해 각 객체를 비교해야함
비교 대상이 되는 객체에 Comparable이나 Comparator 인터페이스를 구현 해야 TreeSet에 추가 될 수 있음
String, Interger 등 많은 클래스들이 이미 COmparable을 구현했음
Comparable java.lang
Comparator의 활용 : 이미 Comparable이 구현된 경우 Comparator로 비교하는 방식을 다시 구현할 수 있음 java.util
쌍으로 자료를 관리하는 Map 인터페이스를 구현한 클래스와 그 활용
HashMap 클래스 활용하기
Map 인터페이스를 구현한 클래스와
가장 많이 사용되는 Map 인터페이스 기반 클래스
key - value를 쌍으로 관리하는 메서드를 구현함
검색을 위한 자료구조
key를 이용하여 값을 저장하고 key를 이용하여 값을 꺼내오는 방식 - hash 알고리즘으로 구현됨
key가 되는 객체는 중복될 수 없고 객체의 유일성을 비교를 위한 equals()와 hashCode() 메서드를 구현해야 함
댓글