자료구조

그래프(Graph)란? 연결되어 있는 객체 간의 관계를 표현하는 자료구조이다. 그래프 G는 (V, E)로 표시되며 V는 정점 또는 노드라고 불리며, 여러 가지 특성을 가질 수 있는 객체를 의미하고 E는 간선 또는 링크로 정점들 간의 관계를 의미한다. 그래프의 종류 무방향 그래프(undirected graph) 간선을 통해서 양방향으로 갈 수 있다. 방향 그래프(directed graph) 간선을 통해서 한쪽 방향으로만 갈 수 있다. 가중치 그래프(weighted graph) 간선에 비용이나 가중치가 할당된 그래프 그래프(graph)의 용어 인접 정점(adjacent vertex) :하나의 정점에서 간선에 의해 직접 연결된 정점 차수(degree) : 하나의 정점에 연결된 간선의 수 경로(path) : 간..

우선순위 큐(Priority Queue)란? 모든 데이터가 우선순위를 가지고 있고, 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 출력된다. 스택이나 큐를 우선순위 큐로 구현할 수 있으며, 응용분야로는 네트워크 트래픽 제어, os의 작업 스케쥴링 등이 있다. 우선순위 큐 구현 방법 힙(heap)이란? 완전 이진트리(complete binary tree)로 구성되며 최대 힙, 최소 힙의 두 가지 표현법이 있다. 우선순위 큐를 위해 만들어진 자료구조로 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도의 느슨한 정렬 상태를 유지한다. 힙의 목적이 삭제 연산에서 가장 큰 값을 효율적으로 찾아내기만 하면 되는 것이므로 전체를 정렬할 필요는 없다.(최대 힙을 가정할 때) 최대 힙(max heap..

이진 탐색 트리(Binary Search Tree)란? 이진트리 기반의 탐색을 위한 자료 구조로 효율적인 탐색 작업을 할 때 사용하는 자료 구조입니다. 이진 탐색 트리(Binary Search Tree)의 정의 -모든 노드는 유일한 키를 갖는다. -왼쪽 서브 트리 키들은 루트 키보다 작다. -오른쪽 서브 트리의 키들은 루트의 키보다 크다. -왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. -탐색작업을 효율적으로 하기 위한 자료구조 이진 탐색 트리(Binary Search Tree)의 탐색 그림 예시 && C언어 코드 -비교한 결과가 같으면 탐색이 성공적으로 끝난다. -키 값이 루트보다 작은면 왼쪽 자식을 기준으로 다시 탐색 -키 값이 루트보다 크면 오른쪽 자식을 기준으로 다시 탐색 이진 탐색 트리(Bin..

트리(Tree)란? 트리는 부모-자식 관계의 노드들로 이루어져있으며, 계층적인 구조를 나타내는 자료구조입니다. 응용분야로는 회사의 조직도, 컴퓨터의 폴더 구조 ,인공지능 바둑 프로그램의 거대한 결정 트리 , 등이 있습니다. 트리(Tree)의 용어 노드(node) : 트리의 구성요소 루트(root) 부모가 없는 노드(A) 서브트리(subtree) : 하나의 노드와 자손들로 이루어짐 단말노드(terminal) : 자식이 없는 노드(E,FG,H,I,J) 비단말노드 : 자식을 가지는 노드(A,B,C,D) 레벨(level) :트리의 각층의 번호 높이(height) : 트리의 최대 레벨 차수(degree) : 노드의 자식 노드수 트리(Tree)의 종류 이진트리(binary tree) 이진트리란 모든 노드가 2개의 ..

단순 연결 리스트(singly linked list) -하나의 링크 필드를 이용하여 연결 -마지막 노드의 링크 값은 NULL 연결 리스트로 구현한 리스트 (삽입, 삭제 연산 예시 && 코드) 연결 리스트 구조체는 int형 data와 포인터 링크로 구성되어 있으며 전역 변수로 포인터 head가 NULL값으로 설정해 놓습니다. 전역 변수를 포인터 head을 사용할 경우 삽입 삭제할 때 전 노드를 찾아야 할 경우가 있기 때문에 get_entry 함수로 따로 만들어놔야 합니다. 굳이 만들지 않고 삽입 삭제 안에서 설정해놓아도 되는데 코드 길이가 길어지기 때문에 함수를 임의로 만들어 놓았습니다. 삽입 연산에서는 prev와 new_node라는 두 개의 포인터 변수를 설정하여, new_node는 현재 삽입할 값을 가..

큐(queue)란? 큐(queue)는 스택과 다르게 먼저 들어온 데이터가 먼저 나가는 자료구조로 선입선출(FIFO : First-in First-out) 방식으로 삽입과 삭제는 FIFO 순서로 따릅니다~ 삽입은 큐(queue)의 후단에서, 삭제는 전단에서 이루어져요! 큐(queue)의 연산 -init() : 큐를 초기화한다. -enqueue(e) : 주어진 요소 e를 큐의 맨 뒤에 추가한다. -dequeue() : 큐가 비어있지 않으면 맨 앞 요소를 삭제하고 반환한다. -is_empty() : 큐가 비어있으면 true를 아니면 false를 반환한다. -peek() : 큐가 비어있지 않으면 맨 앞 요소를 삭제하지 않고 반환한다. -is_full() : 큐가 가득 차 있으면 true을 아니면 false을 반..

후위(postfix) 표기법 - 컴퓨터에서 수식 계산 순서는 중위표기식 에서 후위표기식으로 걸쳐서 계산을 한다. 예 ) 2+3*4 --> 234*+ --> 14 - 모두 스택을 사용 후위(postfix) 표기법의 장점 -괄호를 사용하지 않고도 계산 순서를 알 수 있다. -연산자의 우선순위를 고려할 필요가 없다. -수식을 읽으면서 바로 계산할 수 있다. 후위(postfix) 표기 수식 알고리즘 예시 중위 표기 수식의 후위 표기 변환 - 피연산자를 만나면 그대로 출력을 하며 연산자를 만나면 스택에 저장했다가 스택보다 우선순위가 낮은 연산자가 나오면 그때 출력한다. -왼쪽 괄호는 우선순위가 가장 낮은 연산자로 취급하며 오른쪽 괄호가 나오면 스택에서 왼쪽 괄호위에 쌓여있는 모든 연산자를 출력한다.

괄호 검사란? 괄호의 종류로는 대중소([,]), ({,}), ((,))가 있는데 3가지 조건이 성립해야 한다. 조건 1 : 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다. 조건 2 : 동일 타입의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다. 조건 3 : 서로 다른 타입의 괄호 쌍이 서로를 교차하면 안 된다. 괄호 검사 예시 괄호 검사 알고리즘 문자열에 있는 괄호를 차례대로 조사하면서 왼쪽 괄호를 만나면 스택에 push() 오른쪽 괄호를 만나면 pop() 연산으로 스택의 top에 있는 괄호를 꺼냄 - 꺼낼 수 있는 요소가 없으면 즉, 스택이 비어 있으면 조건 2에 위배 - pop 한 왼쪽 괄호와 짝이 맞지 않으면 조건 3에 위배 마지막 괄호까지를 조사한 후에도 스택에 괄호가 남아 있으면..