⭐ Programming/자료구조와 알고리즘
[자료구조] DFS (Depth First Search) 깊이 우선 탐색
[자료구조] DFS (Depth First Search) 깊이 우선 탐색
2022.10.28인접 리스트 version 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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #include #include #include using namespace std; // [ ][ ][ ][ ][ ][ ][ ][ ] // DFS (Depth First Search) 깊이 우선 탐색 struct Vertex { // int data; }; vector vertices; vector adjacent; vector visited; void ..
[자료구조] BIG-O 표기법, 그래프 기초
[자료구조] BIG-O 표기법, 그래프 기초
2022.10.27글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자입니다 목차 인프런 Rookiss님의 '자료구조와 알고리즘' 강의를 기반으로 정리한 필기입니다. 😎 [C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part3: 자료구조와 알고리즘 강의 들으러 가기! BIG-O 표기법 BIG-O 표기법 의의 위의 그래프와 표는 입력 N값에 따라 걸리는 시간을 나타낸다. (= 시간 복잡도) 프로그램을 돌리는데 1초가 넘어가면 아주 느려서 쓰기 힘든 정도로 봐야한다. n^2 같은 연산은 지양해야 한다. 제..
[자료구조] Queue 큐
[자료구조] Queue 큐
2022.07.11글의 요약 목차 Queue 큐 입력과 출력을 담당하는 창구가 따로 존재한다. 먼저 들어간 데이터가 먼저 나오는 자료구조이다. 대기열을 떠오리면 쉽다. 은행 대기열은 번호표를 뽑은 순서대로 창구에 간다. FIFO(First-In-First-Out) 선입선출 Enqueue & Dequeue 삽입과 제거 연산 큐의 삽입(Enqueue)연산은 끝에서 큐의 제거(Dequeue)연산은 첫부분에서 수행된다. Circular Queue 순환 큐 시작과 끝을 연결하여 효율적인 삽입/삭제가 가능하다. 큐 배열을 생성할 때 실제 용량보다 1만큼 더 크게 만들어서 Front와 Rear 사이를 비워준다. 비워준 노드를 더미 노드라고 부른다. Rear은 실제 Rear보다 1 더 큰 값을 갖는다. ' Node의 크기 x ( Cap..
[자료구조] Stack 스택
[자료구조] Stack 스택
2022.07.11글의 요약 목차 Stack 스택 스택은 데이터를 쌓아 올리는 자료구조이다. 스택에서 데이터의 입력과 출력은 오직 꼭대기에서만 이루어진다. LIFO(Last-In-First-Out) 후입선출 FILO(First-In-Last-Out) 선입후출 스택이 사용되는 예시 - 지역 변수는 스택에 할당된다. (변수 선언 후 수명주기가 끝나면 자동 제거 = 자동 메모리(= 스택)) - 자동 메모리, 대다수의 네트워크 프로토콜, 컴파일러 구문 분석기, 편집 되돌리기 기능 Array Stack 배열 기반의 스택 스택 생성 초기에 프로그래머가 설정한 용량만큼의 노드를 생성한다. 최상위 노드의 위치를 가리키는 변수를 두고 삽입/삭제를 한다. 배열 기반의 스택 3요소 용량 최상위 노드의 위치 노드 배열 Linked List S..
[자료구조] 연결 리스트
[자료구조] 연결 리스트
2022.07.10목차 연결 리스트 연결 리스트(=링크드 리스트 Linked List)는 노드를 연결해서 만든 리스트이다. 각각의 연결 리스트의 노드는 '데이터'와 '다음 노드에 대한 포인트'로 이루어진다. 연결리스트 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 #include #include using namespace std; int main() { list li; list::iterator eraseIt; // [ ] [ ] [ ] for (int i = 0; i _data; } bool operator==(const Iterator& other) { return _node == other._node; } boo..
[자료구조] 동적배열 구현 연습
[자료구조] 동적배열 구현 연습
2022.07.09Vector 자료구조 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 48 49 50 51 52 53 54 55 56 57 58 #include #include using namespace std; template class Vector { public: Vector() {} ~Vector() {} void push_back(const T& value) { // 증설 작업 // 데이터 저장 // 데이터 개수 증가 } // 메모리를 증설 void reserve(int capacity) { // capacity만큼의 메모리..
[자료구조] 동적 배열
[자료구조] 동적 배열
2022.07.03동적 배열 - vector의 size ≠ capacity - 동적 할당 정책으로 capacity는 1씩 증가하는게 아니다. - 이미 늘어난 capacity는 줄지 않고 그 상태로 남는 경우가 많다. 그래서 v.clear(); 후에도 capacity 141 값이 나온다. - 임의 접근이 불가능하다. - push_back, pop_back (O), front_back(X) - 뒤쪽에 삽입과 삭제는 가능하나 앞쪽에 삽입은 불가능하다.
[자료구조] 배열, 동적 배열, 연결 리스트
[자료구조] 배열, 동적 배열, 연결 리스트
2022.07.03배열 - 사용할 방 개수를 고정해서 계약하고 절대 변경이 불가하다. - 연속된 방으로 배정 받아 사용 - 장점: 연속된 방 - 단점: 방을 추가/축소 불가 예시) 1인 1실 이용. 3명이 예약 호텔 501호 502호 503호 504호 505호 506호 507호 508호 401호 402호 403호 404호 405호 406호 407호 408호 301호 302호 303호 304호 305호 306호 307호 308호 201호 202호 203호 204호 205호 206호 207호 208호 101호 102호 103호 104호 105호 106호 107호 108호 동적 배열 - Vector - push_back(O), front_back (X) - 사용할 방 개수를 유동적으로 계약 - 연속된 방으로 배정 받아 사용 -..
[자료구조] 선형 vs 비선형 구조
[자료구조] 선형 vs 비선형 구조
2022.07.03선형 구조 - 자료를 순차적으로 나열한 형태 - 배열(Array), 연결 리스트(Linked List), 스택/큐(Stack/Que) - 스택 프레임 깨지는 경우: Visual Studio 기준, 해당 스택의 크기가 2MB가 넘어서면 지역변수가 스택이 깨지면서 스택 오버플로우가 발생한다. - 이중 연결리스트 삽입/삭제를 물어보는 경우도 많다. 비선형 구조 - 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태 - 트리(Tree), 그래프(Graph)