그리디 알고리즘 (Greddy Algorithm) 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하는 방식의 알고리즘 - 탐욕 알고리즘, 욕심쟁이 알고리즘으로도 불림 - 최적해를 구하는 상황에서 사용하는 방법 - 최적해를 보장해주지 않음 - 대표적으로 거스름돈, 다익스트라 알고리즘이 있음 ex) 자식노드로 향하면서 가장 높은 값을 얻을 때 그리디 알고리즘을 사용한다면 그리디 알고리즘은 처음 7과 13에서 13이 크기때문에 13을 선택 그 후 5와 11을 비교해서 11이 크므로 11을 선택해서 결과값 24를 도출 하지만 처음에 7을 선택하고 후에 100을 선택해서 107의 결과값을 도출하는것이 최적해

해싱(Hashing) 키 값을 특정한 계산을 통하여 나온 결과를 주소로 사용하여 값에 접근하는 과정 - 키와 벨류를 매핑시키는 과정 - 빠른 탐색과 삽입,삭제를 통하여 항목간의 관계를 모형화 하는데 유용함 - 키 값에 직접 산술적인 연산을 적용, 테이블의 주소를 계산하여 접근 - 키값의 연산에 의해 직접 접근이 가능한 구조를 해시 테이블 이라 부르고 테이블을 이용한 탐색 추상 자료형 사전구조 - 인터페이스와 기능 구현을 분리한 자료형 - 기능 구현구분을 명시하지 않아 사용 시에는 기능이 어떻게 돌아가지 몰라도 되는 편리함을 가짐 - 대표적으로 스택 큐 연결리스트 딕셔너리 - 해시 테이블은 인터페이스만을 보았을때는 데이터 식별자로 숫자 뿐만아니라 문자열 파일등을 받아와 Value를 연상 해싱의 구조 - 어..

B 트리 말단 노드를 제외한 모든 노드는 2개 이상의 자식 노드를 가지는 트리 데이터를 정렬하여 탐색, 삽입, 삭제 및 순차 접근이 가능하도록 유지하는 트리형 자료구조 이진트리를 확장해서 더 많은 수의 자식을 가질 수 있게 일반화 - Balanced - Tree 의 일종 - B 트리는 하나의 노드에 여러 자료가 배치되는 트리구조 - 한 노드에 M개의 자료가 배치되면 M차 B 트리라고 함 - 데이터베이스와 파일시스템에 널리 사용 - 노드 내의 데이터는 오름차순으로 정렬 - 모든 말단 노드는 항상 레벨이 같음 - 새로운 값은 항상 말단노드에 삽입 B+ Tree B-Tree와 유사하지만 연결리스트 내부의 데이터 탐색을 용이하게 하는 자료구조 모든 말단 노드는 연결리스트로 구현되어 있음 말단 노드가 아닌 노드들..

AVL 트리 AVL트리는 트리가 한쪽으로 치우쳐 자라나는 현상을 방지하여 트리 높이의 균형을 유지하는 이진탐색트리 노드의 두 하위 트리(왼쪽, 오른쪽)의 높이의 차이가 최대 1을 넘지 않음 엄격하게 균형을 유지하기 때문에 Red-black 트리보다 더 빠른 성능을 가지지만 더 많은 작업이 필요 대부분의 연산은 이진탐색트리와 동일 삽입 삭제 연산은 트리가 균형을 유지하는지 확인 Linked List, Binary Search Tree, Balanced Binary Tree 차이점 1. Linked List - 구현이 쉬움 - 많은 포인터(참조)를 저장 - O(N) 시간복잡도를 가짐 2. Binary Search Tree - 탐색의 O(N) 시간복잡도를 O(logN) 시간복잡도로 줄임 - Unbalanced..

이진 탐색 트리란 이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조 왼쪽 자손 노드에는 현재 노드 보다 작은 값을, 오른쪽 자손 노드에는 현재 노드보다 큰 값을 넣는 방식의 트리 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안 연결리스트의 경우 자료 입력, 삭제에 필요한 계산복잡성은 O(1), 탐색하는 데에는 O(n)의 계산복잡성이 발생 두개의 이점을 합치기 위해 만든 자료구조 - 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어짐 - 각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어짐 - 중복된 노드는 없어야 함 - 왼쪽 서브트리, 오른쪽 서브트리 또한 이진 탐색..

트리순회(tree traversal)란 트리의 각 노드를 체계적인 방법으로 방문하는 과정 노드를 방문하는 순서에 따라 세 가지로 나뉘어짐 - 전위순회(preorder) - 중위순회(inorder) - 후위순회(postorder) V => 루트 또는 어떤 서브트리의 루트노드 L => 왼쪽 서브트리 R =>오른쪽 서브트리 전위 순회 순서 : V->L->R 중위 순회 순서 : L->V->R 후위 순회 순서 : L->R->V 전위 순회 루트 노드에서 시작해서 노드-왼쪽 서브트리-오른쪽 서브트리 순으로 순회하는 방식 깊이우선순회(depth-first traversal)라고도 불림 중위 순회 왼쪽 서브트리 노드에서 시작해서 루트 노드 - 오른쪽 서브트리 순으로 순회하는 방식 대칭순회(symmetric travers..

탐색이란 여러 개의 자료 중에서 원하는 자료를 찾는 작업 탐색키와 데이터로 이루어진 여러개의 항목 중에서 원하는 탐색 키를 가지고 있는 항목을 찾는 방법 정렬되지 않은 배열에서의 탐색 1. 순차 탐색 (Sequential Search) 데이터의 첫 부분부터 순차적으로 데이터를 비교하여 원하는 데이터의 위치를 찾는 알고리즘 탐색 방법중에서 가장 간단하고 직접적인 탐색 방법 평균 비교 횟수 탐색 성공 : (n + 1)/2번 비교 탐색 실패 : n번 비교 시간 복잡도 : O(n) 코드 int seqSearch(int key,int low, int high){ int i; for(i = low;i

프림 알고리즘 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법 - 정점선택을 기반으로 하는 알고리즘 - 이전 단계에서 만들어진 신장 트리를 확장하는 방법 동작과정 1. 시작 단계에서는 시작 정점만이 MST집합에 포함 2. 앞 단계에서 만들어진 MST집합에 인접한정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장 (가장 낮은 가중치를 선택) 3. 위의 과정을 트리가 N-1개의 간선을 가질때까지 반복 시간복잡도 주 반복문이 정점의 수 N만큼 반복하고 내부 반복문이 N번 반복 - 프림 알고리즘의 시간복잡도 O(n^2) - 그래프에 간선이 많이 존재하는 밀집 그래프에 프림 알고리즘이 적합