bebeghi3356

최단 경로 찾기(BFS)- 경로 : 인접한 정점들의 수열- 단순 경로 : 경로상의 정점들의 모두다른경우- 경로의 길이 : 경로상의 간선의 개수- 정점 V에서 W까지의 최단 경로의 길이는 V를 시작 정점으로 너비 우선 탐색(BFS)을 수행해서 W를 처음 방문할 때의 단계 수 최소비용신장트리(MST): 네트워크에 있는 모든 정점들을 가장 적은 비용으로 연결하는 신장트리 ( 도로건설, 전기 회로, 통신)대표알고리즘1. kriskal 알고리즘2. Prim의 알고리즘 탐욕적인 방법ㅗㅗㅠㅠㅜㅜㅎㅎㅋㅋ

그래프 - 연결되어있는 객체간의 관계를 표현한 자료구조- 오일러 오일러 문제 : 모든 다리를 한번만 건너서 처음 출발했던 장소로 돌아오는 문제위치 : 정점(node), 다리 : 간선(edge)오일러 경로 : 정점에 연결된 간선의 개수가 짝수이면 존재용어그래프 G = (V , E) : 정점과 간선의 집합으로 구성된다- V : 정점들의 집합- E : 간선들의 집합  인접 정점 : 간선에 의해 연결된정점>> 그래프에서 두 정점 A와 B가 연결되어 간선 (A, B)가 있을 때, 두 정점 A와B 를 인접한다고 한다. 차수 : 그 정점에 인접한 정점의 개수  경로 : 간선으로 연결된 정점을 순서대로 나열한 리스트- 단순 경로 : 모두 다른 정점으로 구성된 경로- 사이클 : 단순 경로 중에서 경로의 시작 정점과 마지..

우선순위 큐: 우선순위를 가진 항목들을 저장하는 큐FIFO 순서가 아니라 우선 순위가 높은 데이터가 먼저 나가게 된다. 자료구조삭제되는 요소스택가장 최근에 들어온 데이터 (LIFO)큐 가장 먼저 들어온 데이터 (FIFO)우선순위 큐가장 우선순위가 높은 데이터 우선순위 큐도 동일하게 insert 연산, delete 연산이 가장 중요한 연산이다.두가지로 구분이 되는데 1. 최소 우선순위 큐(가장 작은값 우선) 2. 최대 우선순위 큐(가장 큰값 우선) 우선순위큐 구현방법배열 이용연결리스트를 이용히프(heap)이용비교 표: 삽입과 삭제 연산의 시간 복잡도구현 방법삽입 시간 복잡도삭제 시간 복잡도순서 없는 배열O(1)   O(n)순서 없는 연결 리스트O(1) O(n) 정렬된 배열O(n) O(n)정렬된 연결 리스트..

용어정리- 서브 트리 : 하나의 노드와 그 노드들의 자손들로 이루어진 트리- 단말 노드 : 자식이 없는 노드( leaf node)라고도 불림- 비단말 노드 : 적어도 하나의 자식을 갖는 노드- 레벨 : 트리의 각층의 번호- 높이 : 트리의 최대 레벨 h- 차수 : 노드가 가지고 있는 자식 노드의 개수 이진 트리: 모든 노드의 차수가 2 이하가 되어 구현하기에 편리하다는 장점특징1. 노드의 개수가 n개이면 간선의 개수는 n-1개2. 높이가 h인 이진트리의 경우, 최소 h개의 노드, 최대 2h-1개의 노드를 갖는다.3. n개의 노드를 가지는 이진트리의 높이는 최대 n이거나 최소 ┌log₂(n+1)​┐-> 높이가 h일 때(노드의 개수 h) 최대 2^h-1개의 노드따라서 2^h = logn(n+1) 만약 h가 ..

### **1. `llink`와 `rlink`의 역할**- **`llink` (left link)**: 현재 노드의 **이전 노드**를 가리키는 포인터.- **`rlink` (right link)**: 현재 노드의 **다음 노드**를 가리키는 포인터.---### **2. 새 노드가 삽입될 때 해야 할 작업**`add_rear` 함수에서는 새 노드 `new_node`를 **덱의 끝에 추가**합니다.  즉, 새로 추가된 노드는 이전의 `tail` 노드와 연결되어야 합니다.#### (1) 기존 `tail`과 새 노드 연결- 새 노드는 이전 노드(`tail`)을 알고 있어야 하므로, **`new_node->llink`**에 기존의 `tail`을 저장합니다.- 동시에, 기존의 `tail`도 새 노드를 알아야 하므..

덱(deque) : double-ended queue의 줄임말큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐 양쪽에서 삽입, 삭제가 모두 가능해야함 >> 이중연결리스트 사용

참고: 원형 큐에서 front와 rear 사용삽입(Enqueue): 데이터를 큐에 추가하고 rear를 갱신.삭제(Dequeue): 데이터를 큐에서 제거하고 front를 갱신.빈 상태:front == -1 && rear == -1꽉 찬 상태:(rear + 1) % MAX_QUEUE_SIZE == frontlinked list Queue1. 삽입 큐 #include #include  typedef int element; // 큐의 각 노드를 정의하는 구조체 (연결 리스트 방식)typedef struct QueueNode {    element item;    struct QueueNode* link;} QueueNode; // 큐를 정의하는 구조체typedef struct {    QueueNode* fro..

스택과 큐배열/리스트 vs 스택/큐공통점: 선형 구조 이다.차이점: 삽입과 삭제의 위치 고정 여부배열/리스트: 임의의 위치에서 삽입/삭제스택: 맨 위(top)큐:삽입: 맨 앞(front)삭제: 맨 뒤(rear)     구조체 포인터(다시 복습 >> 함수 선언할 시에 구조체에 포인터를 사용하기 위해)포인터가 어떤 변수의 주소를 담아 가리키는 변수이기 때문에 구조체 포인터도 마찬가지로 구조체의 주소를 가리키는 포인터를 구조체 포인터라고 합니다. 구조체 포인터 문법struct 구조체이름* 구조체포인터이름;// examplestruct book my_book;struct book* p_my_book;p_my_book = &my_book;배열의 경우와는 달리 구조체의 이름은 구조체를 가리키는 주소가 아닙니다.따라..