자료구조와 알고리즘 ft. 수업/알고리즘 정리
3. 이진 탐색 트리
이진 탐색 트리 이진 탐색 트리(binary search tree) : 이진 트리 기반의 탐색을 위한 자료 구조 탐색(search) : 레코드(record)의 집합에서 특정한 레코드를 찾아내는 작업을 의미 레코드(record) : 하나 이상의 필드(field)로 구성 테이블(table) : 레코드(record)들의 집합 주요 키(primary key) : 각각의 레코드를 구별할 수 있는 키 탐색 작업을 할 때 주요 키가 입력이 되어 특정한 키를 가진 레코드를 찾게 됨 이진 탐색 트리는 이러한 탐색 작업을 효율적으로 하기 위한 자료구조 - 이진 탐색 트리의 정의 이진 탐색 트리: 이진 탐색 트리의 성질을 만족하는 이진 트리 이진 탐색 트리 - 모든 노드 키는 유일함 - 왼쪽 서브 트리의 키들은 루트의 키보..
5. 덱의 응용 : 미로 탐색 프로그램 ft. C++
깊이 우선 탐색과 너비 우선 탐색 스택을 사용하는 것 : 깊이 우선 탐색 (DFS. Depth First Search) 전략 => 최대한 갈 수 있는데 까지 가보고 막히면 다시 다른 길을 찾는 방식 이웃의 탐색 순서는 그림과 같이 상-하-좌-우 순으로 진행 현재 위치에서 생쥐는 항상 상-하-좌-우를 검사하여 갈 수 있는 위치이면 스택에 저장 다음으로 스택에서 꺼내지는 것은 항상 가장 최근에 저장된 위치 그림은 생쥐가 깊이우선으로 탐색하는 순서를 표시하고 스택의 변화를 보여주고 있음 큐를 사용하는 것 : 너비 우선 탐색 (BFS, Breadth First Search) 전략 => 탐색 순서에서 깊이보다는 폭을 우선으로 취함 이 방법에서도 마찬가지로 생쥐는 현재 위치에서 상-하-좌-우 순서로 인접 위치를 검..
Array (배열)
1. 배열 - 배열의 개념 배열(array)은 거의 모든 프로그래밍 언어에서 기본적으로 제공되는 자료형 배열은 기본이 되는 중요한 자료형으로서 많은 자료 구조들이 배열을 사용하여 구현 배열은 동일한 타입의 데이터를 한 번에 여러 개 만들 때 사용됨 배열이 지원되지 않으면 int list1, list2, list3, list4, list5, list6; 그러나 배열이 지원된다면? int list[6]; 대량의 데이터를 저장하기 위하여 여러 개의 개별 변수를 사용하는 것은 "인접한 요소를 교환하라"와 같은 연산을 할 때, 매번 다른 이름으로 접근을 해야 하므로 많은 불편이 따를 수 있다. 하지만 배열을 사용하면 "연속적인 메모리 공간"이 할당되고 인덱스 (index) 번호를 사용하여 쉽게 접근이 가능하기 때..
array, search, insert, delete
Reference : - 건국대학교 컴퓨터공학과 자료구조 수업 / 김성렬 교수님 Search, Insert, Delete 자료구조의 가장 중요한 연산들 책상 위를 보시오! (우리가 평소에도 많이 하는 작업들 공책에 쓰고 지우고...) 그렇다고 모든 자료 구조에 해당하는 것은 아니다. 예) 그래프 Item: 저장되는 대상을 부를 이름 정수만 가능한 것으로 생각을 하자. 임의의 배열을 통해서 알아보자. Array 임의의 배열 형태 임의의 배열의 형태를 생각해보자 배열은 index와 value로 구성되어있다. 그렇다면 위 배열을 토대로 배열 안에서 삽입, 삭제, 검색이 어떻게 이루어지는지 알아보자 How to Store Items in an Array? Packed vs Unpacked (빈자리가 있냐? 없냐..
2. 이진 트리
2. 이진 트리의 소개 - 이진 트리의 정의 이진 트리 (binary tree) : 이진트리의 서브 트리들은 모두 이진트리여야 함 => 트리 중에서 가장 많이 쓰이는 트리 이진 트리의 정의 공집합이거나 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의 이진 트리와 일반 트리의 차이점 이진 트리의 모든 노드는 차수가 2이하, 즉 자식 노드의 개수가 2이하지만 일반 트리는 자식 노드의 개수에 제한이 x 일반 트리와는 달리 이진 트리는 노드를 하나도 갖지 않을 수도 있다 서브 트리간에 순서가 존재한다 (왼쪽 서브트리와 오른쪽 서브트리를 구별) - 이진 트리의 성질 n개의 노드를 가진 이진트리는 정확하게 n-1의 간선을 가짐 => 이진트리에서의 노드는 루트를 제외하면 정확하게 하나..