본문 바로가기

coding/Data Structure(C)

[C] 그래프와 DFS, BFS 구현
coding/Data Structure(C) 2020. 12. 14. [C] 그래프와 DFS, BFS 구현 그래프(Graph)에 대해 알아보자. 그래프는 객체 사이의 연결 관계를 표현할 수 있는 자료구조이다. 가장 쉬운 예로는 지하철 노선도가 있겠다. 서울시 지하철 노선도이다. 역과 역 사이는 철로로 연결되어 있고, 노선도에 거리는 나와있지 않지만 대충 길이를 보고 종착지로의 최단 경로도 파악할 수 있다. 연결 상태를 파악할 수 있는 자료구조이기 때문에 다음과 같은 필드에 응용할 수 있다: 전기회로의 연결 상태 운영 체제에서 프로세스와 자원들의 연관 관계 미로 과목 간의 연관관계(선수과목 파악) 그래프는 정점과 간선들의 유한 집합이라고 할 수 있다. 해당 그래프의 이름을 G1이라고 한다면, V(G1) = { a, b, c, d, e, f } E(G1) = { (a, b), (a, c), (a, f), (b, ..
[C] 힙과 우선순위 큐
coding/Data Structure(C) 2020. 12. 13. [C] 힙과 우선순위 큐 힙(Heap)과 우선순위 큐(Priority Queue)에 대해 알아보자. 1. 힙 (Heap) 여기서 배우는 힙은 메모리상의 힙이 아니다!!! 자료구조의 첫장 안에 코드, 데이터, 스택, 힙 영역이 있다는 건 배웠을 것이다. 하지만 이 힙은 힙 정렬을 배우기 위한 자료구조 구현 방법이다. 밑에 우선순위 큐를 구현하기 위해 힙을 이용한다. 힙이란 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다. 예를 들어, 가장 큰 값을 빠르게 찾기 위해선 다음과 같은 최대 힙 트리를 만드는 게 좋다. 잘 보면 우리가 지금까지 배워오던 이진트리와는 아주 다르다. 이진트리는 루트노드를 기준으로 작은 값은 왼쪽 서브트리에, 큰 값은 오른쪽 서브트리에 배정된 형태이다. 최대 힙 ..
[C] AVL트리
coding/Data Structure(C) 2020. 12. 13. [C] AVL트리 AVL트리에 대해 알아보자. 이전 포스트에서, BST 순회와 연산의 시간복잡도를 줄이기 위해 균형잡힌 이진트리를 만든다고 했었다. 그 중 한 방법이 AVL트리이다. AVL트리는 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 1이하이다. 그리고 노드가 삽입되는 과정에서 스스로 노드들을 재배치해서 균형 상태를 유지한다. 균형 인수 = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이 'AVL트리이다'는 말은 모든 노드의 균형 인수가 다음을 충족시킬 때를 일컫는다. -1 RR회전) 그림으로 보자. 노드 1을 삽입했다. 3보다 작기 때문에 3의 왼쪽자식으로 배정. 하지만 노드 5와 7의 균형인수가 2를 넘어버렸다! 이럴때는 노드 1과 가장 가까우면서 균형이 깨진 조상노드를 찾아야 하는데, 노드 5이다. 노..
[C] 이진탐색트리(BST; Binary Search Tree)
coding/Data Structure(C) 2020. 12. 13. [C] 이진탐색트리(BST; Binary Search Tree) 이진탐색트리를 구현해보자. 이진탐색트리는 이진트리 기반의 탐색을 위한 자료구조이다. 효율적인 탐색을 위해 inorder traversal(중위순회) 방법을 씀. 이러면 자료가 오름차순으로 정렬되어서 시간복잡도를 줄일 수 있다고 한다. 최선의 경우 최악의 경우 이진트리가 균형적으로 생성되어 있는 경우 : h=log(n) 경사 이진트리(일렬로 쭉 늘어선 트리) : h=n 시간복잡도: O(log(n)) 시간복잡도: O(n) [C]트리와 이진트리 포스트에서 이진트리의 성질 부분을 다시 복습하자. n개의 노드를 가진 이진트리의 높이는 최대 n이거나 최소 [log(n+1)]이 된다. 왜 log(n+1)에서 log(n)이 됐는지는 모르겠지만..? 아마 Big-O 기법이 뭉뚱그려서 최고순위 차수만 고려해서(?) 그런가..
[C] 이진트리의 순회
coding/Data Structure(C) 2020. 12. 12. [C] 이진트리의 순회 연결리스트로 이진트리를 구현해보자. 트리도 마찬가지로 배열 혹은 연결리스트로 구현할 수 있다. 배열로는 안해봤다. 기억공간의 낭비가 심해진다고 한다(? 무슨소리냐...). 그래서 연결리스트로 구현했다. 하나의 링크에는 총 3개의 필드가 있다. 가운데에 데이터필드, 왼쪽과 오른쪽에 각각의 자식노드를 가리키는 2개의 포인터필드이다. 그림을 보면 더 쉽게 이해할 수 있음. 1 2 3 4 5 typedef struct TreeNode { int data; struct TreeNode* left, * right; }Node; Colored by Color Scripter cs 이렇게 데이터필드와 왼쪽, 오른쪽의 포인터필드를 만들어주면 된다. (1) 이진트리의 순회 개념정리 이전에 배웠던 선형 자료구조에서, 연산을..
[C] 트리와 이진트리
coding/Data Structure(C) 2020. 12. 12. [C] 트리와 이진트리 트리(Tree)와 이진트리(Binary Tree)에 대해 알아보자. (1) 트리 트리는 계층적인 구조를 나타내는 자료구조이다. 지금까지 배웠던 스택, 큐, 리스트는 모두 선형 자료구조이지만, 트리는 비선형 자료구조 중 하나이다. 트리의 응용분야에는 회사의 조직도, 컴퓨터의 폴더 구조, 인공지능에서의 결정 트리(decision tree) 등이 있다. 차수(degree): 노드의 자식 노드 수 레벨(level): 트리의 각 층의 번호 높이(height): 트리의 최대 레벨 예를 들면, 루트노드인 P의 차수는 2이고(자식이 Q, R 2개이므로), A의 레벨은 3이다. 레벨을 구할 때 루트=1인 것을 잊지말자. 이 트리의 높이는 5이다. 트리도 데이터필드와 링크필드로 나누어서 메모리상에 구현할 수 있는데, 링크..
[C] 큐와 연결리스트
coding/Data Structure(C) 2020. 12. 12. [C] 큐와 연결리스트 단순 연결리스트(simply linked list)로 큐를 구현해보자. 스택과 마찬가지로 큐도 연결리스트로 구현 가능하다. 단순 연결리스트에 2개의 포인터를 추가한 것과 같은데, front로 삭제하고 rear로 삽입한다. FIFO이기 때문에 먼저 들어온 요소가 먼저 삭제된다. 나머지는 [C]스택과 연결리스트에 정의되어 있는 함수들과 같고, 삽입은 enqueue 삭제는 dequeue가 해준다. 마찬가지로 전역변수를 쓸 때와 쓰지 않을 때로 나누어보았다. (1) 전역변수 사용 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47..
[C] 스택과 연결리스트
coding/Data Structure(C) 2020. 12. 12. [C] 스택과 연결리스트 단순 연결리스트(simply linked list)로 스택을 구현해보자. 리스트뿐만 아니라 스택과 큐도 연결리스트로 구현할 수 있다. 똑같이 구조체로 노드를 정의하고 시작하면 된다. 일단 스택은 top이 head가 된다. 위에서부터 삽입하고 삭제하는거 잊지말기~ 이것도 두 가지 방법이 있는데 전역변수를 사용할 것인지 말것인지에 따라 나눠보았다. 왜 전역변수의 유무에 집착하냐고 물어보고 싶으면 저 말고 제 교수님께 여쭤보세요. 사용한 함수들은 다음과 같음: init(): top을 초기화한다. is_empty(): 스택이 비었는지 확인한다. push(value): 요소를 삽입한다. pop(): top을 삭제한다. (스택은 LIFO이기 때문에 무조건 맨 위의 요소를 삭제한다. User Input으로 못 받아옴..

티스토리툴바