cs/CS5037 6: 자료구조-8(스택, 큐, 딕셔너리) 배열, 연결 리스트, 해시 테이블, 트라이 외에도 많은 자료 구조들이 있음 위의 자료 구조를 기반으로 해서 문제 해결에 적합한 새로운 자료 구조를 만들 수도 있음 큐 - 메모리 구조에서 살펴봤듯이 값이 아래로 쌓이는 구조 - 값을 넣고 뺄 때 ‘선입 선출’ 또는 ‘FIFO’(First In First Out)’라는 방식을 따르게 됨(가장 먼저 들어온 값이 가장 먼저 나가는 것) -> 줄을 설 때 가장 먼저 줄을 선 사람이 들어가는 것 - 배열이나 연결 리스트를 통해 구현 가능함 - 큐의 두 가지 기본 연산 enqueue(get in line): 줄에 들어가서 서는 것 dequeue(get out of line): 줄을 빠져나오는 것 스택 - 메모리 구조에서 살펴봤듯이 값이 위로 쌓이는 구조 - 값을 넣고.. 2021. 12. 11. 6: 자료구조-7(트라이:Retrieval) 트라이 : ‘트리’ 형태의 자료 구조 각각의 노드가 배열로 이루어져 있음 - 트라이에는 많은 메모리가 들지만 자료 구조 안에 있는 이름이나 단어를 찾는 데 일정한 시간을 가짐 - 맨 위에 있는 배열은 트라이의 루트 - 예를 들어 영어 알파벳으로 이루어진 문자열 값을 저장한다고 한다면 이 노드는 a부터 z까지의 값을 가지는 배열이 됨 그리고 배열의 각 요소, 즉 알파벳은 다음 층의 노드(a-z 배열)를 가리킴 - 그림과 같이 Hermione, Harry, Hagrid 세 문자열을 트라이에 저장해 보면 루트 노드를 시작으로 각 화살표가 가리키는 알파벳을 따라가면서 노드를 이어주면 됨 - 단순히 문자열의 각 문자를 보며 트리를 탐색해 나가기만 하면 되어서 위와 같은 트라이에서 값을 검색하는데 걸리는 시간은 ‘.. 2021. 12. 11. 6: 자료구조-6(해시 테이블) 해시 테이블: “연결 리스트의 배열” 해시 테이블에서는 단어나 이름 같은 입력값이 들어온다면 그 단어에 포함된 문자를 보고 어디에 그 이름을 넣을지 결정하는 방식이 흔하게 사용됨 - 이름이 해시 테이블에 저장되며, 알파벳 개수에 해당하는 총 26개의 포인터들이 있을 수 있으며, 해시 함수는 ‘이름의 가장 첫 글자’인 경우, 각 포인터는 그 알파벳을 시작으로 하는 이름들을 저장하는 연결 리스트를 가리키게 됨 - 해시 테이블 -> 세로: 배열 / 가로: 연결 리스트 - 충돌: 어떤 값을 넣으려고 하는데 이미 무언가 들어가 있는 경우. / 최대한 충돌을 피해야 함! 인덱싱을 하는데 사용하는 배열 -> 해시 함수 Albus를 해시함수에 넣으면 0이 반환되어서 0번째 배열 즉 A에 해당하게 됨 Harry를 해시함.. 2021. 12. 11. 6: 자료구조-5(연결 리스트: 트리) 트리 : 연결 리스트를 기반으로 한 새로운 데이터 구조 - 연결 리스트에서의 요소들의 연결은 1차원적으로 구성되어 있고, 트리에서의 노드들의 연결은 2차원적으로 구성되어 있음 - 각 노드는 일정한 층에 속하고, 다음 층의 노드들을 가리키는 포인터를 가지게 됨 - 가장 높은 층에서 트리가 시작되는 노드 ‘루트’ - 루트 노드는 다음 층의 노드들을 가리키고 있고, 이를 ‘자식 노드’라고 함 - 트리의 노드들은 최대 두 개의 자식 노드를 가짐. 이진법의 이진을 따와서 최대 2라는 것을 표현 - 왼쪽 자식 노드는 자신의 값보다 작고, 오른쪽 자식 노드는 자신의 값보다 큼 이런 트리 구조는 이진 검색을 수행하는 데 유리함 - 트리를 탐색하려면 트리의 가장 위에 있는 루트라는 노드만 알려주면 트리의 모든 곳으로 갈.. 2021. 12. 11. 6: 자료구조-4(연결 리스트: 코딩과 시연) 연결리스트의 코드를 나눠서 보기 1. 연결 리스트의 기본 단위가 되는 node 구조체를 정의 typedef struct node { //node 안에서 정수형 값이 저장되는 변수를 number로 지정 int number; //다음 node의 주소를 가리키는 포인터를 *next로 지정 struct node *next; } node; 2. list라는 변수 생성하고 그곳에 node의 주소(포인터)가 들어감 int main(void) { // List of size 0 -> 연결리스트를 아무것도 없는 상태로 초기화(NULL) // 연결 리스트의 첫 번째 node 가리킴 // list라는 빈박스를 NULL로 표현(아무것도 들어가 있지 않아서) node *list = NULL; } 3. 새로운 node를 위한 메.. 2021. 12. 11. 6: 자료구조-3(연결 리스트: 도입) 자료 구조: C, C++, 자바, 파이썬에 있는 프로그래밍 구조 자료 구조는 컴퓨터 메모리에 정보를 각기 다른 방법으로 저장할 수 있도록 해 줌 데이터 구조는 우리가 컴퓨터 메모리를 더 효율적으로 관리하기 위해 서로 정의하는 구조체 일종의 메모리 레이아웃, 또는 지도라고 생각할 수 있음 1) 구조체(struct) - C에서 자신만의 구조를 만들 수 있는 키워드(예, person 구조체에 이름과 번호) 2) . 구조체의 속성 값에 접근할 때 사용(속성 값을 가져올 때 사용) 3) * 메모리 덩어리로 접근할 수 있는 역참조 연산자 배열 장점: 쉽게 인덱싱할 수 있음 단점: 고정된 값 배열에서는 각 인덱스의 값이 메모리상에서 연이어 저장되어 있음 연결 리스트 : 각 값이 메모리 상의 여러 군데에 나뉘어 있어도.. 2021. 12. 11. 이전 1 2 3 4 ··· 7 다음
