[Date Structure] 자료구조와 알고리즘
1. 자료구조
- 자료구조 : 컴퓨터에서 자료들을 정리하고 조직하는 여러 가지 구조
자료구조의 분류
- 단순 자료구조 : 대부분의 프로그래밍 언어에서 기본적으로 제공하는 정수나, 실수, 문자와 같은 것
- 복합 자료구조 : 여러 개의 자료들을 모은 창고와 같은 것
복합 자료구조에서 원하는 자료에 접근하는 방법
- Direct access(직접 접근) : 인덱스(i)를 이용하여 요소(A[i])에 한 번에 접근할 수 있는 방식
- Sequential access(순서 접근) : 시작 노드에서부터 다음 노드로 하나씩 이동하면서 원하는 자료를 찾는 연결 리스트와 같은 방식
복합 자료구조는 창고의 형태에 따라 선형 구조와 비선형 구조로 나누어진다. 이들 대부분은 직접 접근과 순서 접근 방법으로 모두 구현할 수 있다.
- 선형 자료구조 : 자료들이 기본적으로 순서적으로 나열되는 자료구조. 자료의 접근이 맨 앞과 맨 뒤 항목으로 제한되는 스택, 큐, 덱, 임의의 위치에 있는 항목에 접근할 수 있는 가장 자유로운 리스트.
- 비선형 자료구조 : 자료들이 보다 복잡한 연결 관계를 갖는 자료 구조. 계층 구조를 표현하는 트리, 우선순위 큐, 가장 복잡한 형태의 그래프.
자료구조의 가장 대표적인 응용이 정렬과 탐색이다.
2. 알고리즘
- Algorithm : 어떤 문제를 해결하는 절차. 주어진 문제를 논리적으로 해결하기 위해 필요한 절차, 방법, 명령어들을 모아놓은 것
Program = Data struecture + algorithm
프로그램은 자료구조와 알고리즘으로 구성된다.
자료구조가 결정되면 그 자료구조에서 사용할 수 있는 알고리즘이 결정된다. 응용 프르고램에 가장 적합한 자료구조와 알고리즘을 선택해야 한다.
알고리즘의 조건
| 알고리즘의 조건 | |
|---|---|
| 입력 | 0개 이상의 입력이 존재해야 한다. |
| 출력 | 1개 이상의 출력이 존재해야 한다. |
| 명백성 | 각 명령어의 의미는 모호하지 않고 명확해야 한다. |
| 유한성 | 한정된 수의 단계 후에는 반드시 종료되어야 한다. |
| 유효성 | 각 명령어들은 실행 가능한 연산이어야 한다. |
알고리즘 기술 방법
- Nature language
- Flowchart(흐름도)
- Pseudo-code(유사 코드)
- Particular programming language(c, cpp, java, etc)
3. 추상 자료형
- Abstraction(추상화) : 어떤 시스템의 간략화 된 기술 또는 명세로서 시스템의 핵심적인 구조나 동작에만 집중하는 것
- Abstract Data Type(ADT, 추상 자료형) : 데이터의 집합과 자료에 가해지는 연산들의 집합에 대한 수학적인 명세
- 자료 구조 : 추상 자료형을 프로그래밍 언어로 구현한 것.
4. 알고리즘의 성능 분석
성장하는 프로그램의 규모와 빠른 프로그램에 대한 사용자들의 선호로 인해, 하드웨어의 성능과 무관하게 효율적인 알고리즘이 필요하다.
효율적인 알고리즘은 전체 실행시간이 짧으면서 메모리와 같은 컴퓨터의 자원들을 적게 사용하는 알고리즘이다. 일반적으로 실행시간이 메모리 공간보다 더 중요하게 생각되기 때문에 알고리즘의 실행시간을 효율적인 알고리즘의 기준으로 삼는다.
실행시간 측정 방법
- Algorithm complexity analysis(알고리즘 복잡도 분석) : 알고리즘을 직접 구현하지 않고서도 대략적인 효율성을 살펴보는 것
알고리즘의 복잡도 분석 방법
- 좋은 알고리즘 : 실행시간이 빠르고 알고리즘이 필요로 하는 기억공간이 적은 알고리즘. 시간 복잡도와 공간 복잡도가 작은 알고리즘
- Time complexity(시간 복잡도) : 알고리즘의 실행 시간 분석
- Space complexity(공간 복잡도) : 알고리즘이 사용하는 기억 공간 분석