정렬 리스트를 오름차순, 내림차순 혹은 어떤 조건에 대해 순서대로 배열한 것 정렬에 필요성 빠른 탐색을 위해 사용 리스트의 엔트리를 비교하는 방법으로 사용 정렬 방법 내부 방법 - 정렬할 리스트가 작아서 전체적인 정렬이 메인 메모리 상에서 실행될 수 있을 때 사용 외부 방법 - 큰 리스트에 사용 삽입 정렬 template void Insert(const T &e, T *a, int i) { // e를 정렬된 리스트 a[1:i]에 삽입 // 리스트 a[1:i+1]도 정렬되게 함 // 배열 a는 적어도 i+2 원소를 포함할 공간 필요 a[0] = e; while (e < a[i]) { // 리스트의 맨 뒤부터 e가 삽입될 위치인지 탐색하며, a[i + 1] = a[i]; // 배열 a의 원소를 한칸씩 위로 ..

Generics 제네릭의 사용 이유 컴파일 시간 단축 캐스트의 제거 Generics class, interface // raw type Box class public class Box { private Object object; public void set(Object object) { this.object = object; } public Object get() { return object; } } // generic type Box class public class Box { private T t; public void set(T t) { this.t = t; } public T get() { return t; } } 클래스 또는 인터페이스의 이름 뒤에 를 통해 타입 매개변수를 지정할 수 있음 타입 ..

Interface Queue Queue는 인터페이스 Collection 상속 메소드 기능 boolean add(E e) e를 큐에 삽입, 성공시 true 반환 용량을 초과한 경우 IllegalStateException 발생 E element() 큐의 head 반환 큐가 비어있으면 예외 발생 boolean offer(E e) e를 큐에 삽입, 성공시 true 반환 용량을 초과한 경우 false 반환 E peek() 큐의 head 검색 큐가 비어있으면 null반환 E poll() 큐의 head 검색 및 삭제 큐가 비어있으면 null 반환 E remove() 큐의 head 삭제 큐가 비어있으면 예외 발생 Queue는 선입선출 방식으로 원소를 저장 head에서는 remove, poll로 인해 삭제가 일어남 re..

Set HashSet HashSet은 인터페이스 Set의 구현 클래스 Enhanced for문 사용 가능 랜덤 위치에 원소가 저장되므로 입력한 순서에 상관없이 원소가 출력됨 Set는 원소 중복 허용 x Set 원소 중복 import java.util.*; class Point { int x, y; public Point(int x, int y) { this.x = x; this.y = y; } @Override public String toString() { return "Point(" + x + "," + y + ")"; } // @Override // public boolean equals(Object obj) { // Point p = (Point) obj; // if (x == p.x && y =..

List Enhanced for문 사용 // list가 초기화 되어있다고 가정 for(String str: list) { System.out.println(str); } // 위쪽 코드와 같은 기능 for(Iterator i = list.Iterator; i.hasNext(); ) { System.out.println(str); } Interface Iterable 메소드 기능 Iterator iterator() 타입의 반복자 리턴 public interface ListIterator extends Iterator 메소드 기능 void add(E e) 리스트에 원소를 더함 boolean hasNext() 리스트 반복자가 가리킬 다음 원소가 있으면 true boolean hasPrevious() 리스트 ..

패키지 서로 관련된 클래스와 인터페이스의 컴파일 된 클래스 파일들을 하나의 디렉터리에 묶어 놓은 것 패키지 사용하기 import 사용 x - 소스 내에서 패키지 이름과 클래스 이름의 전체 경로명을 써주어야 함 java.util.Scanner import 사용 - 소스의 시작 부분에 사용하려는 패키지 명시(클래스만 명시) import java.util.Scanner; // 특정 클래스의 경로명만 포함 import java.util.*; // 패키지 내의 모든 클래스 포함 패키지 만들기 패키지 선언 package 패키지명; - 컴파일한 클래스 파일을 패키지명의 디렉터리에 저장하라는 명령 - 소스 파일의 첫 줄에 선언 - 클래스의 경로명은 "패키지명.클래스명" 디폴트 패키지와 패키지 특징 디폴트 패키지 - p..

자바 인터페이스의 구성 요소 (취소선 부분 생략 가능) 상수 public static final int X = 10; int X; int X = 10;은 public static final int X = 10;이 생략된 형태로 X라는 상수를 정의한 것이지만, int X;는 변수를 선언하는 것으로 해석되기 때문에 컴파일 에러가 발생 메소드 public abstract (abstract public) 추상 메소드 함수 몸통 부분 없음 사용하려면 반드시 함수 몸체 구현 필요 public default (default public) 인터페이스 내에서 메소드 정의({ } 부분이 필요함, 정의 안하면 컴파일 에러) 인터페이스 상속하여 default 메소드 사용 가능 오버라이딩 가능 Interface A -> Int..

탐색 리스트: 하나 이상의 필드로 된 레코드의 집합 키(key): 레코드를 구분하기 위해서 사용되는 필드 순차 탐색 template int SeqSearch(E *a, const int n, const K &k) { // a[1:n]을 왼쪽에서 오른쪽으로 탐색 // a[i]의 키 값이 k와 같은 가장 작은 i를 반환, 없으면 0 반환 int i; for (i = 1; i n) return 0; // i값을 찾지 못한 경우 return i; // i값을 찾은 경우 } 시간복잡도 - O(n) 순차 탐색의 성능 향상(정렬된 리스트의 경우) SepSearch의 for 조건 부분을 i n을 i > n || a[i] != k로 변경 탐색이 실패할 때 성능 향상 이원 탐색(Binary Search) int Binar..

신장 트리(spanning tree) G의 간선들로만 구성되고 G의 모든 정점들이 포함된 트리 신장트리는 G의 최소 부분 그래프(간선의 수가 가장 적은 부분 그래프) G'로서 V(G') = V(G)이고 G'는 연결되어 있음 신장트리는 n-1개의 간선 가짐 최소 비용 신장 트리 최저의 비용을 갖는 신장트리 Kruskal, Prim, Sollin 알고리즘 사용 신장 트리의 제한 조건 그래프 내에 있는 간선들만을 사용 정확하게 n-1개의 간선만을 사용 사이클을 생성하는 간선을 사용 금지 Kruskal 알고리즘 한 번에 하니씩 T에 간선을 추가해 가면서 최소비용 신장트리 T를 구축 T에 포함될 간선을 비용의 크기 순으로 선택 이미 T에 포함된 간선들과 함께 사이클을 형성하지 않는 간선만을 T에 추가 G는 연결되..

그래프 정의 그래프 G: 2개의 집합 V, E로 구성 V: 공집합이 아닌 정점(vertex)의 유한집합 E: 간선(edges)이라고 하는 정점 쌍들의 집합 표기: G = (V, E) 그래프의 제약 사항 자기 간선 또는 자기 루프 없음 동일 간선의 중복 없음 무방향 그래프 간선을 나타내는 정점의 쌍에 순서 없음 (u, v) = (v, u) 방향 그래프 방향을 가지는 정점의 쌍 로 표시 ≠ 완전 그래프 n개의 정점과 n(n-1)/2개의 간선을 가진 그래프 그래프 G의 부분그래프(subgraph) v(G') ⊆ V(G) 이고 E(G') ⊆ E(G)인 그래프 G' (u, v)가 E(G)의 한 간선이라면 u와 v는 인접 간선 (u, v)는 정점 u와 v에 부속 정점 u로부터 정점 v까지의 경로 그래프 G에서 \(..