필기용 블로그

○Tree

 ▷비선형 자료구조

 ▷선-후 관계 대신, 계층 구조를 가지는 자료구조 (부모 - 자식)

 ▶구성

  ▷Root: 부모가 없는 node (가장 상위의 node)

  ▷Internal node: 최소 하나의 자식을 가진 node

  ▷External node: 자식을 가지지 않은 node

  ▷Ancestors: 해당 node의 상위 node들 (부모, 부모의 부모, ...)

  ▷Depth: ancestors의 수

  ▷Height of tree: 최대 depth

  ▷Descendant: 해당 node의 하위 node들 (자식, 자식의 자식, ...)

  ▷Subtree: node와 그의 descendant로 이루어진 새로운 tree

 ▶ADT

  ▷각각의 abstract nodes에 대해 position을 적용함.

  ▶메소드

   ▶Generic

    ▷int size(): Tree의 크기

    ▷boolean empty(): 비어있는 Tree인가?

   ▶Accessor

    ▷position root(): Tree의 root의 position

    ▷list<position> positions(): 모든 노드의 positions

   ▶Position-based

    ▷position p.parent(): 노드의 부모

    ▷list<position> p.children(): 노드의 자식들

   ▶Query

    ▷boolean p.isRoot(): root인가?

    ▷boolean p.isExternal(): External node인가?

 ▶순회

  ▶Preorder Traversal (전위 순회)

   ▷방문 -> 자식 중 한명 방문 -> 자식의 자식 중 한명 방문 ...

  ▶Postorder Traversal (후위 순회)

   ▷자식의 자식 .. 방문 -> ... 자식 방문 -> 방문

 ▶구현

  ▶Linked Structure

   ▷Position ADT를 포함한다.

   ▷각 노드는 다음의 정보를 가진다.

    ▷Element (요소)

    ▷Parent node

    ▷Sequence of children nodes

○Sequence

 ▷Array List, Node List를 조합한 것.

 ▷index 또는 position으로 접근 가능

 ▷정렬된 자료들을 저장하는 기초적인 자료구조

 ▷stack, queue, vector, list를 대체 가능

 ▶메소드

  ▶Generic

   ▷size(): Sequence의 요소의 수 반환

   ▷empty(): Sequence가 비어있는가?

  ▶ArrayList-based

   ▷at(index): index에 있는 object 반환

   ▷set(index, object): index에 해당 object 할당.

   ▷insert(index): index에 해당 object 삽입

   ▷erase(index): index에 있는 object 제거.

  ▶List-based

   ▷begin(): 가장 앞의 position 반환.

   ▷end(): 가장 뒤의 position 뒤에 있는 가상의 position 반환.

   ▷insertFront(e): 가장 앞에 해당 element를 가진 position 추가

   ▷insertBack(e): 가장 뒤에 해당 element를 가진 position 추가

   ▷removeFront(): 가장 앞의 position 제거

   ▷removeBack(): 가장 뒤의 position 제거

   ▷insert(p, e): position p의 앞에 e를 가진 position 추가.

   ▷remove(p) : position p 제거.

  ▶Bridge

   ▷atIndex(i): index -> position

   ▷indexOf(p): position -> index

 ▶구현

  ▶Linked List Implementation

   ▷Doubly Link List로 만듬.

   ▷Node는 element, next node, previous node를 가지고 있음.

   ▷postion based -> O(1) / index vased -> O(n)

  ▶Array-based Implementation

   ▷Circular Array로 만듬.

   ▷Array는 position을 담고 있음.

   ▷position은 index와 element를 담고 있음.

   ▷중간 삽입, 삭제 -> O(n)

  ▶실행 시간 비교

○Deterministic Finite Automata

 ▶다음과 같은 5개의 요소들로 구성된 FSM (M = (Q, Σ, δ, q₀, F))

  ▷Q: state symbols의 알파벳 -> 원

  ▷Σ: input symbols의 알파벳 -> 라벨

  ▷δ: Q×Σ → Q인 transition function -> 라벨이 있는 directed edge

  ▷q₀: start state (q₀ ∈ Q) -> 라벨이 없는 directed edge가 가리키는 원(state)

  ▷F: final states set(F ⊆ Q) -> 선이 2개인 원

 ▶Machine-Oriented Viewpoint

  ▷기계로 생각해 보는 DFA - cell들이 있는 input tape, read-only head, FA controller

  ▷메모리가 없음.

  ▷head는 가장 왼쪽(start state)에서 부터 오른쪽으로 움직임

  ▷δ(current state, tape symbol) -> next state

 ▶configuration (상황)

  ▷QΣ*

   ▷Q: 현재 State

   ▷Σ*: 아직 남아있는 input string

  ▶configuration sequence (px ┣ qy)

   ▷x = ay이고, δ(p, a) = q일 때. (a ∈ Σ)

   ▷px에서 qy으로 configuration이 transition 가능함.

   ▶px ┣^k qy

    ▷px에서 k-steps 이후 qy로 transition함.

    ▷px ┣ rz, rz ┣^k-1 qy

    ▷┣⁺ ≡ ┣^k (k ≥ 1) : transitve closure

    ▷┣^* ≡┣^k (k ≥ 0), 자기 자신도 포함. : reflexive transitive closure

    ▷┣⁺이 가능하면, ┣^*도 가능하다.

 ▶Accepted Language (L(M))

  ▷M = (Q, Σ, δ, S, F)에 대해서

  ▷Sx ┣^* fλ가 성립하는 x (x ∈ Σ^*, f ∈ F)

  ▷DFA Language: 어떤 DFA에 대해 Accepted Language인 L

 ▶Equivalence of DFA

  ▷DFA M₁, M₂에 대해서

  ▷L(M₁) = L(M₂)이면, M₁과 M₂는 equivalent하다.

 ▶DFA 설계

  ▷1. 기억해야할 정보 결정, State로 표현

  ▷2. Input마다 State transition을 결정.

  ◎1이 짝수개 있는 String (Σ = {0, 1})

  ◎Substring 0101을 가진 String (Σ = {0, 1})

   ▷0101을 찾는다면 Final State에서 빠져나가지 않는다.

  ◎Substring 0101을 가지지 않은 String (Σ = {0, 1})

   ▷Dead State: 들어간다면, Final State로 갈 수 없는 State

  ◎L( (010+01)* )

○Mealy vs Moore

 ▶Moore: M = (Q, Σ, δ, q_0, F)

  ▷Q: state symbols의 알파벳 -> 원

  ▷Σ: input symbols의 알파벳 -> 라벨

  ▷δ: Q×Σ → Q인 transition function -> 라벨이 있는 directed edge

  ▷q_0: start state (q0 ∈ Q) -> 라벨이 없는 directed edge가 가리키는 원(state)

  ▷F: final states set(F ⊆ Q) -> 선이 2개인 원

 ▶Mealy: M = (Q, Σ, Γ, δ, γ)

  ▷Q: state symbols의 알파벳 -> 원

  ▷Σ: input symbols의 알파벳 -> 라벨 (앞)

  ▷Γ: output symbols의 앞바벳 -> 라벨 (뒤)

  ▷δ: Q×Σ → Q인 next state function -> 라벨이 있는 directed edge

  ▷γ: Q×Σ → γ인 output function

●Finite State Machine (FSM)

 ▷유한개의 State와 그 사이의 transition으로 구성된 상태도

 ▷각 상태는 특정 정보를 가지고 있다.

 ◎11을 찾는 FSM (Finite Automata)

○Exception Handling

 ▷프로그램에서 예상치못한 예외가 일어날 경우, 이를 처라히는 방법.

 ▶Exception (예외)

  ▷프로그램이 재대로 실행될 수 없는 상황

  ▷프로그램이 이상한 결과를 일으킬 수 있는 비정상적인 상황

  ◎Ex - Standard Exception, 기본적으로 내장

   ▷null 참조 (NullPointerException)

   ▷0으로 나눔 (ArithmeticException)

   ▷음수/범위를 벗어난 index (ArrayIndexOutOfBoundsExcepton)

   ▷Class 객체의 Casting 오류 (ClassCastException)

  ▶Checked vs Unchecked Exception

   ▷Checked: 도중에서의 에러 (입력 오류, 방해, ...)

    ▷Check Exception처리를 잘 해주는 것이 중요.

   ▷Unchecked: run-time 프로그래밍 과정에서의 에러, 컴파일 도중 에러가 발생한다.

 ▶try ~ catch

  ▷java에서 Exception을 처리하는 방법

  ▷try 내에서 exception이 throw되었을 경우, exception에 알맞은 catch구문으로 넘어간다.

   ▷throw new Exception();

  ▷rethrow: exception을 throw하고 catch하지 않는 경우, 해당 함수/메서드에 throw하는 exception을 명시해야 한다.

  ▶Multiple catch

   ▷여러 catch블럭을 하나의 try에 대해 정의할 수 있다.

   ▷다만, exception은 각기 다르거나, 부모 Exception이 뒤에 있어야 한다.

    ▷부모 Exception이 앞에 있을경우, 뒤의 자식 Exception들이 실행되지 못한다.

  ▶General Exception

   ▷모든 exception은 Exception Class를 상속받는다.

   ▷Exception은 모든 종류의 exception에 대해 반응 가능하다.

  ▶finally

   ▷언제나 실행되는 구문

   ▷try에서 exception이 throw되어도 실행된다.

   ▷try구문이 정상적이던 비정상적이던 resource를 안전하게 종료시키는데 사용된다.

  ▶try-with-resource (Java 7)

   ▷resource가 statement끝에 종료되는것을 보장한다.

   ▷java.lang.AutoCloseable을 implements한 Class에 대해서 지원한다.

○User-defined Exception

 ▷사용자가 exception을 직접 정의할 수 있다.

 ▷알맞은 exception을 상속받는다. (주로 RuntimeException)

○assert

 ▷단언문. boolean식을 포함하고 있다.

 ▷조건을 확인하고, 해당 조건을 만족하지 못하면 프로그램을 종료시킨다.

 ▷즉, 조건이 참임을 확신가능하다.

 ▷Precondition, Postcondition을 확인하는데 주로 사용된다.

 ▶사용

  ▶assert boolean식;

   ▷boolean식이 false이면 프로그램을 종료시킨다.

  ▶assert boolean식 : 수식;

   ▷boolean식이 false이면 수식을 실행하고, 프로그램을 종료시킨다.

 ▶enable / disable

  ▷-ea 옵션을 통해 assertion을 실행하거나, 무시할 수 있다.