yoongrammer

목차이진 탐색 (Binary search) 개념 및 구현이진 탐색은 정렬된 리스트에서 검색 범위를 줄여 나가면서 검색 값을 찾는 알고리즘입니다. 이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있습니다. 동작 방식이진 탐색 알고리즘은 리스트의 중간 값과 비교하여 검색값을 찾습니다.중간 값을 찾아야 하기 때문에  반드시 정렬된 배열에서만 사용할 수 있습니다. 이진 탐색의 동작 방식은 다음과 같습니다. 배열의 중간 값을 가져옵니다.중간 값과 검색 값을 비교합니다.중간 값이 검색 값과 같다면 종료합니다. (mid = key)중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색합니다. (mid..

목차 순차 검색(Sequential Search) 개념 및 구현순차 검색(Sequential Search)은 선형 검색(Linear Search)으로도 불리며 리스트에서 순차적으로 탐색하면서 원하는 값을 찾아내는 알고리즘입니다. 순차 검색은 구현이 쉽고 리스트의 정렬 여부와 상관없이 동작하는 장점이 있지만, 리스트의 모든 요소를 확인해야 하기 때문에 검색할 리스트의 길이가 길면 비효율적이라는 단점이 있습니다. 시간 복잡도(Time complexity)OperationBestAverageWorstSearchO(1)Θ(n)O(n)*n = 데이터 수 종료 조건순차 검색의 종료 조건은 두 가지가 있습니다. 다음 조건중 하나라도 성립하면 검색을 종료합니다. 1. 검색을 실패할 경우검색할 값을 발견하지 못하고 리스..

목차다원 탐색 트리 (Multiway search tree)다원 탐색 트리(Multiway search tree)는 m-원 탐색 트리 (m-way search tree)라고도 합니다. 다원 탐색 트리는 한 노드안에 최대 m-1개의 요소와 m개의 자식을 가질 수 있습니다.이진 탐색 트리는 m=2 인 다원 탐색 트리입니다.다원 탐색 트리의 특징다원 탐색 트리는 다음과 같은 특징이 있습니다. 1. 각 노드는 아래의 개수만큼 서브 트리를 갖습니다.\(0 ≤ 서브트리 개수 ≤ m\)2. k 개의 자식 노드를 가지는 노드는 k-1개의 요소를 갖습니다. (k ≤ m)3. 각 노드 안에 있는 키는 오름차순으로 정렬되어 있습니다.\(key_1 ≤ key_2 ≤ ... ≤ key_{(k-1)}\)4. 다음 조건을 항상 만..

목차AVL 트리(Tree) 개념 및 구현AVL 트리는 스스로 균형을 잡는 이진 탐색 트리입니다. 트리의 높이가 h일 때 이진 탐색 트리의 시간 복잡도는 O(h)입니다.한쪽으로 치우친 편향 이진트리가 되면 트리의 높이가 높아지기 때문에 이를 방지하고자 높이 균형을 유지하는 AVL 트리를 사용하게 됩니다. AVL트리는 다음과 같은 특징을 가집니다.AVL 트리는 이진 탐색 트리의 속성을 가집니다.왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1 입니다.어떤 시점에서 높이 차이가 1보다 커지면 회전(rotation)을 통해 균형을 잡아 높이 차이를 줄입니다.AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN) 입니다. Balance Factor(BF)Balance F..

목차이진 탐색 트리 (BST, Binary Search Tree)이진 탐색 트리란 정렬된 이진트리로써 다음과 같은 속성을 가지고 있습니다.노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가있는 노드 만 포함됩니다노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가있는 노드 만 포함됩니다.왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리 여야합니다.중복된 키를 허용하지 않습니다.이러한 이진 탐색 트리의 특성 때문에 효율적인 검색이 가능합니다. 생성 예시50, 15, 62, 80, 7, 54, 11주어진 요소를 사용하여 BST를 생성하는 과정은 다음과 같습니다.50을 트리의 루트로 트리에 삽입합니다.다음 요소를 읽고 루트 노드 요소보다 작 으면 왼쪽 하위 트리의 루트로 삽입합니다.그렇지 않으면 오른쪽 하위 트..

목차 트리 순회 (Tree Traversal)트리의 모든 노드들을 방문하는 과정을 트리 순회(TreeTraversal)라고 합니다.선형 자료 구조(연결 리스트, 스택, 큐 등)는 순차적으로 요소에 접근하지만 트리 자료구조는 다른 방식을 사용해야 합니다. 일반적으로 트리 순회에는 다음과 같은 방법들이 있습니다.전위 순회 (Preorder)중위 순회 (Inorder)후위 순회 (Postorder)이러한 순회는 보통 재귀로 쉽게 구현할 수 있습니다.전위 순회 (Preorder Traversal)전위 순회는 깊이 우선 순회(DFT, Depth-First Traversal)이라고도 합니다. 트리를 복사하거나, 전위 표기법을 구하는데 주로 사용됩니다.트리를 복사할때 전위 순회를 사용하는 이유는 트리를 생성할 때 자..

목차[자료구조] 이진트리 (Binary tree) 알아보기이진트리(Binary tree)란 모든 노드들이 둘 이하의 자식을 가진 트리입니다.이진트리 유형전 이진트리 (Full Binary Tree or Strict Binary Tree)전 이진 트리는 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리입니다.완전 이진 트리 (Complete Binary Tree)완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리입니다.마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 합니다.포화 이진 트리 (Perfect Binary Tree)포화 이진 트리는 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 잎 노드가 동일한 깊이 또는 레벨을 갖습니다.균형 이진..

목차트리 (Tree)트리 (Tree)란 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조입니다. 트리는 다음과 같이 나무를 거꾸로 뒤집어 놓은 모양과 유사합니다.트리는 또한 트리 내에 다른 하위 트리가 있고 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료구조이기도 합니다. 컴퓨터의 direcory구조가 트리 구조의 대표적인 예가 될 수 있습니다.트리 구조에서 사용되는 기본 용어노드 (Node)트리를 구성하고 있는 기본 요소노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음.A, B, C, D, E, F, G, H, I, J간선 (Edge)노드와 노드 간의 연결선루트 노드 (Root Node)트리 구조에서 부모가 없는 최상위 노드root node : A부모 노드 (Parent N..

목차교착상태(Dead Lock) 해결 방법일반적으로 교착 상태를 해결하는 방법에는 세 가지가 있습니다.교착 상태 예방(Prevention) 또는 회피(Avoidance)교착 상태가 되지 않도록 합니다.교착 상태 탐지(Detection) 및 복구(Recovery)교착 상태가 탐지되면 시스템에 문제가 발생하지 않도록 조치를 취합니다.교착상태 무시(Ignore)교착 상태가 정말 드물게 발생하는 경우(1년에 한번) 교착 상태 예방 또는 탐지와 관련된 지속된 오버헤드 및 성능 저하를 발생 시키는 것보다 교착 상태가 발생하도록 하고 필요에 따라 재부팅하는 것이 더 나을 수 있습니다. (Unix 및 window를 포함한 대부분의 운영체제가 사용하는 방법) 교착 상태 예방 (Deadlock Prevention)교착 상..

목차교착상태(Dead Lock) 알아보기교착상태(Dead Lock)은 상호 배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한 대기하는 현상을 의미합니다.교착상태 조건교창상태가 일어나려면 다음과 같은 네 가지 조건을 모두 충족시켜야 합니다.상호 배제 (Mutual exclusion)자원은 한 번에 한 프로세스만이 사용할 수 있어야 한다.점유 대기 (Hold and wait)최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.비선점 (No preemption)다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한..