자료구조와 알고리즘 차이점

# 자료구조 와 알고리즘 정의

 

“자료구조” 의 사전적의미:

데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계

즉 데이터의 접근 을 효율적으로 관리 (저장,수정,삭제) 하기 위한 데이터 조직 입니다.

 

“알고리즘” 사전적의미:

입력된 자료를 가지고 원하는 출력을 유도 하는 유한개의 규칙의 집합.

즉, 문제 해결에 필요한 계산 절차 또는 처리 과정의 순서 

 

 

예시) 도서관 마다 책장에 진열되어 있는  방식 (연도별, 색인별, 종류별 등) 을 데이터 구조 그 구조안에서

원하는 책을 효율적으로 찾기 위한 논리적인 규칙 을 알고리즘

 

자료구조 방법론으로 인해 새로운 개발 언어들이 탄생 되고

특히 객체 지향 언어 (C#, Java) 같은 경우 세부적인 구현 방식은 몰라도 인터페이스 를 이용해서 

개발을 쉽게 하는 경우가 많습니다. 네트워크 데이터를 제어 한다던지 디스플레이 GDI를 직접 그린

다던지 하는 저수준(Low Level)에 처리 하는 구현 방식을 모르더라도 인터페이스 호출 만으로 구현 할 수 있어 편리 합니다.

 

C++의 표준 템플릿 라이브러리나 자바의 자바 API, 마이크로소프트 .NET과 같은 표준 라이브러리가 이에 해당 됩니다.

 자료구조에서 가장 기초적인 단위는 행렬, 레코드, 유니온, 참조와 같은 것입니다.

 

# 자료구조 종류

구현에 따라 

배열: 메모리상에 같은 타입의 자료가 연속적으로 저장 됩니다.

튜플: 둘이상의 묶음을 표현 하기에 용이 합니다.

연결리스트: 노드단위로 저장되고 그 노드 안에는 데이터와 그 다음 노드를 가리키는 참조값을 가지고 있습니다.

해시테이블:  Key 와 Value 형태로 저장되며 개체가 해시값에 따라 인덱싱 됩니다.

 

여기서 한가지 짚고 가자면 *리스트와 배열의 차이점 은

리스트는 메모리 공간을 동적으로 할당 되어서 관리 하고 저장되는 위치가

불연속적인 반면에 메모리는 공간을 정적으로 할당되어 저장되는 위치는 연속적 입니다.

동적이라는 말은 특정 공간을 점유 하지 않고 프로그램이 해당하는 부분이 필요할 때 그때 메모리에

적재 되는 방식이고 정적이라는 말은 컴파일 실행시 항시 그 공간을 점유 해서 움직이지 않는 다는 뜻입니다.

 

위의 방식으로 인해 몇가지 특징들이 있는데 배열은 데이터가 중간에 삭제 되더라도 할당된 크기 만큼

연속적으로 할당되기 때문에 공간을 점유 하고 있습니다.

리스트는 포인터를 통해 접근 하므로 중간에 데이터가 삭제 되더라도 그  메모리 공간이 삭제 됩니다.

 

검색에 있어서는 배열이 유리 한데 연속적으로 메모리 공간을 점유 하기 때문에  검색시 빠르게

접근이 가능하고 리스트는 불규칙 적으로 메모리 공간을 점유 하므로 검색시 접근한데 속도 가 차이가 납니다.

 

그러므로 배열은 데이터 삭제가 자주 일어 나지 않고 검색을 주로 사용하면 유리 하고

리스트는 삭제가 자주 일어 나고 검색을 자주 하지 않을때 유리합니다.

 

형태에 따라  선형구조 와 비선형 구조가 있다.

 

선형 구조

스택: 데이터가 후입선출(First In First Out) 형태로 관리 됩니다.

큐: 데이터가 선입선출(Last In Last Out) 형태로 관리 됩니다.

 

비선형구조

그래프:  vertex와 edge로 구성된 한정된 자료구조를 의미 합니다. vertex는 정점,

edge는 정점과 정점을 연결하는 간선 입니다.

트리: 정렬된 데이터가 트리 형태로 최상위 루트노드, 자식 노드를 가리키는 부모노드, 

부모노드 하위에있는 자식노드, 자식 노드가 없는 잎노드로 구성 됩니다.

 

# 알고리즘 종류

재귀 함수

• 최대값 또는 최소값 찾기 : 가장 큰 숫자를 기억해가며 진행함
• 유클리드 알고리즘 : 두 정수의 최대공약수(GCD)를 빠르게 구하기
• 팩토리얼
• 피보나찌 수열

정렬 알고리즘

• 선택 정렬
• 버블 정렬
• 퀵 정렬
• 삽입 정렬
• 쉘 정렬
• 힙 정렬 
• 병합 정렬
• 기수 정렬

탐색 알고리즘

• 선형탐색
• 이진 탐색

해시 알고리즘

그래프 알고리즘

• BFS(Breath First Search) (깊이 우선 검색)
• DFS(Depth First Search) (넓이 우선 검색)