자료구조 키워드 정리
** 자료구조 수업 내용 정리입니다.
** 생능출판의 C언어로 쉽게 풀어쓴 자료구조 교재 내용을 참고하였습니다.
자료구조와 알고리즘
- 자료구조
- 자료들을 정리하여 보관하는 구조
- 알고리즘
- 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것
- 입력은 0개 이상, 출력은 1개 이상 존재하여야 하고, 명백성, 유한성, 유효성(실행가능성)을 가진다.
- 추상 자료형(ADT)
- 실제적인 구현으로부터 분리되어 정의된 자료형
- 사용자들이 어떻게 구현되는지 몰라도 사용 가능
- 알고리즘의 성능 분석
- 시간복잡도: 알고리즘의 수행시간 분석
- 공간복잡도: 알고리즘이 사용하는 기억공간 분석
- 빅오 표기법: n의 값에 따른 함수의 상한값을 나타내는 방법
- 최선, 평균, 최악의 경우
순환
- 순환(recursion): 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법
- 반복(iteration): 반복구조로 되풀이 하는 방법
배열, 구조체, 포인터
- 배열(array)
- 동일한 타입의 데이터를 한 번에 여러 개 만들 때 사용
- <인덱스, 값>의 쌍으로 이루어진 집합
- 구조체(structure)
- 타입이 다른 데이터를 묶을 때 사용
- 구조체 간 식별자(구조체 태그)로 구분하고, 구조체 안에 들어있는 멤버는 구조체 변수 뒤에 멤버연산자(.)와 항목 이름을 적어서 사용
- 포인터(pointer)
- 다른 변수의 주소를 가지고 있는 변수
-
int a = 100; // 정수형 변수 int *p; // int형 변수를 가리키는 포인터 p = &a; // 변수의 주소를 포인터에 저장 *p = 200; // 변수a에 200저장
- 동적 메모리 할당
- 필요한 만큼의 메모리를 운영체제로부터 할당받아서 사용하고, 사용이 끝나면 반납
-
int *p; p = (int *)malloc(sizeof(int)); //동적 메모리 할당 *p = 1000; // 동적 메모리 사용 free(p); // 동적 메모리 반납
스택
- 스택(stack): 후입선출(LIFO: Last-In First-Out)형 자료구조
- 스택의 응용 - 연산 표기법
- 중위 표기법: 2+3*4
- 전위 표기법: +2*34
- 후위 표기법: 234*+
큐
- 큐(queue): 선입선출(FIFO: First-In First-Out)형 자료구조
- 선형큐: 일차원 배열을 이용한 큐
- 원형큐: 선형큐에서 배열의 처음과 끝을 연결시킨 큐
- 덱(deque): 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 큐
연결 리스트
- 리스트(list): 항목이 차례대로 정리된 자료구조. 삽입, 삭제, 탐색이 가능
- 연결 리스트
- 포인터를 사용하여 데이터를 연결한 리스트
- 동적으로 크기가 변할 수 있고 삭제나 삽입 시에 데이터 이동을 하지 않음
- 원형 연결 리스트
- 마지막 노드의 링크필드가 첫 번째 노드 주소가 되는 리스트
- 하나의 노드에서 모든 노드로 접근 가능
- 이중 연결 리스트
- 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트
트리
- 트리 용어
- 루트 노드: 계층 구조에서 가장 높은 곳에 있는 노드
- 서브 트리: 루트 노드를 제외한 나머지 노드
- 레벨: 트리의 각 층에 번호를 매기는 것
- 부모 노드: 노드 상위에 연결된 노드
- 형제 노드: 부모노드가 같은 노드
- 자손 노드: 노드 하위에 연결된 노드
- 조상 노드: 루트 노드에서 임의의 노드까지 경로를 이루고 있는 노드
- 후손 노드: 임의의 노드 하위에 연결된 모든 노드
- 이진 트리
- 정의: 공집합이거나, 루트와 왼쪽 서브 트리, 오른쪽 서브트리로 구성된 노드들의 유한 집합
- 포화 이진트리(full binary tree): 트리의 각 레벨에 노드가 꽉 차있는 이진트리
- 완전 이진트리(complete binary tree): 마지막 레벨 전까지의 모든 노드가 채워져있고, 마지막 레벨에서 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리
- 이진 트리 순회방법
- 전위 순회(preorder traversal): VLR - 루트, 왼쪽 서브트리, 오른쪽 서브트리 순서로 방문
- 중위 순회(indorder traversal): LVR - 왼쪽 서브트리, 루트, 오른쪽 서브트리 순서로 방문
- 후위 순회(postorder traversal): LRV - 왼쪽 서브트리, 오른쪽 서브트리, 루트 순서로 방문
- 레벨 순회(level order): 각 노드를 레벨 순으로 검사하는 순회 방법
- 이진 탐색 트리
- 이진 트리 기반의 탐색을 위한 자료구조.
- 모든 원소의 키는 유일한 키를 가진다.
- 왼쪽 서브트리 키들은 루트 키보다 작고, 오른쪽 서브트리 키들은 루트 키보다 크다.
- 삭제하려는 노드가 두개의 서브트리를 가지는 경우 왼쪽 서브트리에서 가장 큰 값 또는 오른쪽 서브트리에서 가장 작은 값을 가져온다.
우선순위 큐
- 우선순위 큐: 우선 순위가 높은 데이터가 먼저 나가는 자료구조
- 힙(heap)
- 완전 이진 트리의 일종으로 우선순위 큐를 위해 특별히 만들어진 자료구조
- 느슨한 정렬 상태를 유지
- 삽입 연산: 마지막 위치에 위치 후 부모 노드와 비교하며 이동
- 삭제 연산: 루트 노드 삭제 후 마지막 노드로 대체. 자식 노드와 비교하면서 이동
- 허프만 코드: 빈도수에 따라 많이 등장하는 글자에는 짧은 비트열, 잘 나오지 않는 글자에는 긴 비트열을 사용하여 크기를 줄이는것
그래프
그래프 개념
- 그래프(graph): 객체 사이의 연결 관계를 표현할 수 있는 자료 구조
- 그래프 용어
- 정점(vertex) 또는 노드(node)
- 간선(edge) 또는 링크(link)
- 정점의 차수: 정점과 직접 연결된 정점의 수
- 그래프 종류
- 무방향 그래프: 간선을 통해 양방향으로 갈 수 있음
- 방향 그래프: 한쪽 방향으로만 갈 수 있음
- 네트워크(가중치 그래프): 간선에 가중치가 할당된 그래프
- 부분 그래프: 어떤 그래프의 정점이 일부와 간선의 일부로 이루어진 그래프
- 연결 그래프: 모든 정점쌍에 대하여 항상 경로가 존재하는 그래프
- 완전 그래프: 그래프에 속해있는 모든 정점이 서로 연결되어 있는 그래프
- 인접 행렬(adjacency matrix): 2차원 배열을 사용하여 그래프를 표현
- 인접 리스트(adjacency list): 연결 리스트를 사용하는 그래프를 표현
그래프 탐색
- 깊이 우선 탐색(DFS: depth first search)
- 그래프를 탐색하다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 탐색하는 방법
- 너비 우선 탐색(BFS: breath first search):
- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 방법
최소 비용 신장 트리
- 신장 트리(spanning tree): 그래프내의 모든 정점을 포함하는 트리
- 최소 비용 신장 트리(MST: minimum spanning tree): 사용된 간선들의 가중치 합이 최소인 신장 트리
- Kruskal의 알고리즘
- 그리디 알고리즘 사용
- 그래프의 간선들을 가중치의 오름차순으로 정렬하고, 정렬된 간선들의 리스트에서 사이클을 형성하지 않는 간선을 찾아서 현재의 최소 비용 신장 트리의 집합에 추가
- 간선을 선택할 때 사이클을 생성하는지 체크하기 위해 union-find 연산 사용
- 희소 그래프를 대상으로 할 경우 유리
- Prim의 알고리즘
- 한 정점에서 최소 간선을 선택
- distance라는 정점 개수 크기의 배열에 현재까지 알려진 신장 트리 정점 집합에서 각 정점까지의 거리 기록
- 밀집 그래프를 대상으로 할 경우 유리
최단 경로
- Dijkstra의 알고리즘
- 하나의 시작 정점으로부터 모든 다른 정점까지의 최단경로를 찾는 알고리즘
- 시간복잡도: O(n^2)
- Floyd의 알고리즘
- 그래프에 존재하는 모든 정점 사이의 최단 경로를 한 번에 모두 찾아주는 알고리즘
- 시간복잡도: O(n^3)
위상 정렬
- 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것
- 진입 차수가 0인 정점을 선택하고, 선택된 정점과 여기 부착된 모든 간선을 삭제하는 과정을 반복
정렬
- 선택 정렬(selection sort): 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동하는 작업을 반복
- 삽입 정렬(insertion sort): 정렬되어 있지 않은 부분을 정렬된 부분의 어느 위치에 삽입되어야 하는가를 판단한 후 삽입
- 버블 정렬(bubble sort): 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환
- 쉘 정렬(shell sort)
- 정렬해야할 리스트를 일정한 기준(간격)에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고 각 부분을 삽입정렬을 이용해 정렬
- 간격이 1이 될 때까지 간격을 절반으로 줄이면서 반복
- 합병 정렬(merge sort)
- 하나의 리스트를 두 개의 균등한 크기로 분할(분할) 후 부분 배열을 정렬(정복)하여 통합(결합)
- 순환호출을 이용하여 작은 크기로 분할 하여 정렬하고, 정렬된 부분 배열을 결합
- 퀵 정렬(quick sort)
- 리스트 안에 있는 요소를 피벗(pivot)으로 선택하고, 피벗보다 작은 요소들은 왼쪽으로, 큰 요소들은 오른쪽으로 옮겨서 정렬 (합병 정렬과 달리 비균등하게 분할)
- 순환호출을 이용하여 작은 크기로 분할 하여 정렬하고, 정렬된 부분 배열을 결합
- 힙 정렬(heap sort): 힙을 만들어 차례대로 삽입한 다음, 차례대로 추출
- 기수 정렬(radix sort)
- 레코드를 비교하지 않는 정렬
- 0부터 9까지의 값을 가지는 10개의 버킷을 만들어 자리수의 값에 따라 버킷에 넣고 빼는 것을 반복
탐색
- 순차 탐색(sequential search): 배열의 항목들을 처음부터 마지막까지 하나씩 검사하여 찾는 방법
- 이진 탐색(binary search): 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지 알아내어 탐색의 범위를 반으로 줄여가며 찾는 방법
- 색인 순차 탐색(indexed sequential search): 인덱스 테이블을 사용하여 탐색의 효율을 높이는 방법
- 보간 탐색(interpolation search): 탐색키가 존재할 위치를 예측하여 탐색
- 이진 탐색 트리(binary search tree): 트리-이진 탐색 트리 참조
- AVL트리
- 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 1 이하인 이진 탐색 트리
- 삽입 연산 시 균형이 깨질 때 마다 트리를 부분적으로 회전
- 2-3 트리
- 차수가 2 또는 3인 노드를 가지는 트리
- 노드에 2개의 데이터값을 저장할 수 있고, 데이터 추가 시 저장할 공간이 없는 경우 노드를 분리
- 2-3-4 트리
- 하나의 노드가 4개의 자식까지 가질 수 있도록 2-3 트리를 확장한 것
- 삽입 노드를 찾는 순회시에 4-노드를 만나면 미리 분할을 수행하여 후진 분할 방지
댓글남기기