2주차 - 데이터 구조와 해싱, 정렬

2주차

기본 데이터 구조

데이터 타입

• 정수형 : int
• 문자형: char
• 실수형: float, double

문법 구조

DataType VariableName;

특징

• 변수는 항상 1개의 데이터만 가질 수 있음
• 변수의 값은 연산에 따라 달라 질 수 있음

구조체

• 문법 구조

structure st-name{
	dataType member 1;
		.
		.
		.
	dataType member n;
}

배열

• 동일 타입의 데이터를 갖는 여러 데이터를 사용 할 때 사용

• 문법 구조

  dataType arrayName[Size];
  

  
  

  • 예시

    • 정수 데이터 5개

      int arry[5];

    • 문자 데이터 10개

      char arry[10];

특징

• 다차원으로 사용 가능함

예시

int[,] a = new int[4,4];

• 배열의 차원 수와 차원의 길이 배열 인스턴스를 생성시 사용됨, 인스턴스 된 이후에는 변경 불가능 함
• 배열의 기본 크기는 0
• 배열 형식은 어떤식으로도 가능

Stack

Stack의 개념

• 스택은 입구 한곳만 뜷린 형태의 메모리이다 아래의 사진과 같이 제일 먼저 쌓인 메모리가 아래쪽으로 쌓이고, 마지막에 입력한 데이터가 먼저 제거되는 형태이다.

Stack의 특징

• 함수의 호출과 함께 생성되며 호출 이후 소멸된다.
• 변수 크기의 조절이 불가능 함
• 빠른 엑세스가 가능함
• 해당 메소드 내에서만 접근이 가능함
• FILO(First In Last Out)
• LIFO(Last In First Out)

Queue

Queue의 개념

• 양쪽의 끝이 뜷린 형태의 메모리

• 아래의 사진과 같이 한쪽으로 데이터가 쌓이고, 메모리에서 값을 제거할 경우 제일 먼저 들어간 값이 먼저 빠져나가는 방식

Queue의 특징

• FIFO(First In First Out)
• 사용자가 직접 관리하는 메모리 영역
• 사용자에 의해 메모리가 동적으로 할당 및 해제
• 메모리가 낮은곳에서 높은곳으로 할당 됨
• 메모리 크기 제한이 없음
• 스택보다 상대적으로 엑세스가 느림
• 전역적으로 변수 엑세스가 가능함
• 사용자가 직접 관리하는 메모리 영역이므로 메모리 관리가 필요함

컴퓨터의 연산 순위

일반 연산

• x -> +

컴퓨터

• + -> x

  컴퓨터는 왼쪽부터 수식을 처리함

연결 리스트

단순 연결 리스트

• 단순 연결리스트는 1개의 data와 link로 구성됨
• link는 다음 노드의 주소값을 가지고있음

이중 연결 리스트

• 이중 연결리스트는 Left Link, Data, Right Link로 구성됨

• Left Link는 이전 노드 주소값을 가짐

• Right Link는 다음 노드 주소값을 가짐

  
  

예시

3개 데이터 사용

원형 데이터 사용

관련 용어

그래프 구조

• 사이클을 포함하는 자료 구조

트리

• 사이클이 존재하지 않는 그래프 구조

일반 트리

• 하나의 가지에서 나오는 서브 가지의 수가 임의 개인 트리

이진 트리

• 나오는 가지의 수가 2개 이하인 트리

이진 탐색트리와 m-원 탐색트리의 비교

• 탐색 트리에서 다루는 데이터는 키의 값만 다름

  
  

	이진 탐색트리	M-원 탐색트리	4-원 탐색트리	9-원 탐색트리
최대 / 최소 가지의 수	2 / 0개	M / 0개	4 / 0 개	9 / 0 개
노드에서 포함한 최대 / 최소 키 값의 수	1 / 0 개	M-1 / 0 개	3 / 0 개	8 / 0 개
10개 키 값을 다룰때 필요한 노드의 수	10개 노드		4개 노드	2개 노드

해싱

정의

• 해쉬 함수와 해쉬 테이블을 이용해, 데이터를 빠르게 저장 및 탐색 가능하게 하는 방법

사용 방식

장점

• 검색시간이 테이블 크기와 관계 없이 항상 동일하며, 이진검색보다 빠름
• 삽입과 삭제가 쉬움

단점

• 키 값이 다른 데이터가 같은 해시 테이블에 있을 경우, 충돌이 일어날 수 있음
• 해시 테이블의 이용도가 낮으면, 메모리의 낭비가 심함

정렬

• 주어진 데이터를 순서에 따라 배열하는 것
  • 내부 정렬: 주 기억장치 이용
  • 외부 정렬: 보조 기억 장치 이용

참고 자료

• https://www.programiz.com/dsa/stack
• https://en.wikipedia.org/wiki/Queue_%28abstract_data_type%29