개발일지

추상 클래스 하나 이상의 메서드가 추상메서드이거나 abstract로 정의된 경우 public abstract class 클래스이름 { public abstract void 메서드이름(); } 추상 클래스는 인스턴스, 즉 객체를 만들 수 없는 클래스 입니다. (추상 클래스를 구현한 클래스의 인스턴스는 만들 수 있다.) 추상 메소드는 하위 클래스에서 메소드의 구현을 강제해야 합니다. 추상 메소드를 포함하는 클래스는 반드시 추상 클래스여야 합니다. 상속하는 집합간에는 연간관계가 있습니다. 다중 상속이 불가능합니다. 인터페이스 모든 메서드가 추상메서드인 경우 인터페이스는 ==상수와 추상메서드== 의 집합이다. interface 인터페이스이름 { public abstract void 메서드이름(); public ..

Tree node 와 edge 로 연결한 계층형hierarchical자료구조 하나의 노드로 이루어진 트리는 그 노드 자체가 트리이며, 루트이다 트리 용어 차수 (degree): 노드가 가지고 있는 서브트리의 수 리프, 단말: 차수가 0인 노드 비단말: 차수가 0이 아닌 노드 트리의 차수: 트리가 가지고 있는 노드 중에서 차수 중에서 최대 차수 레벨 트리의 높이: 트리의 최대 레벨 바이너리 트리 (이진 트리) 모든 노드가 두개의 서브트리나 리프노드인 트리 이진 트리 자체가 노드가 없는 공백 트리일 수 있음. 레벨 k의 최대 노드수는 2^k 높이가 h인 이진 트리의 최대노드 수 2^(h+1) - 1 편향 트리 포화 이진 트리 완전 이진 트리 완전 이진트리일까요 완전 이진트리 일차원 배열 표현 이진 트리의 인..

DFS(Depth First Search) DFS는 깊이 우선 탐색 알고리즘이다. DFS는 스택, 재귀함수를 사용하여 구현한다. 모든 그래프에 대해서 적용 가능한 탐색 알고리즘이다. 그래프 노드 탐색에서는 전위순회와 탐색하는 순서가 같다. 순서는 0, 1, 3, 4, 2, 5, 6 노드를 순차적으로 탐색한다. 인접 행렬을 사용할 경우 시간복잡도: O(V²) 노드 n의 인접 노드를 찾는 과정에서 O(V)의 시간복잡도가 필요하고, 모든 정점을 탐색해야하므로 V번 반복해야 하기 때문에 총 시간 복잡도는 O(V²) 가 된다. 인접 리스트를 사용할 경우 시간복잡도: O(V+E) 노드 n의 리스트에는 노드 n과 인접한 노드 개수만큼만(차수만큼) 들어있다. 다른 노드의 경우도 이러할 것이다. 이 개수를 모두 합하면 ..

Queue는 한쪽 끝(rear)에서는 enqueue, 또 다른 끝(front)에서는 dequeue 연산을 하는 유한 순서리스트이다. Queue는 FIFO(First in First out) 리스트이다. Queue ADT ADT Queue 데이타:0개 이상의 원소를 가진 유한 순서 리스트 연산: queue ∈ Queue; item ∈ Element; createQ() ::= create an empty queue; enqueue(queue, item) ::= insert item at the rear of queue; isEmpty(queue) ::= if (queue is empty) then return true else return false; dequeue(queue) ::= if (isEmpty(..

스택은 삽입과 삭제가 한쪽 끝 top에서만 이루어지는 유한 순서 리스트이며 주로 사용하는 함수가 push, pop이기에 pushdown 리스트라고도 한다. 스택은 LIFO(Last In First Out) 방식이기 때문에 스택을 역순으로 만드는데 유용하다. 스택 ADT ADT Stack 데이타 : 0개 이상의 원소를 가진 유한 순서 리스트 연산 : stack ∈ Stack; item ∈ Element; createStack() ::= create an empty stack; push(stack, item) ::= insert item onto the top of the stack; isEmpty(stack) ::= if (stack is empty) then return true else return f..

순차표현의 장점으로 표현이 간단하다는 것과 원소의 접근이 빠르다는 것(random access)이 있다.하지만 단점으로는 원소를 중간에 삽입, 삭제가 어렵고 저장공간의 낭비와 효율성적으로 문제가 있다. 연결표현 비순차 표현: 원소의 물리적 순서와 논리적 순서가 일치하지 않아도 되며 다음 원소에 대한 주소를 저장하고 있다. 하나의 노드는 데이터 필드와 링크 필드를 가지고 있다. class ListNode { String data; ListNode link; } ListNode startNode, p1, p2; p1 = new ListNode(); p2 = new ListNode(); p1.data = "첫번째 데이터"; p2.data = "두번째 데이터"; p1.link = p2; p2.link = nul..

algorithm : 특정 문제 해결을 위해 논리적으로 기술한 일련의 명령문 program : algorithm + data structure 알고리즘의 요건 완전성과 명확성 수행단계와 순서과 완전하고 명확해야 하고 지시한대로 실행하면 결과가 얻어 져야함. 입력과 출력 입력 : 알고리즘이 처리해야 할 대상으로 제공되는 data 출력: 입력 data를 처리하여 얻은 결과 유한성 유한한 단계 이후에는 반드시 종료되어야 한다.ADL (Algorithm Description Language) 알고리즘 기술을 위해 정의한 언어이며 사람이 이해하기 쉽고 프로그래밍 언어로의 변환이 용 이하다. ADL 데이터 : 숫자, bool값, 문자 알고리즘의 표현 ADL 명령문 : 지정문, 조건문, 반복문, 함수문, 입력문 …,..

순차적 메모리 할당 방식이며 쌍의 집합이다. 원소들이 모두 같은 타입, 같은 크기를 가진다. 인덱스: 순서를 나타내는 원소의 유한 집합이며 집합 내 상대적 위치를 식별하는데 사용된다. 인덱스 만으로 원하는 원소를 직접 접근하기에 내부 구현을 알 필요가 없다.(정보은닉) 메모리 표현 연속적인 메모리 주소를 배열에 할당한다. 순차 사상: 배열의 논리적 순서와 메모리의 물리적 순서가 같도록 표현한다. 순차 표현: 순차 사상을 이용하여 데이터를 표현한다. 순차 사상의 특징으로 인해 빠르게 검색이 가능하다. 하지만 메모리의 크기를 할당하면 크기를 바꿀수 없다는 점과 삽입, 삭제가 다른 자료구조들에 비해 어렵다는 특징이 있다. 배열 추상 데이터 타입(ADT) public class Array { private Ob..