자료구조,알고리즘7 자료구조의 정리와 이해(AVL 트리) 균형트리 AVL트리는 트리가 한쪽으로 치우쳐 자라나는 현상을 방지하여 트리 높이의 균형을 유지하는 이진탐색트리 Balanced 이진탐색트리를 만들면 N개의 노드를 가진 트리의 높이가 O(logN)이 되어 탐색,삽입,삭제 연산의 수행시간이 O(logN)이 보장된다. -Linked List 구현이 쉬움 많은 포인터를 저장 O(N) 시간복잡도를 가짐 - Binary Search Tree 탐색의 O(N) 시간 복잡도를 O(logN) 시간복잡도로 줄임 Unbalanced Tree일 경우 탐색의 속도는 느려짐 - Balanced Binary Tree(AVL Tree,Red-Black Tree) 균형을 이루도록 보장 항상 O(logN)의 시간 복잡도를 보장 AVL Tree의 특성 1. 이진탐색트리 연산 실행시간은 이진탐색트리.. 2022. 5. 11. 자료구조의 정리와 이해(Binary Search Tree) 이진탐색트리 Binary Search Tree란 이진 탐색 트리는 이진탐색의 개념을 트리 형태의 구조로 접목한 자료구조이다. 1.Binary Search란 이진 탐색은 정렬된 데이터의 중간에 위치한 항목을 기준으로 데이터를 두 부분으로 나누어가며 특정 항목을 탐색하는 방법이다. Tree란 배열이나 연결리스트는 데이터를 일렬로 저장하기 때문에 탐색 연산이 순차적으로 수행되어야 한다는 단점을 가집니다. 배열은 미리 정렬해 놓으면 이진 탐색을 통해 효율적인 탐색이 가능하지만 삽입이나 삭제 후에도 정렬상태를 유지해야 하므로 삽입이나 삭제하는데 O(n)시간이 소요된다. 이러한 문제를 보완한 것이 계증적 자료구조인 트리이다. 트리는 실제 트리를 거꾸로 세워 놓은 형태의 자료구조로 HTML,XML,자바 클래스 계층구조, 운영체제.. 2022. 5. 11. 자료구조의 정리와 이해(Queue) Queue의 특징 삽입과 삭제가 양 끝에서 각각 수행되는 자료구조 기본연산 : enqueue(),dequeue(),shock() FIFO(First In First Out) : 선입선출 구조 Dynamic array,Linked List 로 구현이 가능 BFS 알고리즘 구현에 중요 Queue의 Enqueue연산 Enqueue연산은 새로운 항목을 Queue의 끝에 추가하면 된다. Queue의 Dequeue연산 Dequeue 연산은 Queue의 첫번째 항목부터 제거하면 된다. Queue의 활용 리소스가 여러 쓰레드에 공유되는 경우 대기열에 저장 : CPU scheduling 두 프로세스 간에 비동기식으로 데이터가 전송되는 경우 : IO buffer 2022. 5. 11. 자료구조의 정리와 이해(Stack) Stack의 특징 Stack은 한 쪽 끝에서만 항목을 삭제하거나 새로운 항목을 저장하는 자료구조이다. 스택에서 새로운 항목을 저장하는 연산을 push라고 하고, 항목을 삭제하는 연산을 pop이라고한다. - LIFO(Last In First Out) : 선입 선출 - 대부분의 고수준의 언어에서 스택은 Array나 Listed List 로 쉽게 구현할 수 있다. push,pop,peek 연산 3개 다 O(1) 시간 복잡도를 가진다. Stack in memory management(Stack,Heap) 1.Call Stack - 프로그램의 코드정보(서브루틴 / 메소드 / 함수)를 저장하는 Stack 자료구조이다. - 세부 정보는 일반적으로 고급 프로그래밍 언어에서는 숨겨져있고, 자동화 되어있다. - Stack.. 2022. 5. 11. 자료구조의 정리와 이해(Linked List) Linked List란 Linked List는 동적 메모리 할당을 이용해 리스트를 구현하는 가장 간단한 형태의 자료구조이다. 동적 메모리를 할당 받아 노드를 저장하고 노드는 참조를 이용하여 다음 노드를 가리키도록 만들어 노드들을 한 줄로 연결한다. // 하나의 노드는 integer,object와 같은 데이터를 포함하고 있으며, 다음 노드를 가르키는 참조 변수를 포함하고 있다. Linked List의 구성 Linked Link의 노드는 데이터와 참조값으로 구성되는데 참조값은 한 노드에서 다른 노드를 가리키는 포인터 역할을 한다. 마지막 참조값은 null을 가리키게 된다. Linked List의 특성 Linked List는 단순하고 매우 일반적인 데이터 구조로 Stack, Queue 등의 다른 일반적인 데이.. 2022. 5. 11. 자료구조의 정리와 이해(Array) Array Array란 동일한 타입의 원소들이 연속적인 메모리 공간에 할당되어 각 항목이 하나의 원소에 저장되어 있는 기본적인 자료구조이다. Array의 구성 배열의 인덱스 또는 키로 식별되는 요소 / 값의 컬렉션 인덱스는 0부터 시작 인덱스 떄문에 랜덤 엑세스 가능 Array의 특성 배열은 동일한 유형의 타입을 저장하기 위한 자료구조 배열은 인덱스를 키로 사용 배열은 원하는 만큼의 차원을 가질 수 있음, 1차원/2차원/3차원 배열 등 동적배열 : 배열의 크기가 동적으로 변경되는 경우 응용 프로그램에는 table,hashtable,heap이 있음. Array의 장점 - 인덱스, 즉 키 때문에 랜덤 엑세스가 가능하다 - 구현 및 사용이 쉽다. - 매운 빠른 자료구조로 항목을 반복해서 추가하거나, 삭제하려고.. 2022. 5. 11. 알고리즘의 기초 이해 알고리즘의 조건 입력- 0개 이상의 입력이 존재해야한다.(입력이 없어도 된다) 출력 - 1개이상의 출력이 존재해야한다. 명백성 - 각 명령어의 의미는 모호하지않고 명확해야 한다. 유한성 - 한정된 수의 단계 후에는 반드시 종료되어야 한다. 유효성 - 각 명령어들은 실행 가능한 연산이여야 한다. 알고리즘의 기술방법 자연어 ( ex)메뉴얼 ) 1.읽기 쉬움 2.단어들을 정확하게 정의하지 않으면 의미 전달이 모호 흐름도 1.직관적이고 이해하기 쉬운 알고리즘 기술방법 2.그러나 복잡한 알고리즘의 경우 상당히 복잡해짐 유사코드(슈도코드) 1. 알고리즘의 고수준 기술 방법 2. 자연어보다는 더 구조적인 표현방법 3. 프로그래밍 언어보다는 덜 구체적 프로그래밍 언어 1. 알고리즘의 가장 정확한 기술이 가능 2. 실제.. 2022. 5. 6. 이전 1 다음
