벨만 포드 (Bellman-Ford) 알고리즘 한 노드에서 다른 노드까지의 최단거리를 구하는 알고리즘 - 최단 경로를 찾는 알고리즘 (다익스트라, 벨만 포드, 플로이드 와샬) - 가중치가 음수 일 때도 사용이 가능 - 다익스트라 알고리즘에 비해 느리므로 가중치가 모두 양수일 경우 다익스트라 알고리즘을 사용 - 경로 중에 음수 사이클이 존재하는 경우 확인 가능 음수 사이클 확인 방법 그래프의 정점의 개수를 V라고 할 때, 인접 간선을 검사하고 거리 값을 갱신하는 과정은 V - 1번이 필요 음수 사이클을 확인하기 위해 V - 1번 대신 V번 검사를 하고 V번째에 값이 갱신 되었을 경우, 음수 사이클이 존재 벨만-포드 알고리즘 프로세스 1. 시작 정점을 결정 2. 시작 정점부터 다른 정점까지 거리 값 모두 무..

분할 정복 알고리즘 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하는 개념 - 대표적으로 퀵소트, 병합정렬이 있음 - 문제를 둘 이상의 부분 분제로 나누는 자연스러운 방법이 있어야 함 - 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야 함 분할: 문제를 동일한 유형의 여러 하위 문제로 나눔 정복: 가장 작은 단위의 하위 문제를 해결하여 정복 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합 장점 - 문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결하는 데 큰 강점을 가짐 - 같은 작업을 더 빠르게 처리가 가능 단점 - 함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 ..

그리디 알고리즘 (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..