👩‍💻 프로그래밍/✨ 자료구조

🟩 FIFO (First In First Out) 🟩 BFS (너비우선탐색) 에서 활용 탐색 후보 중에서 항상 가장 오래된 것을 선택 🟩 헤더 추가 🟩 주요 동작 enqueue : 삽입 dequeue : 추출 peek : 추출할 데이터의 값을 알 수 있음 🟩데이터 추가/삭제 방향이 반대 1 : 삽입 연산만 발생 (가장 위에 추가됨) 2 : 삭제 연산만 발생 🟩 중간에 있는 데이터에 접근 불가 필요한 데이터가 나올 때까지 dequeue 멤버 함수 기능 q.size() q의 사이즈(물리적인 저장 용량이 아닌 원소의 개수)를 리턴 q.empty() q의 사이즈가 0인지 아닌지를 확인 q.front() q에 가장 먼저 들어간 원소를 리턴 q.back() q에 가장 나중에 들어간 원소를 리턴 q.push(val)..

데이터를 1열로 나열 🟩 접근 어려움 흩어져서 저장되어 있기 때문에 포인터를 처음부터 순서대로 따라가야만 원하는 데이터에 접근 가능 🟩 추가, 삭제 용이 추가시 추가할 위치의 앞뒤 포인터만 변경하면 된다. 삭제도 동일 cf. 삭제시, 메모리에는 데이터가 남지만 어디에도 접근할 수 없으므로 일부러 삭제할 필요없다. 이후에 이 영역이 다시 사용될 때 덮어쓰여 재사용 가능하다. 🟩 데이터가 메모리 사이의 연속된 위치에 저장되지 않는다 데이터의 물리적인 순서와 관련없음 연결 정보의 논리적 순서를 결정한다. 🌟 head 시작점, 선형 구조에서 첫 번째 노드를 가리키는 용어 노드(node) = data + pointer 전체 리스트를 탐색하거나 데이터 추가/삭제시 기준점으로 사용한다. 🟩 계산시간 검색 O(n) 추..

데이터를 1열로 나열한 자료구조 같은 자료형, 같은 크기의 기억 공간 🌟 배열의 선두는 왜 0번인가? 더보기 배열의 인덱스는 첫 번째 요소에서 얼마나 떨어져 있는가를 통해 정한다. 첫 번째 요소는 0만큼 떨어져 있으므로 a[0]이다. 🟩 접근(검색) 용이 연속된 영역에 저장되어 메모리 주소 계산 가능 각 데이터에 바로 접근 가능 🟩 추가, 삭제가 어려움 1. 데이터 추가시 배열의 마지막에 추가로 공간 확보 2. 공간이 비므로 앞으로 하나씩 옮긴다. 3. 원하는 공간에 데이터 추가 cf. 삭제 시에는 삭제 후 빈공간에 맞춰 하나씩 매꾸기 🟩 로 구성 index : 컴퓨터 구조, 메모리 주소와 무관하게 정의된다. 🟩 원소의 메모리 공간의 물리적인 위치를 '순서'적으로 결정 배열의 순서 : 메모리 공간에서 저..

이진 트리의 노드를 순회활 때, 방문하지 않고 지나쳐 온 노드들은 스택에 저장하여 관리해야 하는 번거로움이 발생함 스레드 트리 : '스레드'라는 포인터를 추가하여 트리 순회를 편리하게 하는 것 '스레드' : 순회 방법에 따른 방문순서를 유지하는 포인터 스레드 트리 구현방법 1. 포인터 필드의 추가 : 스레드를 저장하는 포인터를 추가하는 것 -> 왼쪽 스레드 포인터, 왼쪽 자식 포인터, 데이터, 오른쪽 자식 포인터, 오른쪽 스레드 포인터 필드로 노드 구조를 정의함 오른쪽 스레드 : 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리키고 왼쪽 스레드 : 그 노드의 선행 노드를 가리킴 추가된 포인터 필드에 의한 스레드 구현 - 스택을 운영하지 않고도 쉽게 트리에 속한 모든 노드를 순회 가능 - 하지만 스레드..

모든 노드의 차수가 2 이하인 트리 수학적으로, 이진트리의 구성에 관한 이론을 정리하기 쉽고, 컴퓨터 내부에서 구현하기도 효율적임 모든 노드가 2개 이하의 자식 노드를 가지므로, 일반성을 잃지 않고 '오른쪽', '왼쪽'이라는 방향 개념을 부여 가능 오른쪽 노드, 왼쪽 노드의 개념적 접근도 있음 포화 이진 트리 이진 트리의 각 레벨에서 허용되는 최대 개수 노드를 가지는 트리 완전 이진 트리 높이가 k인 이진 트리가 '0레벨'부터 'k-2 레벨'까지 다 채우고, 마지막 'k-1 레벨'에서 왼쪽부터 오른쪽으로 노드들이 차례로 채워진 이진트리 이진트리 구현 1. 배열을 이용한 구현 - 트리가 완전 이진 트리 또는 포화 이진 트리인 경우 낭비되는 공간이 없어 효율적 트리가 깊어질수록 기억장소 낭비가 2의 거듭제곱..