안녕하세요. 오랜만입니다 이번에는 트리에 대해서 알아보도록 합시다 트리 ADT란? 위의 그림처럼 각 트리 원소는 부모원소와 0개 이상의 자식을 가지고 이러한 것을 트리라고 부릅니다. 이러한 트리 ADT에는 다양한 용어가 있습니다 루트 : 부모가 없는 노드 내부노드 : 적어도 한 개의 자식을 가진 노드 외부노드('리프'라고도 부름) : 자식이 없는 노드 형제 : 같은 부모를 가진 노드들 노드의 조상 노드의 자손 부트리 : 노드와 그 노드의 자손들로 구성된 트리 경로 : 조상 또는 자손을 따라 이어진 노드 시퀀스 경로길이 : 경로내 간선의 수 노드의 깊이 : 루트로부터 노드에 이르는 유일한 경로의 길이 노드의 높이 : 노드로부터 외부노드에 이르는 가장 긴 경로의 길이 트리의 높이 : 루트의 높이 이러한 트리..
이번 시간에는 "큐"입니다. 버스나 지하철을 보시면 먼저 대기한 사람이 먼저 들어가죠? 바로 그런 선입선출의 순서를 따르는 것이 큐입니다. 큐 ADT란? 큐도 어떠한 개체를 저장하는 자료구조이고 삽입과 삭제를 아까 말씀드린 선입선출의 방식으로 구현합니다. 따라서 삽입은 큐의 뒤에서 삭제는 큐의 앞에서 수행하게 됩니다. 큐 ADT 메쏘드는 무엇이 있을까? 주로 쓰이는 큐 메쏘드는 대표적으로 push : 원소 삽입 pop : 원소를 삭제하고 반환 그리고 보조적으로 쓰이는 seek : 큐의 앞부분에 있는 원소를 삭제하지 않고 반환 size : 원소 개수 반환 isEmpty : 큐가 비어있는지 여부를 반환 printQueue : 큐의 원소들 전부를 출력 주로 이러한 메쏘드가 존재하고 있고 이것을 활용해서 큐의 ..
이번에는 스택 ADT를 살펴볼 것입니다. 스택은 간단히 말해서 "후입 선출" 즉, 나중에 들어온 것이 제일 첨 나간다. 예시를 들자면, 쌓여있는 책중에서 우리가 고르는 것은 제일 위에 있는(제일 나중에 들어온) 책을 고르게 됩니다. 또는 웹브라우저의 방문기록도 이러한 스택의 구조를 가지고 있습니다. 이러한 스택 ADT의 메쏘드를 살펴봅시다. 주로 push(e) : 원소를 삽입 pop() : 가장 최근에 삽입된 원소를 삭제하여 반환 이 두개의 함수가 쓰이게 되고 이외에는 top() : 가장 최근에 삽입된 원소를 삭제하지 않고 반환 isEmpty() : 비어 있는지 여부를 반환 이러한 메쏘드들도 사용됩니다. 이런 스택을 응용하게 되면 직접 응용 1. 웹브라우저에서 방문한 웹페이지들의 기록 2. 문서편집기에서..
이번에는 집합 ADT입니다. 먼저 특징을 살펴보자면, 집합 ADT는 유일한 개체들을 담아야 하고 이러한 개체들을 정렬된 리스트로 표현한다는 것이 되겠습니다. 각 개체들은 유일해야 하고, a b c d 나 1 2 3 4처럼 정렬되어야 합니다. 이런 집합 ADT의 주요 함수들은 이렇습니다. set union(B) set intersect(B) set subtract(B) union은 집합 B와 합집합을 반환하고, intersect는 집합 B와 교집합을 반환합니다. 그리고 subtract는 집합 B를 차감한 차집합을 반환합니다. 그리고 이러한 메서드들의 실행시간은 최대 O(|A| + |B|)가 되어야 합니다. 즉, 각 집합들의 최대 원소들의 수를 합한 것이 최대 실행시간이 된다는 것입니다. 이외의 함수들도 써..
이번 시간에는 리스트 ADT를 확장해서 그룹과 공유라는 개념을 알아봅시다. 이 개념이 다른책에는 없고 제가 듣는 강의에서만 나오는거 같은데.....그래서 간단하게 정리하는 식으로 쓰게 되었네요 ㅋㅋ 우선 그룹의 개념부터 살펴보자면 데이터 원소들이 각각 다른 그룹에 속한다는 뜻으로 받아들일 수 있습니다. 예를 들면 쇼핑몰의 상품들 1. Maker X : x1 2. Maker Y : none 3. Maker Z : z1, z2 대학의 강좌들 1. Prof. Kook : DS 2. Prof. Park : (no lecture) 3. Prof. Shin : DB, C lang 이러한 예를 들 수 있습니다. 이런 그룹의 설계 방안을 살펴보자 A. 레코드의 리스트 사용 : 1. 배열을 이용한 구현 2. 연결리스트를..
이번에는 리스트ADT를 알아볼겁니다. 우선 ADT를 먼저 알아야합니다. 추상자료형(ADT)이란 데이터구조의 추상형을 말한다고 하는데....조금 더 쉽게 말하자면 어떤 자료형이 있으면 그 자료형에 대한 연산을 명세한 것을 ADT라고 부르는 것입니다. 따라서 다음을 명세한다고 정리할 수 있겠습니다 1. 저장된 데이터 2. 데이터에 대한 작업들 3. 작업 중 발생 가능한 에러 상황들 예를 들어서 주식거래 시스템 ADT를 짠다고 하면 1. 데이터 : buy/sell 주문들 2. 지원하는 작업들 buy, sell, cancel 등이 있을 수 있다. 3. 에러 상황들 : 존재하지 않는 주식에 대한 buy/sell 주문, 존재하지 않는 주문에 대한 cancel 정말 쉽게 얘기하자면 그리고 실제로 C언어를 공부하다보면..
이번에는 데이터 구조의 기초에 대해서 이야기해봅시다. 우리가 스택, 큐, 리스트, 집합 이러한 데이터 구조를 설계할 때 우선 기초적으로 쓰이는 재료가 있는데 그것이 바로 배열과 연결 리스트입니다. 배열을 여러분들이 c, python에서 배웠다시피 순차적인 기억 장소에 할당된 유한한 개수의 데이터 원소를 저장하는 방식입니다. 이러한 배열에는 1차원, 2차원, 3차원....... 등의 다차원 배열들이 있고 각 배열들은 행 우선 순서 즉, 저 차원 우선적으로 데이터 원소들이 메모리에 할당됩니다. 배열은 프로그래밍 언어를 공부하면서 꼭 거치게 되는 개념이니까 아시는 분들이 많을 거라고 생각합니다 하지만 연결 리스트는 처음 보는 분들이 더 많을 거라고 생각하는데요 원리를 알고 보면 크게 어렵지 않은 개념입니다:)..
이번에는 재귀를 알아보겠습니다. 우선 재귀 알고리즘이란 알고리즘 자신을 이용해 정의된 알고리즘을 말합니다. 그리고 이러한 재귀는 재귀 케이스와 베이스 케이스로 이루어져 있습니다. 작동 원리 : 대기중인 재귀호출을 위한 저장/복구는 컴퓨터에 의해 자동적으로 수행됩니다. 그리고 만약 재귀알고리즘을 짜게 된다면 기본적으로 지켜야할 규칙들이 있습니다. 기본 규칙 베이스 케이스를 항상 가져야합니다. 재귀호출은 항상 베이스 케이스를 향해야 합니다. 저장/복구 때문에 성능이 저하되서 꼭 필요할 때만 써야합니다. 나쁜 재귀 베이스 케이스가 없거나 재귀 케이스가 베이스 케이스로 향하지 않습니다. 따라서 부정확한 결과, 미정지, 기억장소 고갈 등의 문제가 발생합니다. 이러한 재귀알고리즘에서 대표적으로 소개되는 사례는 하노..
