2-1

Collection : 여러 원소들을 담을 수 있는 자료구조 ( = 인터페이스 . 각 자료구조들은 Collection인터페이스를 구현한 것이고, 이때 iterator가 사용된다 ) 세 가지 큰 분류 인터페이스 = List / Set / Map 1. List 인터페이스 : 순서가 있는 데이터 집합, 중복허용 o ->구현 클래스 : Linked List, Stack, Queue, ArrayList, Vector • LinkedList : 저장할 요소를 노드로 만들어 값과 포인터를 저장함. 삽입, 삭제 빠르나 탐색이 느리다. 단일/이중연결리스트 존재 • Vector : 연결리스트와 같은 동작을 수행, Thread-safe ! 동기화를 지원함. 한번에 한 스레드만 vector호출가능. 그치만 속도는 연결리스트보..

개념 : 객체의 결합을 통해 기능을 동적으로 유연하게 확장할 수 있게 하는 패턴 - 기본 기능에 추가할 수 잇는 기능의 종류가 많이 존재 (샷추가 같은거) -> 추가 기능을 Decorator 클래스로 정의한 후 -> 필요한 Decorator 객체를 조합하여 추가 기능의 조합을 설계함 ! - 음료수 처럼 기본 abstract 클래스 하나를 만듦 - 각 음료는 그걸 상속 - 첨가 옵션들은 1. Beverage (기본 component 클래스) 를 상속한 기본Decorator(추상)클래스만듦 2. 각 옵션은 1클래스를 상속함 -> 각 옵션 클래스들은 beverage 객체를 각각 가지고 있음 -> 해당 음료에 해당 옵션 추가한걸 리턴하는 함수 구현 Observer Pattern : 한 객체의 상태가 바뀔경우, ..

Design patter = 소프트웨어 설계할 때 자주 발생하는 문제들에 재사용할 수 있는 훌륭한 해결책 = 가이드로 사용할 수 있는 모델 혹은 설계 => 특정 상황에서 일반적인 문제에 대한 입증된 솔루션 ! - 이미 해결된 문제를 처리하기 위한 툴킷을 제공 - 소프트웨어 문제를 어떻게 해결할지 생각하는데 도움을 줌 - 23개의 디자인 패턴을 정리하고, 다음 3가지로 분류함 1. Creational(생성) : 객체 생성과 관련된 패턴 2. Structural(구조) : 클래스나 객체를 조합해 더 큰 구조를 만드는 패턴 3. Behavioral(행위) : 객체나 클래스 사이의 알고리즘이나, 책임 분재에 관련된 패턴 Singleton = 한 클래스에 대해 객체를 하나만 !! 생성할 수 있도록 한 것 -> 어..

ArrayList Class - java의 standard library class (java.util.ArrayList 에 있음) (lang이 기본으로 되는거고, 저거는 임포트 해줘야됨 ^^) = 동적 데이터 구조 -> 아이템이 리스트에서 추가되거나 삭제될 수 있고, 이때 배열 길이가 늘어나거나 줄어든다! -> 실행동안 배열의 길이를 변경할 수 있다는 점 을 제외하면 일반 배열과 동일한 용도로 사용됨! ( 일반적인 array : 초기 크기가 고정되어있으므로 정적 데이터 구조) • 구현 ; array를 private 멤버로 만들어 구현. 꽉차면 새로운 배열에 데이터를 옮기는 방식! - base type은 class type! (그래서 기본 자료형(primitive type)으로 배열 만들면 Integer..

Minimum-cost Spanning Tree Spanning tree - connected undirected weighted tree를 말한다 ( 모든 점들이 연결되어 있어야 하며 cycle이 없는 tree) - BFS / DFS 로 찾을 수 있다 - cost : 모든 엣지의 weight의 합 - 점이 n개면 엣지는 n-1개 (당연) -> spanning tree중에서 엣지들의 가중치 합이 최소인 트리를 찾는 알고리즘! 1. Kruskal Algorithm - edge를 이용! - 큭큭. 엣지잇게 엣지중에서 엣지하나선택 ㅋㅋ - 엣지를 오름차순으로 정리 - 젤작은거부터 하나씩 고름 ! 이때 사이클이 발생하지 않을때만 고른다! 모든간선에대해 다하면 끗 or n-1개 고르면 끗 복잡도는 O(eloge)..

* 선형 자료 구조 : array, linked list, stack, queue 비선형 자료구조 : tree, graph, hash ! Concepts • graph 정의 : 하나 이상의 노드들의 집합 V와 두 노드)의 쌍으로 구성된 edhe들의 집합 E로 이루어진 자료구조 ( 노드와 엣지의 집합으로 구성된 자료구조. pair(V, E) ) - tree는 graph의 특수한 경우 ! (Graph가 더 큰 범위) • 종류 Directed graph ( = digraph ) - 화살표 있는거 - self-loop 있음 Undirected graph - 화살표 없는거 - self-loop 없음 Weighed graph - 각 엣지에 가중치가 부여되는 것 (거리를 의미~~ 거리가 서로 다름~~ 노드사이의 거리..

Concept 정의 : M-way Search Tree + AVL tree - M-way search tree : 자식 노드가 최대 m개이고 최대 m-1개의 키를 갖는 탐색 트리 - 최소 𝑚/2(위로올림) 개의 자식을 가짐 쓰이는 곳 - database 와 file system에서 쓰임. 복잡도 O(log n)

레드블랙트리 개념 - 모든 노드의 컬러가 red / black 인 binary search tree - 모든 빈 노드(null pointer)가 외부 노드로 대체된다 (external node = 맨끝에잇는 리프노드. 네모) (자녀가 없음 -> 자녀를 nill 노드라고 설정함) - 복잡도 O(log n) !!! - rank : 해당 노드에서부터 external node까지 블랙노드 개수 lemma (부명제) - h 부모가 레드면 자식은 무조건 블랙 (삽입시 어기게됨) - 레드규칙 이라고 부름 - 루트에서(임의의 노드에서) 외부까지 모든경로에서 블랙 개수는 같다! (자기 자신은 제외) -> delete연산시 위반가능. 연산 1. insert 굿노트에 정리함~~

Interface - 추상 메소드의 집합, 일종의 추상 클래스 (extreme case of 추상클래스) - 실제로 구현된 게 전혀없는 기본 설계도 - 객체 생성 불가 ! - 클래스 작성에 도움을 줄 목적으로 사용. 미리 정해진 규칙에 맞게 설계하도록! • 클래스와 공통 - 여러 메소드 포함 가능 - .java 확장자 가진 파일로 저장 - 파일이름과 인터페이스 이름 일치해야함 - byte code는 .class파일에 • 클래스와의 차이 - 인터페이스는 인스턴스화 불가 - 생성자 포함xx - 인스턴스 변수 포함 불가 ; static final 만 가능 !! - 모든 메소드는 추상메소드 규칙 • 인터페이스는 객체화 불가!!(당연) • 인터페이스는 무조건 public • 인터페이스는 type임 -> 함수의 매..

Merge sort A. concept : 두 sorted list를 합친다. 각각 리스트의 맨첨 애를 비교해서 작은 애를 새로운 리스트에 넣는 방식 -> 리스트를 1개 될때까지 다 절반으로 divide 한 담에 차례로 merge 합니다 처음에는 sorted안되어있으니까 다 1개인걸로 쪼개놓으면 sorted니까 쪼개서 합치는 것!! B. Code C. Analysis : O(nlogn) !! - (worst average 둘다) T(1)=1, T(n)=2T(n/2)+n 알고리즘 정리한거 참고 Quick Sort = 분할 정복 divide-and conquer 알고리즘. (그대로 해결할 수 없는 문제를 작은문제로 분할하여 문제 해결함) 1. 피벗 하나를 정해서 앞에는 피벗보다 작은걸 배치, 뒤에는 피벗보다..