본문 바로가기
728x90
반응형

2024/05

[8] 트리 ② 트리의 구현 : ADT 2024. 5. 30. 이진트리 ADT∙ 이진트리: 각 노드가 최대 두 개의 자식을 가지는 트리이다.∙ 이진트리의 성질: 노드 수, 외부노드 수, 내부노드 수, 트리의 높이 등의 관계를 정의한다.중요 메서드▶ leftChild(v): 노드 v의 왼쪽 자식을 반환합니다.▶ rightChild(v): 노드 v의 오른쪽 자식을 반환합니다.▶ sibling(v): 노드 v의 형제를 반환합니다.이진트리 순회∙ 선위순회 (Preorder): 노드를 왼쪽 및 오른쪽 자식들보다 먼저 방문한다.∙ 후위순회 (Postorder): 노드를 왼쪽 및 오른쪽 자식들 다음에 방문한다.∙ 중위순회 (Inorder): 노드를 왼쪽 자식들 다음에, 오른쪽 자식들보다 앞서 방문한다.배열에 기초한 이진트리 알고리즘배열을 이용하여 이진트리를 구현하는 방법은 간단..
[8] 트리 ① 트리의 정의 2024. 5. 29. 트리 ADT트리의 정의• 트리는 계층적 데이터 구조로, 상위 노드에서 하위 노드로 분기되는 형태를 가진다.• 회사 조직도를 예로 들어, 대표 아래에 제조부, 연구부 등의 부서가 있고, 그 아래에는 더욱 세부적인 부서들이 있다. 트리는 조직 구성, 파일 시스템, 프로그래밍 환경 등 다양한 데이터 모델에 직접적으로 활용될 수 있으며, 특정 알고리즘을 위한 보조 데이터 구조나 다른 복잡한 데이터 구조의 부분적 요소로 간접적으로 활용될 수 있다.트리 용어트리이에 대한 알고리즘을 학습하기 전, 트리와 관련된 용어들의 설명은 아래와 같다. 트리는 리스트, 스택, 큐, 집합과 같은 1차원의 선형 데이터 구조와 달리 계층구조에 의한 2차원적 구조를 가지므로 선형에 비해 한 차원 높은 정보를 다룰 수 있는 만큼 관련 용..
[7] 큐 ⑥ 응용 : 연결리스트를 이용한 데크 구현 2024. 5. 22. [ 문제 2-데크 ] 데크는 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 자료구조다. 헤드 노드와 테일 노드가 없는 이중연결리스트를 사용하여 아래에 정의된 데크 함수들을 구현하시오. ◦ 초기 상태- 주의 : 연산 수행 도중 원소가 모두 삭제되어 데크가 비는 경우에도, 아래 초기 상태가 되어야 함.◦ 데크 연산- add_front(deque, X) : deque의 앞에 원소 X를 추가 (주 교재의와 동일).- add_rear(deque, X) : deque의 뒤에 원소 X를 추가 (주 교재의와 동일).- delete_front(deque) : deque의 앞에 있는 원소를 반환한 다음 삭제 (주 교재의pop과 동일).- delete_rear(deque) : deque의 뒤에 있는..
[7] 큐 ④ 덱(deque) 2024. 5. 22. 덱(deque)덱(deque)은 double-ended queue의 줄임말로서 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 자료 구조이다.특징1. 배열로도 구현이 가능하고, 연결 리스트로도 구현이 가능하다. 따라서 구현한 자료구조에 따라서 해당 자료구조의 특징을 갖는다.2. 데이터의 맨 앞과 맨 뒤에서만 삽입, 삭제, 접근이 필요할 때 사용하는 것이 바람직하다.장점단점데이터의 앞과 뒤에서만 삽입, 삭제, 접근이 이루어질때 굉장히 빠르게 동작한다. O(1)중간 요소를 접근하거나 중간에 삽입, 삭제가 필요한 작업이 있다면 굳이 채택할 필요가 없다. 덱의 연산시계방향으로 증가하는 함수• delete_front • add_rear • is_full• get_front반시계방향으로 감소..
[7] 큐 ⑤ 응용 : 배열로 구성된 원형 큐 ADT 구현 2024. 5. 22. [ 문제 1-큐 ] 배열로 구성된 원형 큐를 위한 삽입, 삭제 프로그램을 작성하시오.◦ 주요 전략 : 본 문제의 원형 큐에서는 포화 상태와 공백 상태를 구분하기 위해 한 자리를  비워둠. - front, rear, 배열의 초기 값은 0 - 삽입 시 rear 값을 하나 증가시킨 후 데이터를 큐에 삽입 (출력 예시 1 참고) - 삭제 시 front 값을 하나 증가시킨 후 front가 가리키는 데이터를 삭제 - front = rea r면 공백 상태로 정의하고, front가 rear보다 하나 앞에 있으면 포화 상태로 정의함  ※ 주의  주교재가 제시하는 전략에서는 front와 rear가 각각 큐의 맨 앞과 맨 뒤의 원소 위치를 직접 가리키는 방식으로 정의되어 있으나 위 전략은 front가 맨 앞 원소 위치보다 ..
[7] 큐 ③ 연결리스트 ADT 2024. 5. 20. 연결리스트에 기초한 큐단일연결리스트를 사용하여 큐를 구현할 수 있다. ☑ 삽입과 삭제가 특정위치에서만 수행되므로, 역방향링크는 불필요하다. (참고: 스택의 경우 헤더노드 불필요)☑ front 원소를 연결리스트의 첫 노드에, rear 원소를 끝 노드에 저장하고 f와 r로 각각의 노드를 가리키게 한다. • 기억장소 사용: O(n)• 큐 ADT의 각 작업: O(1)헤더 및 구조체 선언#include #include #include typedef char element;#define MAX 10typedef struct QueueNode { element data; struct QueueNode* next;} QueueNode;typedef struct { QueueNode* front; ..
728x90
반응형

티스토리툴바