Computer Science

그래프를 구현하는 방법에는 크게 두가지가 있다.1. 순차 자료구조를 이용한 그래프의 구현 : 인접 행렬2. 연결 자료구조를 이용한 그래프의 구현 : 인접 리스트 이번에는 인접행렬로 그래프를 구현해보겠다. ▶전체코드#include #include #define MAX_VERTICES 5 // 최대 정점의 수 제한// 그래프 구조체typedef struct Graph { int numV; //정점의 수 설정 int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // 인접 행렬} Graph;// 그래프 초기화void graphInit(Graph* g, int numV) { g->numV = numV; ..

▶순차 자료구조의 문제점1. 삽입 연산이나 삭제 연산 후에 연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가 작업과 시간 소요2. 순차 자료구조는 배열을 이용해 구현하기 때문에 배열이 갖고있는 메모리 사용의 비효율성 문제를 그대로 가짐   ▶연결 자료구조자료의 논리적인 순서와 물리적인 순서가 불일치함물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않는다.여러개의 작은 공간을 연결하여 하나의 전체 자료구조를 표현크기 변경이 유연하고 더 효율적으로 메모리를 사용  ▶연결리스트란?연속된 노드의 연결제노드란? 연결리스트에서 사용되는 하나의 데이터 덩어리(데이터, 링크를 가지고있음)   ▶순차 자료구조와 연결 자료구조의 비교순차자료구조필요한 전체 메모리 크기를 계산하여 할당하고, 할당 된 메모리의 시..

▶Queue란? Queue는 앞뒤가 뚫려있는 쇠파이프를 떠올리면 이해하기 쉽다. 우리는 쇠파이프의 뒤로 차곡차곡 데이터를 넣을것이다. 그 후 데이터를 꺼내고싶으면 그 데이터를 앞에서 꺼낼 것이다. 즉, 먼저 들어가 데이터가 가장 먼저 나오게 된다. 이것을 First In First Out(FIFO) 데이터 구조라고 부른다. 원형큐는 이 파이프를 동그랗게 만든것이다. 동그랗게 만들면 메모리를 아낄 수 있다는 장점이 있다. ▶큐의 ADT 데이터를 집어넣을 수 있는 선형(linear) 자료형 FIFO(First In First Out) - 먼저 집어넣은 데이터가 먼저 나옴 데이터를 집어 넣는 enqueue, 데이터를 추출하는 dequeue 등의 작업을 할 수 있음큐는 순서대로 처리해야 하는 작업을 임시로 저장..

▶Stack이란? 스택은 프링글스통을 생각하면 이해하기 쉽다. 차곡차곡 쌓여져있는 맛있는 프링글스를 생각해보자. 우리는 프링글스의 위에서부터 꺼내먹는다. 즉, 가장 나중에 들어온 프링글스부터 꺼내먹는다. 이것을 자료구조에서는 마지막에 추가된 항목이 가장 먼제 제거되는 Last In First Out(LIFO) 데이터 구조라고 부른다. ▶스택의 ADT 데이터를 집어넣을 수 있는 선형(linear) 자료형 LIFO(Last In First Out) - 나중에 집어넣은 데이터가 먼저 나옴 데이터를 집어넣는 push, 데이터를 추출하는 pop, 맨 나중에 집어넣은 데이터를 확인하는 peek 등의 작업을 할 수 있음 스택은 서로 관계가 있는 여러 작업을 연달아 수행하면서, 이전의 작업 내용을 저장해 둘 필요가 있..

▶ keys▷ superkeyrelation에서 tuples를 unique하게 식별할 수 있는 attributes set ▷ candidate key어느 한 attribute라도 제거하면 unique하게 tuples를 식별할 수 없는 superkeykey or minimal superkey 라고 불리기도 함.하나하나가 독립적으로 튜플들을 유니크하게 식별할 수 없음 ▷ primary keyrelation에서 tuples를 unique하게 식별하기 위해 선택 된 candidate key보통 프라이머리 키를 고를 때 attribute 수가 적은걸 프라이머리 키로 고른다. (그게 더 편하기 때문에) ▷ unique keyprimary key가 아닌 candidate keysalternate key 라고도 불림프..

▶ 수학에서의 relational ▷set 서로 다른 elements를 가지는 collection 하나의 set에서 elements의 순서는 중요하지 않음 ▷만약 set이 N개라면? n개의 집합에 대한 cartesian product의 부분집합 = n-ray relation 각각의 리스트를 tuple이라고 부를 수 있다. ex)(1-p- … -a), (2-q-…-b) n개의 집합에 대한 튜플 = n-tuple set = 도메인 리스트 = 튜플 전체를 relation이라고 함. ▶ student relation in relational data model 이러한 relational data model을 가장 쉽게 나타낼 수 있는 방법은 테이블이다. ▷용어정리 domain : set of atomic val..