Computer Science/Data Structure6 그래프 정점과 간선의 집합을 그래프라고 한다. 트리는 사이클이 허용되지 않는 그래프이다. 정점(vertex)와 간선(edge)의 연결관계에 있어서 방향성이 없는 그래프를 Undirected Graph, 방향성이 있는 그래프를 Directed Graph라고 한다. 또한 간선에 가중치가 있는 그래프를 가중치 그래프라고 부른다. 그래프를 구현하는 방법은 두가지가 있다. 하나는 인접행렬을 통해서 구현하는 방법, 하나는 인접리스트를 통해 구현하는 방법이 있다. 인접 행렬로 그래프를 구현할 경우에는 정점 i와 j가 연결되어있는지 확인하려면 단순히 graph[i][j]를 확인해주면 된다. 즉 O(1)의 시간동안 연결관계를 파악할 수 있다. 하지만 간선(edge)의 갯수와 관계없이 V^2의 공간 복잡도를 갖는다는 단점이 있다.. 2021. 10. 4. 해시 테이블 해시 테이블(Hash Table) 해시는 내부적으로 배열을 사용해서 데이터를 저장한다. 그래서 평균적으로 O(1)의 시간 복잡도로 검색이 가능하다. (collision때문에 평균적으로 라는 말이 붙는다.) 하지만 문제는 이 인덱스로 저장되는 키(key)값이 불규칙하다는 것이다. 그래서 특별한 알고리즘을 이용하여 저장할 테이터와 연관된 고유한 숫자를 만들어 내 이를 인덱스로 사용한다. 이 특별한 알고리즘을 해시 함수(hash function)이라고 한다. 좋은 해시 함순는 키 전체를 참조해서 해시 값을 만들어 낸다. 해시 함수를 무조건 1:1로 만드는 것보다 Collision을 최소화하는 방향으로 설계하고 발생하는 Collision에 대비해 어떻게 대응할 것인가가 중요하다. Collision이 많아질 수록.. 2021. 9. 29. 힙과 우선순위 큐 힙(Heap) 힙이란 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조라고 한다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다.(큰 값이 상위에 작은 값이 하위 레벨이 있다는 정도) =>부모 노드의 키 값이 항상 자식 노드의 키 값보다 크다. 최대힙(Max heap) vs 최소 힙(Min heap) 최대 힙은 부모 노드의 key가 자식 노드의 키보다 크거나 같은 이진 트리, 최소 힙은 부모 노드이 key가 자식 노드의 키보다 작거나 같은 이진 트리이다. 힙의 구현 힙을 저장하는 표준적인 자료구조는 배열이다. 구현을 쉽게 하기 위해 배열의 첫번째 인덱스로 1을 사용한다. 왼쪽 자식의 인덱스 = (부.. 2021. 9. 29. 트리 Tree는 스택과 큐와 달리 비선형 자료구조로, 계층적 관계를 표현하는 자료구조이다. 트리의 구성 요소 노드(Node) : 트리를 구성하고 있는 각각의 요소를 의미한다. 루트(Root) : 트리의 가장 상단에 있는 노드를 의미한다. 간선(Edge) : 노드와 노드를 연결하는 선을 의미한다. 단말 노드(Leaf Node) : 하위에 다른 노드가 연결되어 있지 않는, 즉 자식이 없는 노드를 의미한다. 트리에서는 각 층별로 숫자를 매겨서 이를 트리의 레벨이라고 한다. 레벨의 값을 0부터 시작하고, 루트 노드의 레벨은 0이다. 트리의 최고 레벨을 가리켜 해당 트리의 높이라고 한다. 트리에는 대표적으로 이진트리가 있다. 이진트리란 루트 노드를 중심으로 두개의 서브 트리로 나뉘어 지고, 나누어진 서브트리 또한 이진.. 2021. 9. 29. 큐와 스택 큐(Queue) 큐는 선형 자료구조의 일종으로 First In First Out(FIFO)의 성질을 가지고 있다. 먼저 들어간 원소가 가장 먼저 나오게 되는 구조이다. 큐가 사용되는 예로는 은행 번호표 시스템, OS의 스케줄링, 리그오브레전드 매칭큐 시스템 등이 있다. 스택(Stack) 스택도 선형 자료구조의 일종으로 Last In First Out(LIFO)의 성질을 가지고 있다. 나중에 들어간 원소가 먼저 나오게 된다. 스택의 예시로는 웹 브라우저 방문기록(뒤로가기), 실행취소(undo), 수식의 괄호 검사 등에서 사용된다. 2021. 9. 29. 배열과 연결리스트 배열(Array) 배열은 가장 기본적인 자료구조로, 논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서 인덱스(index)로 해당 원소에 접근할 수 있고, O(1)의 시간만에 해당 원소에 접근할 수 있다. 하지만 원소를 삽입, 삭제하는 경우에는 뒤의 원소들을 한칸씩 shift 해줘야하기 때문에 O(n)의 시간이 걸린다. 연결리스트(Linked List) 연결리스트는 원소 각각이 자기 자신 다음 순서가 어떤 원소인지만 기억한다. 그래서 어떤 특정 인덱스의 원소에 접근하기 위해서는 첫번째 원소부터 순차적으로 검색해야 하므로 O(n)의 시간이 걸린다. 어떤 특정 원소의 주소를 알고 있을 때 그 원소를 삭제하던가 삽입하는 시간은 O(1)의 시간이 걸리지만, 주소를 모르고 몇번째 원소인지(인덱스)만 알고 있.. 2021. 9. 29. 이전 1 다음