컴퓨터기초 (6) 썸네일형 리스트형 이진탐색트리의 빅오 표기법... 이진탐색트리의 특성이 적혀 있다. 1. adelson velskil landis 이사람이 만든거다... 2. set 중복이 없다... 3. table 테이블 구조다 4. avl 1번의 약자다... G.M. Adelson-Velskii와 E.M. Landis 가 그들의 논문 "An algorithm for the organization of information" 1, 4번.. 1. 검색.. 탐색 기법에 대한 시간탐색도를 설명하기 전에 한가지 설명을 한다면.. root 노드를 기준으로 왼쪽과 오른쪽이 있다. 왼쪽은 작은 값이 들어가고 오른쪽은 큰 값이 들어간다. 1. 15를 기준으로 7이란 값은 작으므로 왼쪽으로 이동 2. 6이란 숫자보다 7이란 값은 크므로 오른쪽으로 이동 3. 7를 찾았다. 그렇다면 시.. 빅오표기법 및 Linked list(링크드리스트)의 시간복잡도에 대하여.... 시간복잡도를 설명하기전에.... 모든 개발자는 자신만의 시간 관념이 있습니다. 개발자들은 대부분의 시간을 사용자들에게 쏟아붓기 때문에, 최대한 시간을 효율적으로 사용하고 싶어하죠. 시간복잡도 를 최소화 함으로써 이게 실현가능해집니다 .프로그래밍에서 시간복잡도를 이해하기 전에, 먼저 이 시간복잡도가 알고리즘에서 흔하게 활용된다는 사실을 기억해야합니다 알고리즘이란??.... 알고리즘은 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들을 의미합니다. 하나의 예시를 들면?.. 밥짓는것을 예로 들어봅시다. 1. 쌀통에 쌀을 담는다. 2. 쌀을 물로 씻는다. 3. 적당량의 물을 담는다. 4. 밥솥에 넣고 취사버튼을 누른다. 5. 완료!!. 밥도 물을 어떻게 넣는냐에 따라 다르고..고산시대에.. Hash Table에 대해서.. Key 값을 가져와서 해쉬함수를 돌려서 반환받은 해쉬코드를 배열의 인덱스로 환산을 해서 데이터 접근하는 방식의 자료구조 Tree에 대해서 노드와 그 노드들을 연결하는 간선으로 이루어져 있다. 트리에 대한 설명 1. 트리에는 사이클(cycle)이 존재할 수 없다. 2. 노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다. 3. 각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있다. 4. 각 노드는 어떤 자료형으로도 표현 가능하다 왼쪽은 자식노드가 3개까지 가능한 트리며 오른쪽은 자식노드가 두개까지 가능한 이진 트리다. 하지만 대표적으로 쓰는 트리의 구조는 이진 트리며 오른쪽은 그 이진트리를 이진탐색트리로 만들어져있다. root 노드(최상위 노드)를 기점으로 왼쪽은 노드 보다 작은 값 오른쪽은 노드보다 큰값을 이어붙였다. Graph에 대해서... 그래프는 tree 구조의 한 종류라고 생각하면 된다. 동그라미 처럼 되어있는 노드(버텍스)와 그것을 이어주는 선 엣지(브런치)라고 말한다. 왼쪽에 있는 건 방향 그래프이며 오른쪽에 있는건 무방향그래프이다. 말그대로 방향 표시가 있고 없고의 차이다. 무방향 그래프는 양방향 모두 이어져 있으며 방향그래프는 방향에 맞게만 이어져 있습니다. 당연한거겠죠??? 그럼 바로 그래프를 코드로 표현하는 두방법에 대해서 알아봅시다. Adjacency Matxrix 노드간 연결관계를 이차원 배열로 표현한 것이다. Adjacency list 배열로 설정한다음 각 원소를 링크드 리스트로 표현한다. 총노드의 개수는 2m개 이므로 8개입니다. 그래프 탐색 기법에는 또 두가지가 있다 1) 깊이 우선 탐색(DFS) 2) 너비 우선 탐.. Linked List 에 대해서 1 . Linked List 원소를 배열처럼 차례대로 저장하지만, 원소들이 메모리상에 연속적으로 위치하지 않는다는 점이 다르다. 특징 다음과 같은 것들이 있다. 1. 연속되는 항목들이 포인터로 연결된다. 2. 마지막 항목은 Null을 가리킨다. 3. 프로그램이 수행되는 동안 크기가 커지거나 작아질 수 있다. 4. (시스템 메모리가 허용하는 범위내에서) 필요한 만큼 길어질 수 있다. 5. 메모리 공간을 낭비하지않는다,(하지만 포인터를 위한 추가의 메모리를 필요로 한다.) 배열에 비해 데이터의 추가/삽입 및 삭제가 용이하나 순차적으로 탐색하지 않으면 특정 위치의 요소에 접근할 수 없다. 그래서 일반적으로는 탐색 속도가 느리다. 그렇기에 탐색 또는 정렬을 자주하면 배열을, 추가/삭제가 많으면 연결리스트를 사용.. 이전 1 다음
