공부/자료구조

5 - 큐(Queue) 학습목표FIFO 방식으로 동작하는 큐의 개념을 이해한다.선형큐, 원형큐, 연결큐를 자바로 구현 할 수 있다.자바 Queue 클래스를 활용할 수 있다.데크(Deque) 자료구조를 활용할 수 있다.1. 큐(Queue) 개념큐는 대기 줄과 유사한 개념으로, 데이터의 제거는 항상 가장 앞에서 수행되고, 데이터의 삽입은 가장 뒤에서 수행되는 구조이다. 이러한 특성으로 큐는 선입선출(FIFO, First In First Out) 형태의 자료구조로 알려져 있다. 스택은 한 쪽 방향에서만 입출력이 발생한다.2. 큐 구현큐는 구현하는 방법에 따라 선형 큐, 원형 큐, 연결 큐로 구분된다.선형 큐(Linear Queue)선형 큐는 배열을 선형으로 사용하여 큐를 구현한다. 삽입을 반복하면 rear 위..

학습목표Kruskal 최소신장트리(MST) 알고리즘을 구현할 수 있다. Prim 최소신장트리(MST) 알고리즘을 구현할 수 있다. 다익스트라 최단경로 알고리즘을 구현할 수 있다.1. 최소신장트리(Minimum Spanning Tree) 알고리즘트리 = 비선형 자료 구조트리는 부모와 자식간의 관계밖에 표시가 안되는데 그래프는 다른 요소간의 관계도 표시할 수 있음 , 그래서 사이클이 만들어짐 이게 단점이 될 수도 있음  신장트리는 그래프에 최소한의 간선만 사용하여 전체 정점으로 연결하는 트리이다. 아래 그림에서 그래프 (b), (c), (d)는 그래프 (a)의 신장트리이다.연결을 하는데 간선을 최소로 하는 것최소 간선 : 노드 개수 - 1최소 간선을 사용하는 이유 : 오버헤드(비용) 문제를 해결 할 수 있다..

학습목표정점, 간선, 경로, 차수 등 그래프 관련 용어를 이해한다.인접 행렬, 인접 리스트로 그래프를 표현할 수 있다.DFS 알고리즘을 이해하고, 구현할 수 있다.BFS 알고리즘을 이해하고, 구현할 수 있다.1. 그래프 개념그래프 정의그래프는 현실 세계의 다양한 관계를 표현하는 자료구조로, 여러 개의 노드(node) 또는 정점(vertex)이 간선(edge)으로 연결되어 있는 구조이다. 도로망, 지인 관계, 링크 관계, 프로세스와 자원 간의 관계 등을 그래프로 모델링할 수 있어 다양한 분야에서 활용된다. 그래프는 방향성과 순환성에 따라 다양한 종류의 그래프로 나뉘며, 이를 통해 다양한 문제들을 해결할 수 있다.그래프 구성요소그래프는 정점(Node, Vertex)과 간선(Edge) 들의 집합으로 구성된다...

학습목표이진탐색트리 탐색, 삽입, 삭제 알고리즘을 이해한다.힙(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) + \cdots + 1 = \frac{n(n-1)}{2} = O(n^2)$ 이다.따라서 버블정렬(선택정렬)의 시간 복잡도는 $O(n^2)$ 이다.import java.util.Arrays;public class SelectionSort { public static void selectionS..

학습목표스택 자료구조의 개념과 동작 방식을 이해한다.배열 스택과 연결리스트 스택을 구현할 수 있다.자바 Stack 클래스를 활용할 수 있다괄호쌍 체크, 중위식을 후위식 변환, 후위식 계산 등 스택 응용을 구현할 수 있다.1. 스택 개념스택(Stack)은 ‘더미’ 또는 ‘쌓아 올림’을 의미하는 용어로, 데이터를 쌓아 올리는 형태로 저장하고 있어, 데이터를 추출할 때는 맨 위에 있는 데이터를 먼저 꺼내는 형태이다. 따라서, 스택은 제일 마지막에 저장한 데이터를 제일 먼저 꺼내는 후입선출(LIFO, Last In First Out) 형태의 자료 구조이다.스택은 가장 마지막 데이터의 위치인 top에서 삽입이나 삭제가 발생하므로 구조적으로 한 쪽 방향에서만 입출력이 수행된다.스택의 동작(연산)삽입 연산 : pus..

학습목표연결리스트 개념과 기본 연산에 대해 익힌다.자바로 연결리스트 클래스 직접 구현할 수 있다.자바 LinkedList 클래스를 활용할 수 있다.다항식을 연결리스트로 표현할 수 있다.순차 리스트 : 데이터를 메모리 공간에 연속적으로 저장한다연결 리스트 : 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 포인터는 이전이나 다음 노드를 가리킴1. 연결리스트 개념연결리스트(Linked List)는 데이터의 집합을 저장하기 위해 사용되는 자료구조로, 순차리스트 방식에서의 삽입, 삭제 연산 시간 및 저장 공간의 문제를 개선한 자료구조이다. 원형 연결리스트는 단순 연결리스트에서 마지막 노드가 첫 번째 노드를 가리켜 원형 구조로 연결되어 있는 리스트이다. 원형 연결리스트에서는 현재 노드의 이전 ..