자료구조5 [자료구조] DFS와 BFS DFS 와 BFS란?DFS (Depth-First Search)와 BFS (Breadth-First Search)는 그래프 탐색 알고리즘그래프의 모든 노드를 탐색하는 방법임두 알고리즘은 탐색의 순서와 방식에서 차이 있음시간복잡도는 DFS/ BFS 동일함-> 왜냐? 모든 조건 내 모든 노드를 검색하니까--> But, 최단거리 구할 때는 BFS가 유리함 1. DFS (Depth-First Search)- 개념: DFS는 깊이 우선 탐색한 노드에서 시작하여 다음 분기로 넘어가기 전에!!해당 분기를 따라 최대한 깊이 내려가며 탐색하는 방법 - 특징: 스택 (Stack) 사용재귀 호출을 사용할 수 있음한 경로를 끝까지 탐색한 후, 다른 경로를 탐색 2. BFS (Breadth-First Search)- 개념:BF.. 2024. 8. 2. [자료구조] Double Linked List (C++) 오늘 아침에 새로운 스터디에서 다시 더블링크드리스트를 공부했다.이전과 다르게 private member로 Tail을 추가했다.공부한 날 다시 짜서일까? 1시간 반 정도만에 완성했다. /*1023 더블링크드리스트*/#include using namespace std;typedef struct Node{ int Data; Node* PrevNode; Node* NextNode; Node(int NewData) : Data(NewData), PrevNode(nullptr), NextNode(nullptr) {};};class DoubleLinkedList{public: DoubleLinkedList() : Head(nullptr), Tail(nullptr), Count(0) {}; ~DoubleLinkedLi.. 2023. 10. 23. [자료구조] Single Linked List (C++) 자료구조 스터디를 옆자리 짝꿍과 다시 시작했다.매주 1개씩 구현해보기로 했다.오랜만에 다시 짜니까 2시간 정도 걸렸다. 아래는 C++로 구현한 싱글링크드리스트!private member로 Head와 Count변수를 썼다.노드 추가 시 Count++,노드 제거 시 Count--해서 노드 수를 카운트 해줬다./*23-10-15 다시 짜본 싱글링크드리스트*/#include using namespace std;typedef struct Node{ int Data; Node* NextNode; Node(int NewData) : Data(NewData), NextNode(nullptr) {};};class SingleLinkedList{public: SingleLinkedList() : Head(nullptr).. 2023. 10. 15. [자료구조] Stack 구현 (C++) 금요일에 짰던 초밥 스택을 Push랑 Pop하는 걸 복습할 겸 아래와 같이 다시 새로 짜보았다.감자초밥에서 초밥 한 접시 주문해보세요 :) #include using namespace std;struct SushiSt { string name = "초밥이름"; int price = 1004;};// 내가 구매한 접시 푸쉬하고 팝하려고 만든 클래스임class Stack { enum { MAX_ARRAY_SIZE = 10 };public: Stack() : m_top(0) { } // m_top을 0으로 초기화 해줌 void Push(string name, int price) { m_sushiAry[m_top].name = name; m_sushiAry[m_top++].price = price; } v.. 2023. 3. 19. [자료구조] Stack 개념 정리 어제 학원에서 스택을 배웠다. 스택이란 자료구조가 따로 있는 게 아니고, 배열이나 링크드리스트로 스택처럼 구현하는 거다. 스택은 Last In First Out나중에 들어간게 먼저 나오는 애인데,예를 들자면 초밥집 접시 쌓을 때 순차적으로 쌓쥬? 마지막으로 쌓은 접시를 가장 먼저 빼는 그 개념 배열은 할당된 메모리에 데이터를 저장하기 때문에 어디에 저장할지 기억하는 변수가 필요함 (Top = 0)왜냐? 몇 번째 방에 저장할 지를 알아야 하니까배열의 최대 크기== TOP의 크기라면 그게 오버플로우임#include using namespace std;class Stack {public: // 집어 넣는 함수 void Push(int num) { ary[top++] = num; } // 빼는 함수.. 2023. 3. 18. 이전 1 다음
