자료구조 (6) 썸네일형 리스트형 [그래프] 인접 행렬과 인접 리스트 전체 정점 개수: N 젠체 간선 개수: E 1. 인접 행렬 그래프의 연결 관계를 이차원 배열로 표현하는 방법이다. graph라는 이차원 배열이 있다고 하자. 이에 인접 행렬을 다음과 같이 정의할 수 있다. 1) 가중치가 없을 때 graph[i][j]: 노드 i에서 노드 j로 가는 간선이 있다면 1, 없다면 0. 1) 가중치가 있을 때 graph[i][j]: 노드 i에서 노드 j로 가는 간선이 있다면 가중치, 없다면 INF. 장점 두 정점을 연결하는 간선을 조회할 때 시간복잡도가 O(1)이다. 단점 1. 간선 수에 상관없이 N^2크기의 이차원 배열이 필요하다. 메모리 낭비이다. 2. 모든 간선 수를 알아내기 위한 시간복잡도가 O(N^2)이다. 2. 인접 리스트 그래프의 각 정점에 인접한 정점들을 연결리스트.. [자료구조] 스택/큐 [Stack/Queue] 스택[Stack] 스택은 LIFO[Last In First Out]이다. 나중에 넣은 데이터가 먼저 반환되는 데이터 구조이다. push : 맨 위에 데이터 이미지 출처 파이썬으로 스택을 구현해보자. 큐(Queue) 큐는 FIFO[First In First Out]이다. 먼저 넣은 데이터가 먼저 반환되는 데이터 구조이다. 이미지 출처 [자료구조] 해시[Hash] 해시함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시함수는 단방향 암호화 기법으로 해시를 만든다. (단방향 암호화 기법은 암호화는 가능하지만 복호화는 불가능한 알고리즘이다.) 추가적인 개념에 대해서도 알아보자. 키[Key] : 매핑 전 데이터의 값 해싱[Hashing] : 매핑하는 과정 해시값[Hashing Value] : 매핑 후 데이터의 값 해시 테이블[Hash Table] : 해시값에 의해 직접 접극이 가능한 데이터 구조 슬롯[Slot] : 한 개의 데이터를 저장할 수 있는 공간 해시함수의 장점은 아래와 같다. 1. 접근/탐색 속도가 빠르다 2. 키에 대한 데이터의 중복확인이 쉽다. (같은 입력값에 대해서는 같은 출력값을 보장하기 때문이다.) 파이썬에서는 딕셔너리[Dic.. [자료구조] 트라이[Trie] 문자열 탐색 알고리즘에 대해 알아보자. 트라이는 입력된 문자열을 트리 형식으로 만든 자료구조이다. 트라이를 이용하면 효율적 탐색이 가능하다. 만약 최대 N개의 문자열이 주어지고, 각 문자열은 최대 M의 길이를 갖는다고 해보자. 이때 특정 문자열의 개수를 구한다면 얼마나 걸릴까? 먼저 모든 문자열을 삽입하고, 특정 문자열과 동일한 문자열을 찾아야 한다. 1. 단순한 방법 모든 문자열을 삽입하는 시간복잡도는 O(N * M)이다. 특정 문자열을 탐색하는 시간복잡도는 O(N * M)이다. 2. 트라이 이용 모든 문자열을 삽입하는 시간 복잡도는 O(N * M)이다. 특정 문자열을 탐색하는 시간복잡도는 O(M)이다. class Node(object): def __init__(self, key, data=None):.. [자료구조] 트리[Tree] 먼저, 트리 관련 용어를 알아보자. (나동빈의 '이것이 취업을 위한 코딩 테스트다'를 참고했다.) 루트 노드: 부모가 없는 최상위 노드 단말 노드: 자식이 없는 노드 크기: 트리에 포한된 모든 노드의 개수 깊이: 루트 노드부터의 거리 ( 예) 노드 F의 깊이는 0이다. 예) 노드 A번의 깊이는 2이다. ) 레벨 : 특정 깊이를 가지는 노드의 집합 높이: 깊이 중 최댓값 차수: 각 노드의 (자식 방향) 간선 개수 1. 트리 트리는 자료구조의 일종이며, 1. 사이클이 없이 2. 모든 정점이 연걸되어 있는 그래프이다. 사이클이 없는 그래프이기 때문에, 트리의 크기가 N이면 간선의 개수는 N-1개이다. 조건 1, 2만 만족하면 트리이다. 따라서 루트 노드의 존재여부는 트리 여부의 영향을 미치지 않는다. 1) 루.. [그래프/트리] 힙[Heap] 우선순위 큐란? 우선순위 개념을 큐에 도입한 자료구조이다. 데이터들은 우선순위를 가지고 있고, 순위가 높은 순부터 나간다. 스택[FILO]과 큐[FIFO]와는 다르다 우선순위 큐는 힙으로 구현이 가능하다. 힙이란? 힙은 두 가지로 설명할 수 있다. 1) 최대 힙 '부모 노드의 키 값 >= 자식 노드의 키 값'인 완전 이진 트리 2) 최소 힙 '부모 노드의 키 값 이전 1 다음
