자료구조(Data Structure)와 알고리즘

//자료구조란?//데이터를 표현하는 방법 및 구조

자료에 대한 처리를 효율적으로 수행할 수있도록 자료를 구분하여 표현하는 것

• 역할 : 프로그래밍에서 가장 기초적인 학문 분야 

->프로그램의 기본 골격 - 효율적이고 안전하게 동작하기 위해서 반드시 필요함

->프로그램 개발과정과 건물 건축하는 과정과 유사

BUT, 프로그램의 크기가 작은 경우, 대형 프로젝트의 초기 단계 -> 구조적인 결함 발생

• 목적: 자료구조는 컴퓨터의 자료를 효율적으로 저장하고, 관리하기 위해 사용한다. 

사용하는 이유? 메모리를 절약하고 프로그램 수행(실행) 시간을 단축을 목적으로 사용된다.

• 프로그램의 수행시간 혹은 저장 공간을 고려한 자료구조의 설계

->프로그램이 어떻게 사용되는지에 따라 결정(목적 및 기능에 적합한 자료구조 설계)

(예) 윈도우 탐색기(트리, 리스트), 사전 프로그램(검색)

1. 윈도우 탐색기 ->(명령) 파일 및 폴더의 게층 구조 정보 / (자료)파일의복사, 이동 및 삭제

2. 전자사전 -> 단어의 철자 및 의미 /단어 검색

//자료구조의 선택 기준//

1. 자료의 처리 시간

2. 자료의 크기 

3. 자료의 활용 빈도 

4. 자료의 갱신 정도 

5. 프로그램의 용이성

//자료구조의 특징//

1. 효율성 : 상황에 맞는 알고리즘을 사용하여 자료를 구조화 시켜 데이터 처리의 효율을 높일수있음.

2. 추상화 : 복잡한 자료, 모듈, 시스템 등으로부터 해심적인 개념 or 기능을 간추려내는 것. 

3. 재사용성 : 자료구조를 설계 할 때 특정 프로그램에 맞추어 설계하는 것이 아닌 다양한 프로그램에서도 사용할 수있도록 되어있음.

//자료구조의 분류//

[자료의 형태에 따른 분류]

• 단순 구조

프로그래밍 언어에서 제공하는 기본적인 자료형을 말한다.

(예) 정수(int), 실수(float), 문자(char)와 문자열(string) 등

• 선형 구조 

자료들 사이의 앞뒤 관계가 일대일(1:1)인 경우를 선형 구조라고 한다.

(예) 리스트(LIST), 스택(STACK), 큐(QUEUE)와 덱(DEQUE) 등

• 비선형 

다음 그림과 같이 자료들 사이의 앞뒤 관계가 계층 구조 혹은 망 구조를 가지는 경우를 비선형 구조라고 한다. 선형구조와 달리 1:1관계가 아니고 1 : 다수의 구조를 가지고있다.

(예) 트리(TREE), 그래프 등

• 파일 구조

보조기억장치(하드디스크)에 저장되는 파일에 대한 자료구조

*자료구조를 이용하는 사용자의 관점*

->자료구조의 내부 구현 소스에 대한 분석 없이 신속하게 자료구조를 이용가능

(예) 이름, 입력, 출력

*자료구조를 공급하는 개발자 관점*

->자료구조를 구현하기 전에 설계도를 미리 그려보는 것

->자료구조의 개발자와 사용자 사이의 간섭 문제가 해결

---

//알고리즘//

문제 해결 절차를 체계적으로 기술한 것을 알고리즘이라고 한다. 

넓은 의미 ; 자료구조와 함께 컴퓨터 프로그램을 구성하는 한가지 요소

-> 컴퓨터의 명령어들의 집함

좁은 의미 : 어떠한 문제를 해결하기 위한 절차

(예) 1부터 100까지 합을 구하는 문제 

• 알고리즘의 조건

1. 입력 - 알고리즘은 0 또는 그 이상의 외부에서 제공된 자료가 존재한다.
2. 출력 - 알고리즘은 최소 1개 이상의 결과를 가진다.
3. 명확성 - 알고리즘의 각 단계는 명확하여 애매함이 없어야 한다.
4. 유한성 - 알고리즘은 단계들을 유한한 횟수로 거친 후 문제를 해결하고 종료해야 한다. 알고리즘의 한 단계 이후 m의 값은 n 보다 작으며, m!=0이면 n의 값은 다음 번 단계에서 줄어든다.
5. 효과성 - 알고리즘의 모든 연산들은 사람이 종이와 연필을 이용하여 유한한 시간 안에 정확하게 수행할 수 있을 정도로 충분히 단순해야 한다.

• 알고리즘의 표현

언어	내용	특성
자연어	사람이 사용하는 일반적인 언어 표현	알고리즘 표현으로 부적절 ->기술하는 사람에 따라 일관성과 명확성이 달라짐
순서도	알고리즘을 그림으로 도식화해서 표현	장점: 알고리즘 각단계를 직관적으로 표현 단점 : 복잡한 알고리즘을 나타내기에는 비효율적
의사코드	특정 프로그래밍 언어가 아닌 가상의 언어로 표현	프로그래밍 언어보다는 덜 엄격한 문법이나, 자연어 보다는 더 체계적으로 기술이 가능,자료구조/알고리즘 책마다 구문에 차이가 있음 유사코드 or 슈도 코드라 불림
프로그래밍 언어	C와 같은 프로그래밍 언어로 표현	장점: 추가 구현 단계가 필요없음(알고리즘을 구현 소스를 통해 나타내기 때문) 단점 : 너무 엄격하게 기술하여 비효율적인 경구가 있다.

//알고리즘과 자료구조의 관계

자료구조를 구현하기 위해서는 알고리즘이 필요하다. 즉, 알고리즘의 성능은 자료구조에 종속되어 있다.

->어떻게 표현되고 저장되느냐에 따라 사용 가능한 알고리즘이 달라짐

자료구조의 기본적인 연산을 구현하기 위해서 알고리즘을 사용함

*자료구조 : 데이터를 표현하고 저장하는 방법

*알고리즘 : 문제 해결 방법