자료구조 (9) 썸네일형 리스트형 [파이썬 | 자료구조] 9. 그래프(Graph) 9. 그래프(Graph) 9.1 그래프의 개념 그래프란 정점과 간선들로 이루어진 집합으로 표현되는 자료구조 트리도 일종의 그래프라고 할 수 있다. 9.2 그래프의 종류 무방향 그래프 : 간선이 방향을 가지지 않음 방향 그래프 : 간선이 방향을 가지고 있음 가중치 그래프 : 각 간선에 가중치 정보가 포함됨. 가중치는 거리, 비용 등으로 표현 할 수 있다. 9.3 그래프의 구현 인접 행렬 기반 그래프 각 정점간의 가중치나 간선의 유무를 행렬로 표현한다. 무방향 그래프의 경우 전치행렬이 되어도 값이 같다. 인접 리스트 기반 그래프 인접 행렬이 행렬을 이용한것과는 달리 인접 리스트로 구현한다. 파이썬에서는 그냥 딕셔너리 자료형에 리스트를 넣어 쉽게 인접 리스트처럼 구현하여 사용할 수 있다. BFS BFS는 너비.. [파이썬 | 자료구조] 8. 힙(Heap) 8. 힙(Heap) 8.1 힙의 개념 힙 역시 트리 구조를 가진 자료구조의 형태이다. 힙은 BST와 비슷하면서 다른 특징을 가지고 있다. root의 값은 항상 최대/최소 이다. 트리는 항상 완전이진트리이다. 어떤 서브 트리 역시 힙의 특성을 그대로 가진다. BST는 모든 원소들이 Inorder로 탐색했을시 정렬되어서 표현된다. 즉 모든 자료들이 정렬되어 있는 형태로, 탐색에 유리하다. 하지만 힙은 root의 값이 최대/최소임은 보장하지만 다른 원소들은 정렬되어 있지 않다. 따라서 BST에 비해 탐색에는 불리한 구조이다. 하지만 모든 삽입과 삭제가 맨 마지막에서 일어나므로 삽입, 삭제 연산에 있어서 장점이 있으며 부모와 자식간의 간선 정보를 수식으로 나타낼 수 있으므로, node를 사용한 연결리스트가 아닌.. [파이썬 | 자료구조] 7. 트리(Tree) 7. 트리(Tree) 7.1 트리의 개념 트리는 앞서 봤던 자료구조와는 달리 비선형 자료구조이다. 데이터를 어떻게 삽입하고 삭제, 검색할 것인지에 대한 관심보다는 데이터를 어떻게 표현하는지에 더 중점을 둔 자료구조이다. 트리는 노드와 노드들을 연결하는 간선으로 이루어져 있다. 7.2 트리 용어 루트 노드(root node) : 부모가 없는 노드. 트리는 하나의 루트 노드만을 가진다. 단말 노드(leaf node) : 자식이 없는 노드이다. 간선(edge) : 노드를 연결하는 선 형제(sibling) : 같은 부모를 가지는 노드. 노드의 크기 : 자신을 포함한 모든 자손 노드의 개수 차수 노드의 깊이 : 루트에서 노드까지 간선의 개수 (B : 1, K : 3) 노드의 레벨 : 루트에서부터 지하로 층수 (A.. [파이썬 | 자료구조] 6. 해시 테이블(Hash Table) 해시 구조란? Key와 Value 두 쌍으로 이루어진 데이터이다. Key를 이용해서 Value를 찾는다. (최선 : O(1) 최악 : O(N)) 파이썬에서는 기본적으로 제공되는 딕셔너리 자료형이 해시 테이블과 같은 구조이다. 검색, 저장, 삭제가 잦은 경우 사용하면 속도가 빠르다. 하지만 저장공간이 더 많이 필요하며(넉넉하게 필요하며), 해시 값이 같은 경우 충돌을 해결하는 알고리즘이 필요하고, 최악의 경우 시간복잡도가 O(N)으로 증가하게 된다. 어떤 Key값에 대해서 숫자(주소값)로 바꿔주는 함수를 해시 함수라고 한다. 해시 테이블이란 해시 함수로 접근하는 데이터 구조를 뜻한다. 파이썬에서는 특정 문자열을 숫자값으로 바꿔주는 hash()함수가 있는데 파이썬3 부터 보안을 이유로 프로그램을 실행할 때마.. [파이썬 | 자료구조] 5. 연결 리스트(Linked List) 5. 연결 리스트(Linked List) Python에서 사용하는 List의 기본적인 구조는 Linked List이다 다른 C나 Java의 경우 기초 프로그래밍을 할 때 배열을 이용하게 되지만 파이썬에서는 배열이 없는 이유가 Linked List를 기본적으로 지원하기 때문이다 연결 리스트라고 하는 Linked List는 배열과 달리 내부 메모리 주소적으로 봤을때 연속된 주소가 아니라, 서로 떨어진 데이터를 주소를 연결하여 관리하는 데이터 구조이다. 따라서 미리 데이터 공간을 할당할 필요가 없다는 장점이 있지만 데이터 검색효율이 안좋으며, 데이터 삭제시 양쪽의 node를 이어주는 등의 구현에서 불편함 등의 단점이 있다. Single Linked List Double LInked List Single Lin.. [파이썬 | 자료구조] 4. 스택(Stack) 4. 스택(Stack) 후입선출, LIFO(Last In, First Out) 방식을 사용하는 데이터 구조 함수를 재귀호출 할 때 스택의 구조로 함수 호출 순서가 결정된다고 생각하면 된다. 나중에 넣은 데이터를 먼저 꺼내게 된다. 프링글스 통을 생각하면 된다. 스택의 Push와 Pop은 모두 파이썬 리스트의 append와 pop으로 대체할 수 있다. [파이썬 | 자료구조] 3. 큐(Queue) 3. 큐(Queue) 선입선출, FIFO(First In, First Out) 방식을 사용하는 데이터 구조 먼저 넣은 데이터를 먼저 꺼내게 된다. 양방향 터널을 생각하면 된다. Python에는 Queue 라이브러리를 제공한다. 하지만 Queue의 대부분의 기능은 기본 List로 구현할 수 있다. 알고리즘 문제를 풀때는 Queue나 Stack의 기능을 deque 라이브러리로 사용하는것이 제일 빠르다. Python 기본 queue 라이브러리 사용 collections 라이브러리의 deque 사용하여 구현 deque 대신 기본 list를 사용해도 무방하지만 deque.popleft()는 O(1)이지만, list.pop(0)는 O(N)으로 시간복잡도 차이가 발생한다. Priority Queue의 구현 일반적인 .. [파이썬 | 자료구조] 2. 배열(Array) 2. 배열(Array) C, Java에서의 배열은 처음 선언시 데이터의 크기를 지정하여 선언한다. Python에서 배열은 list로 구현되어 있어 데이터의 크기와 상관없이 선언할 수 있다는 장점이 있다.\ 배열은 index를 통해 직접 접근이 가능하다 장점 빠른 접근이 가능하다 단점 데이터의 추가와 삭제에 비용이 많이 사용된다. 선언된 크기를 초과하여 데이터를 추가하거나, 데이터를 삭제시 빈공간 관리가 어렵다. 이전 1 2 다음
