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 등의 작업을 할 수 있음 스택은 서로 관계가 있는 여러 작업을 연달아 수행하면서, 이전의 작업 내용을 저장해 둘 필요가 있..

▶배열이 나타난 이유 옛날옛날... 선배님들은 변수를 이용해서 메모리에 값을 할당하고 CPU에게 계산을 시켰다. 하지만 문제가 생겼다. 메모리에 저장해야하는 값이 많아지면서 변수의 수도 많아지게 된것이다. 예를들어 이번 달 사용한 식비를 구하고싶으면 이번달 1일부터 마지막날까지의 식비를 다 더해줘야하므로 대충 30개의 변수가 필요하다. 선배님들은 어떻게 하면 변수를 많이 안쓰고 같은 종류의 데이터를 쉽고 효율적으로 메모리에 저장할 수 있을지를 고민했고, 그렇게 나오게 된 개념이 배열임. ▶배열의 정의와 성질 배열은 같은 종류의 데이터를 모아서 메모리에 순서대로 저장하는 기법이다. 배열은 요소(element)와 인덱스로 구성되어있다. 요소는 배열안에 담겨있는 하나하나의 요소를 말한다. 배열의 성질 k번째 ..