□ 이론/자료구조 (4) 썸네일형 리스트형 그래프(Graph)를 표현하는 방법에 대하여 ▶그래프그래프는 정점들의 집합 V와 간선들의 집합 E로 이루어진 자료구조입니다. ▶그래프 표현 방법그래프를 표현하는 방법으로 인접 행렬과 인접 리스트가 있습니다. 정점의 개수가 N개인 그래프를 인접 행렬로 표현하려면 (N+1) x (N+1) 크기의 2차원 배열이 필요합니다. 무 방향 그래프인 경우에 1번 정점과 2번 정점이 연결되어있다면 (1,2)와 (2,1)에 모두 1을 저장해 두 정점이 연결되었음을 표현합니다. 만약 방향 그래프인 경우에 1번 정점에서 2번 정점으로 화살표가 그려져있다면 (1,2)에만 1을 저장하는 방식입니다. int adj[5][5] = {0,}; // 1번 정점과 2번 정점이 연결된 경우adj[1][2] = 1; adj[2][1] = 1; 정점의 개수가 N개인 그래프를 인접 리스트.. 해싱(Hashing)에 대하여 ▶해싱 (Hashing)해싱은 일종의 데이터 관리 기법이며, 키(key)를 해시값(Hash Value)에 매핑하는 것을 말합니다.해시함수에 의해 키가 해시값으로 변환되며, 해시함수는 인풋으로 키를 받아서 아웃풋으로 해시값을 반환하도록 구현합니다. 해시함수는 다른 두 개의 키에 대해 동일한 해시값을 반환할 수 있습니다.입력 가능한 모든 키에 대해, 키를 유일한 해시값으로 만들어줄수록 좋은 해시함수로 평가받을 수 있습니다. 키를 유일한 해시값으로 변환하는데 O(1)의 시간이 걸린다면,해당 키가 이미 존재하는지 탐색하는 연산을 O(1)의 시간에 처리할 수 있다는 뜻이 되므로 해싱은 상당히 유용하게 사용될 수 있는 기법입니다. HashFunction( key ) → Hash Value ▲ 문자열 타입의 키를 정.. 힙(Heap) ▶힙(Heap)우선순위가 가장 높은 키에 접근이 빈번한 경우 사용되는 자료구조이다. 힙은 반드시 아래의 두 가지 속성을 만족해야 한다. 1. 완전 이진트리(Complete binary tree) 형태이다. (노드들이 왼쪽부터 빠짐없이 채워져 있어야 함, 가득 차지 않아도 됨) 2. 각 노드의 값은 자신의 자식 노드들의 값보다 크거나 같다. (OR 작거나 같다.) ▶Heapifyheap 자료구조의 속성이 깨졌을 때 이를 만족시키기 위해 수행하는 연산. 위에서 아래로 혹은 아래에서 위로 수행할 수 있다. (삽입시 수행) O(logN)의 시간이 걸린다. 아래에서 위로 수행하는 경우 해당 노드의 키가 부모 노드보다 크거나 같은지(OR 작거나 같은지)를 확인하여 결과가 true인 경우 키 값을 swap하고, 위에.. 연결 리스트와 배열 (Linked list) ▶연결 리스트종류는 단일/이중/원형 연결 리스트가 있다. 데이터를 가진 노드를 포인터로 연결해 놓은 자료구조이다.연결리스트는 데이터의 추가/삭제가 O(1)의 시간에 가능하다는 장점이 있지만 (다음 노드의 주소만 변경해주면 됨)배열과는 달리 특정 위치의 데이터 찾기가 최악의 경우 O(N)의 시간이 걸린다는 단점이 있다.(가장 앞이나 뒤에 있는 노드부터 포인터를 하나씩 이동해가며 데이터를 찾아야함) ▶배열번호(인덱스)와 번호에 대응하는 데이터들로 이루어진 자료구조로, 같은 종류의 데이터들을 순차적으로 저장한 것을 말한다.특정 위치의 데이터에 접근하는 것이 O(1)의 시간에 가능하다는 장점이 있지만 (인덱스로 데이터에 바로 접근)데이터 추가/삭제가 최악의 경우 O(N)의 시간이 걸린다는 단점이 있다.(데이터를.. 이전 1 다음
