자료구조와 알고리즘

1. 자료구조

컴퓨터에 자료를 효율적으로 저장하는 방식

 

1-2. 자료구조의 필요성과 목적

- 프로그램에서 사용하는 메모리를 절약하기 위해
- 프로그램 실행시간을 단축하기 위해
- 프로그램의 구현을 쉽게 하기 위해

 

1-3. 자료구조에는 선형 구조와 비선형 구조가 있다.

선형구조 : 여러 개의 자료를 한 줄로 순서대로 저장하는 구조(리스트, 스택, 큐 등)

단순하면서 직관적이어서 여러 프로그램에서 자료를 차례대로 저장하는 목적으로 사용한다.

비선형구조 : 각각의 자료들 사이의 앞뒤 관계가 일대일이 아니다.(트리, 그래프 등)

 

2. 알고리즘

- 어떤 문제를 해결하기 위한 효율적인 절차

- 효율적인 알고리즘이 만들어지려면 당연히 효율적인 자료구조가 먼저 선택되어야 한다. (자료구조는 모든 개발의 기본)

- 반대로 알고리즘은 자료구조를 구현하는 데에도 중요하다.

 

2-1. 알고리즘의 표현

종류	내용	특이점
자연어	사람이 사용하는 일반 언어로 표현	기술하는 사람에 따라 일관성이나 명료함이 달라진다. 그 때문에 알고리즘 표현 방법으로 부적절
프로그램 언어	C 같은 프로그램 언어로 표현	알고리즘을 구체적인 프로그램 소스로 구현하기 때문에 추가적인 구현 단계가 필요 없다. 너무 엄격하게 기술해야 해서 비효율적인 경우가 있다.
순서도	그림으로 도식화해서 표현	알고리즘 각 단계를 직관적으로 표현한다는 장점이 있다. 하지만, 복잡한 알고리즘을 표현하기에는 비효율적이다.
의사 코드	특정 프로그램 언어가 아닌 가상의 언어로 표현	프로그램 언어보다는 덜 엄격한 문법을 갖는다. 또한, 자연어보다는 더 체계적인 기술이 가능하다.

3. 순서도와 의사코드

- 순서도에서 사용하는 기호를 정리하면 아래와 같다.

4. 알고리즘의 성능 분석

-  성능 분석을 통해 알고리즘 중에서 가장 효율적인 알고리즘이 무엇인지 알 수 있다.

 

4-1. 시간 복잡도

- 입력 값에 따라 알고리즘의 수행에 걸리는 시간이다.

- 시간 복잡도에서의 시간은 수행되는 연산의 횟수이다.

- 입력 값 n에 따라 연산을 수행하는 횟수가 결정될 때 이를 시간 복잡도 함수라고 한다.