티스토리 뷰
자료구조
자료구조의 정의 : 컴퓨터에 자료를 효율적으로 저장하는 방식
컴퓨터 프로그램이 효율적이고 안전하게 동작하기 위해서 반드시 필요한 골격
프로그램의 크기가 점점 커지거나 혹은 대형 프로젝트가 진행되면 부실한 기초는
프로그래머의 발목을 붙잡으며 프로젝트의 부실을 발생시킨다
프로그램과 자료구조의 관계 : 프로그램(자료를 처리하기 위한 명령의 집합)이 효율적으로 실행될 수 있도록 자료구조를 잘 설계하는 것이 필요하다.
자료구조를 잘 설계하므로서 시간과 메모리를 절약할 수 있다.
자료구조의 구조 : 단순구조, 선형구조, 비선형구조, 파일구조
단순구조 : 정수, 실수, 문자, 문자열 - 보통 자료구조라 통칭되는 것은 선형구조 부터 이다.
선형구조 : 리스트, 스택, 큐, 덱 - 각각의 자료들 사이의 관계가 1:1인 경우를 말한다.
비선형구조 : 트리, 그래프 - 각각의 자료들 사이의 관계가 1:1이 아닌 계층및 망구조를 가지는 경우를 말한다.
파일구조 : 보조기억장치에 저장되는 파일에 대한 자료구조를 말한다(순차적, 상대적, 색인, 다중키)
추상자료형
자료형,자료 : 자료형은 자료와 자료를 처리하기 위한 명령 혹은 연산을 합친 것
ex) 정수자료형 : 자료 : 1,0,-1,2,-2,3 ........
연산(명령) : 더하기, 나누기, 빼기, 곱하기 등
추상 : 필요에 의해 핵심적인 내용만을 재해석하여 표현함을 의미한다.
추상자료형을 표현하기 위해서는 명령마다 그 명령을 식별할 수 있는 이름, 명령을 호출하기 위해 필요한 입력 및 호출의 결과물인 출력
추상자료형과 자료구조의 관계
추상자료형은 외부에서 호출할 수 있는 일종의 인터페이스를 핵심적이고 대표적이며 내용만 간단히 기술
그에비해 자료구조는 이러한 인터페이스뿐 아니라 모든 내부 변수 및 내부 구현 연산을 포함
알고리즘 : 어떤 문제를 해결하기 위한 절차
특성 : 1. 입력
2. 출력
3. 명백성
4. 유한성
5. 유효성
알고리즘과 자료구조와의 관계
같은 자료라 하더라도 어떻게 표현되고 저장하느냐에 따라 사용가능한 알고리즘이 달라지기 때문에 효율적인 자료구조의 설계는 알고리즘의 설계에 영향을 끼친다. 이것은 프로그램의 성능을 결정짓는 가장 중요한 요인 중 하나이다.
의사코드 : 자연어(사람들이 사용하는 언어)와 c언어의 중간 단계로 자료구조 및 알고리즘의 책마다 의사코드가 달라질 수 있으며 자료구조의 설계를 보다 쉬운 알고리즘으로 보기위해 사용되는 코드
알고리즘의 분석 기준 : 공간복잡도와 시간복잡도 - 일반적으로 시간복잡도를 통해 알고리즘의 효율성을 판단한다.