학습목표이진탐색트리 탐색, 삽입, 삭제 알고리즘을 이해한다.힙(Heap) 삽입, 삭제 알고리즘을 이해한다.PriorityQueue 클래스를 활용하여 힙을 사용할 수 있다.힙 정렬 알고리즘을 구현할 수 있다.전위 순회 : 0->1->3->7->8->4->9->10->2->5->11->6중위 순회 : 7->3->8->1->9->4->10->0->11->5->2->6후위 순회 : 7->8->3->9->10->4->1->11->5->6->2->0층별 순회 : 0->1->2->3->4->5->6->7->8->9->10->11 ★전위 순회는 뿌리->왼쪽 자식->오른쪽 자식 순★중위 순회는 왼쪽자식-> 뿌리-> 오른쪽 자식★후위 순회는 왼쪽자식->오른쪽 자식-> 뿌리★층별 순회는 그냥 노드의 순서대로1. 이진탐색트리..
트리(Tree)는 대표적인 비선형 자료구조 이다.노드들을 간선으로 연결한 계층형 자료구조제일위의 하나의 노드를 루트노드로 하여 나머지 노드들이 간선으로 연결 됨하나의 노드는 그자체로 트리이며 루트가 된다1. 이진트리 개념노드의 차수 -한노드가 가진 서브트리의 수 ex) A의 차수 : 3, B의 차수 : 2, C의 차수 : 0, D의 차수 : 3리프노드(단말,터미널) - 차수가 0인 노드 ex) 리프노드 : E, J, K, L, H, I자식 노드 -노드에 연결된 서브트리의 루트노드들 ex) A의 자식노드 : B, C, D부모 노드 -노드에 연결된 한단계 상위 레벨 노드 ex) I의 부모노드 : D형제 노드 - 부모가 같은 노드 ex) G, H, I 는 형제노드트리의 차수 - 노드가 가지고 있는 자식 노드의..
학습목표선택정렬 알고리즘을 이해하고, 구현할 수 있다.합병정렬 알고리즘을 이해하고, 구현할 수 있다.퀵정렬 알고리즘을 이해하고, 구현할 수 있다.이진검색 알고리즘을 이해하고, 구현할 수 있다.자바의 정렬/검색 메소드를 사용할 수 있다.1. 선택정렬(Selection Sort)남은 것들중에서 제일 작은걸 찾아서 왼쪽에 정렬선택정렬의 단계별 비교횟수의 합은(버블정렬 알고리즘 시간 복잡도) (n−1)+(n−2)+⋯+1=2n(n−1)=O(n2) 이다.따라서 버블정렬(선택정렬)의 시간 복잡도는 O(n2) 이다.import java.util.Arrays;public class SelectionSort { public static void selectionS..
학습목표FIFO 방식으로 동작하는 큐의 개념을 이해한다.선형큐, 원형큐, 연결큐를 자바로 구현 할 수 있다.자바 Queue 클래스를 활용할 수 있다.데크(Deque) 자료구조를 활용할 수 있다.1. 큐(Queue) 개념큐는 대기 줄과 유사한 개념으로, 데이터의 제거는 항상 가장 앞에서 수행되고, 데이터의 삽입은 가장 뒤에서 수행되는 구조이다. 이러한 특성으로 큐는 선입선출(FIFO, First In First Out) 형태의 자료구조로 알려져 있다.스택은 한 쪽 방향에서만 입출력이 발생한다.2. 큐 구현큐는 구현하는 방법에 따라 선형 큐, 원형 큐, 연결 큐로 구분된다.선형 큐(Linear Queue)선형 큐는 배열을 선형으로 사용하여 큐를 구현한다. 삽입을 반복하면 rear 위치가 계속 늘어나고, 삭제..
학습목표스택 자료구조의 개념과 동작 방식을 이해한다.배열 스택과 연결리스트 스택을 구현할 수 있다.자바 Stack 클래스를 활용할 수 있다괄호쌍 체크, 중위식을 후위식 변환, 후위식 계산 등 스택 응용을 구현할 수 있다.1. 스택 개념스택(Stack)은 ‘더미’ 또는 ‘쌓아 올림’을 의미하는 용어로, 데이터를 쌓아 올리는 형태로 저장하고 있어, 데이터를 추출할 때는 맨 위에 있는 데이터를 먼저 꺼내는 형태이다. 따라서, 스택은 제일 마지막에 저장한 데이터를 제일 먼저 꺼내는 후입선출(LIFO, Last In First Out) 형태의 자료 구조이다.스택은 가장 마지막 데이터의 위치인 top에서 삽입이나 삭제가 발생하므로 구조적으로 한 쪽 방향에서만 입출력이 수행된다.스택의 동작(연산)삽입 연산 : pus..
학습목표연결리스트 개념과 기본 연산에 대해 익힌다.자바로 연결리스트 클래스 직접 구현할 수 있다.자바 LinkedList 클래스를 활용할 수 있다.다항식을 연결리스트로 표현할 수 있다.순차 리스트 : 데이터를 메모리 공간에 연속적으로 저장한다연결 리스트 : 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 포인터는 이전이나 다음 노드를 가리킴1. 연결리스트 개념연결리스트(Linked List)는 데이터의 집합을 저장하기 위해 사용되는 자료구조로, 순차리스트 방식에서의 삽입, 삭제 연산 시간 및 저장 공간의 문제를 개선한 자료구조이다. 원형 연결리스트는 단순 연결리스트에서 마지막 노드가 첫 번째 노드를 가리켜 원형 구조로 연결되어 있는 리스트이다. 원형 연결리스트에서는 현재 노드의 이전 ..
순차리스트 기본 개념을 익힌다. 자바 클래스로 순차리스트를 구현할 수 있다. 스마트 배열인 ArrayList 클래스를 사용할 수 있다. 다항식을 순차리스트로 표현할 수 있다.1. 순차리스트(Linear List) 개념리스트는 다음과 같이 순서가 있는 원소들의 집합으로 표현 가능List = (원소 1, 원소2, …. , 원소n)원소가 하나도 없는 리스트는 공백 리스트 (Empty List) 라고 한다.중간에 데이터를 삽입하게 되면 그 데이터 뒤쪽에 있는 데이터들에 접근을 할 때 넣은 데이터 만큼 쉬프트연산으로 접근을 하기 때문에 데이터를 넣을 수록 접근 시간이 늘어 날 수 밖에 없다빈자리를 만들기 위한 원소들의 이동 횟수는 (마지막 원소 인덱스 - 삽입할 자리 인덱스 + 1)빈자리를 채우기 위한 원소들의 ..
자료구조는 컴퓨터에 저장된 자료를 효율적으로 이용할 수 있도록 하는 방법이다. 자료구조를 배우기 전에 자료를 표현하는 방법을 익혀야 한다. 자바 프로그래밍에서 자료구조 활용 능력을 향상시키기 위해 알아보자 일반적인 자료구조 서적에서는 추상자료형(ADT)을 이용하여 자료를 표기하지만, 여기에서는 자바의 자료형을 사용하여 자료를 표기한다. 자바의 자료형에 대해 살펴보자 1. 자바 자료형자바의 자료형은 크게 기본 자료형(Primitive Type)과 참조 자료형(Reference Type)으로 구분된다.자바 정수형 자료형의 최대값과 최소값을 출력하는 예제이다.public class MyIntTypeTest { public static void main(String[] args){ // byte형 System...
