CokeWorld DevLog CokeWorld DevLog

순차 검색(Linear Search) 일렬로 되어있는 자료를 처음부터 마지막까지 순서대로 비교하여 검색하는 방법 가장 간단하고 직접적인 방법 순차 검색 자바 구현 public class SequentialSearch { public static void main(String[] args) { int unorderedArr[] = {26, 35, 88, 44, 34, 12, 96, 31, 64}; int orderedArr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; SequentSearch ss = new SequentSearch(); ss.searchUnorderedList(unorderedArr, 12); ss.searchOrderedList(orderedArr, 9); } } clas..

삽입 정렬(Insertion Sort) 정렬되어 있는 부분집합에 새로운 원소의 순서를 찾아 삽입하는 방법 삽입 정렬 자바 구현 public class InsertSort { public static void main(String[] args) { int arr[] = {3, 6, 4, 87, 54, 23, 44, 65, 21, 95}; InsertionSort is = new InsertionSort(); is.sort(arr); for (int i = 0; i < arr.length; i++) { System.out.printf(" %d", arr[i]); } System.out.println(); } } class InsertionSort { public void sort(int arr[]) { fo..

버블 정렬(Bubble Sort) 인접한 두개의 원소를 비교하여 자리를 교환하는 방식을 첫 번째 원소부터 마지막 원소까지 반복한다. 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다. O(N²) 버블 정렬 자바 구현 public class BubbleSort { public static void main(String[] args) { int arr[] = {23, 5, 35, 66, 11, 77, 24, 34, 54}; BubSort bs = new BubSort(); bs.bubbleSort(arr); for (int i = 0; i < arr.length; i++) { System.out.printf(" %d", arr[i]); } System.out.println(); } } class Bu..

깊이 우선 탐색(DFS, Depth First Search) 수행 순서 시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색 더 이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아옴. 그 정점에서 다른 방향의 간선으로 탐색을 계속하여 모든 정점을 방문 스택 사용 깊이 우선 탐색을 반복하기 위해 가장 마지막에 만났던 갈림길 간선의 정점으로 가장 먼저 되돌아가야한다. 너비 우선 탐색(BFS, Breadth First Search) 수행 순서 시작 정점으로부터 인접한 정점들을 모두 차례로 방문 그 후 방문했던 정점을 다시 시작점으로 설정 그 시작점에서 인접한 정점들을 차례대로 방문 큐 사용 인접한 정점들에 대해서 차례로 다시 너비 우선 탐색을 반복해야한다. DFS, B..

그래프란? 연결된 원소간의 관계를 표현하는 자료구조 SNS 친구관계, 수도 배수 시스템, 물질의 분자구조 등에 적합한 자료구조 그래프의 종류 무방향 그래프(Undirected Graph) 두 정점을 연결하는 간선에 방향이 없는 그래프 방향 그래프(Directed Graph) 간선에 방향이 있는 그래프 완전 그래프(Complete Graph) 한 정점에서 다른 모든 정점과 연결 된 그래프 최대의 간선 수를 가진 그래프 부분 그래프 원래의 그래프에서 일부의 정점이나 간선을 제외한 그래프 가중 그래프(Weight Graph) 간선에 가중치를 할당한 그래프 그래프 관련 용어 인접(adjacent): 그래프의 두 정점이 연결되어 간선이 있을 때, 두 정점을 인접되어 있다고 함. 부속(incident): 두 정점이..

힙이란? 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해서 만든 자료구조 일반적으로 힙은 최대 힙을 의미 같은 키값의 노드 중복 가능 최대 힙(Max Heap) 키 값이 가장 큰 노드를 찾기 위한 힙 부모 노드의 키값 >= 자식 노드의 키값 최소 힙(Min Heap) 키 값이 가장 작은 노드를 찾기 위한 힙 부모 노드의 키값

이진 탐색 트리란? 저장할 데이터의 크기에 따라 노드의 위치를 정의한 이진 트리 효율적인 탐색을 위한 자료 구조 이진 탐색 트리의 조건 모든 원소는 서로 다른 유일한 키를 갖는다. 왼쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 작다. 오른쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 크다. 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리다. 그림 설명 루트 8의 왼쪽 자식노드인 3은 루트보다 작다. 오른쪽 자식노드인 10은 루트보다 크다. 레벨2에 위치한 부모노드 3의 왼쪽 자식노드인 1은 부모노드보다 작다. 오른쪽 자식 노드인 6은 부모노드보다 크다. 이진 탐색 트리 효율성 이진 탐색 트리 정렬된 배열 검색 O(log N) O(log N) 삽입 O(log N) O(N) 삭제 O(l..

1. 트리(Tree) 1-1 트리란? 비선형 자료구조 중에서 자료간에 계층관계를 가진 계층형 자료구조(Hierachical Dta Structure)다 1-2 트리 주요 용어 노드: 트리를 구성하는 원소 간선(edge): 노드를 연결 선 루트 노드(Root Node): 트리의 시작 노드 형제 노드(Sibling Node): 같은 부모노드의 자식노드들 서브 트리(subtree): 각 노드의 모든 자식노드 차수(degree): 한 노드가 가지는 서브 트리의 수 리프 노드(Leaf Node): 차수가 0인 노드 포리스트(forest): 여러 트리들의 집합 2. 이진 트리(Binary Tree) 2-1 이진트리란? 모든 노드의 차수가 2 이하인 트리 2-2 이진 트리의 분류 포화 이진 트리(Full Binary..