자료구조와 알고리즘 ft. 수업
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) 번호를 사용하여 쉽게 접근이 가능하기 때..
자료구조 강의 내용
증명은 일반적이지 않다 => 하지만 증명을 함으로써 더 잘 이해할 수 있다 => 시험 문제 증명해! 이진 탐색의 종류 : 루프 이진 탐색, 재귀 이진 탐색 recursive binary search (재귀 이진 탐색) ex1) int search(int a[], int n, int x) { int m; if (n == 0) return -1; m = n / 2; if (a[m] == x) return m; else if (a[m] > x) return search(a, m, x); else // a[m] < x return m + 1 + search(a + m + 1, n - (m + 1), x); } ex2) ex1을 간단하게 int search(int a[], int n, int x) { int m;..
array, search, insert, delete
Reference : - 건국대학교 컴퓨터공학과 자료구조 수업 / 김성렬 교수님 Search, Insert, Delete 자료구조의 가장 중요한 연산들 책상 위를 보시오! (우리가 평소에도 많이 하는 작업들 공책에 쓰고 지우고...) 그렇다고 모든 자료 구조에 해당하는 것은 아니다. 예) 그래프 Item: 저장되는 대상을 부를 이름 정수만 가능한 것으로 생각을 하자. 임의의 배열을 통해서 알아보자. Array 임의의 배열 형태 임의의 배열의 형태를 생각해보자 배열은 index와 value로 구성되어있다. 그렇다면 위 배열을 토대로 배열 안에서 삽입, 삭제, 검색이 어떻게 이루어지는지 알아보자 How to Store Items in an Array? Packed vs Unpacked (빈자리가 있냐? 없냐..