자료구조란?
- 컴퓨터에서 자료를 정리하여 조직화하는 다양한 구조
- 자료를 정리하여 보관하기 위해 여러 가지 구조를 이용
자료구조의 분류
- 선형 자료구조 : 자료를 일렬로 나열할 수 있는 구조이며 자료들 사이에는 반드시 순서가 존재한다. 자료의 접근이 전단과 후단으로만 제한되는 선형 자료구조는 스택, 큐, 덱이 있고 리스트는 임의의 위치에 있는 자료의 접근을 허용하는 가장 여유로는 선형 자료구조이다.
- 비선형 자료구조 : 한 줄로 나열하기 어려운 복잡한 관계의 자료들을 표현할 수 있는 자료구조이다. 트리, 그래프, 집합이 있다.
자료구조의 표현 방법
- 배열 구조 : 자료를 배열에 모아 저장하는 방법으로 모든 자료가 인접한 메모리 공간에 저장되며 각 정보를 쉽게 찾아 편리하지만 크기 제한이 존재한다.
- 연결된 구조 : 흩어져 있는 자료들을 연결하여 하나로 관리하는 방법으로 새로운 정보를 쉽게 추가, 삭제가 가능하기 때문에 유연하게 사용이 가능하지만 관리하기 복잡하다.
알고리즘이란?
- 주어진 문제를 해결하기 위한 단계적인 절차
- 프로그래밍 언어와 상관없이 문제 해결 절차를 나타내는 명령어의 집합이다.
알고리즘의 조건
1) 입력 : 모호하지 않고 잘 정의된 입력, 0개 이상(random은 입력이 없어도 되기에)의 입력이 존재해야 한다.
2) 출력 : 명확히 정의된 1개 이상의 출력이 존재해야 한다.
3) 명확성 : 각 명령어의 의미가 모호하지 않고 명확해야 한다.(정수 연산? 문자열 연산?)
4) 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 한다.(무한 반복이 되면 안 된다)
5) 언어독립성 : 프로그래밍 언어와 상관이 없어야 한다.
6) 유효성 : 명령어들은 현재 실행 가능한 연산이어야 한다.
알고리즘 기술 방법
1) 자연어 표현
- 인간이 읽기가 쉽고 표현이 자유로워 편리한 방법이지만 사람들의 생각이 다 다르면 표현 방식도 다르기에 단어들의 의미가 명확하지 않으면 의미가 애매해질 수 있다.
ex)
2) 흐름도 표현
- 객관적이고 이해하기 쉬우나 알고리즘이 복잡하면(길다면) 그림이 너무 복잡해져 혼란을 야기한다.
ex)
3) 유사코드 표현
- 자연어보다는 체계적이고 프로그래밍 언어보다는 덜 엄격한 방법으로 프로그래밍 언어에서 발생하는 많은 불필요한 표현이 생략 가능해 알고리즘 자체에만 집중이 가능하다.
ex)
4) 특정프로그래밍 언어 표현
- 바로 실행해 볼 수 있는 편리함이 존재하나 특정 프로그래밍 문법을 정확히 따라야 하므로 언어의 특징에 따른 불필요한 표현들이 알고리즘에 포함되며 실제 구현시에 많은 구체적인 사항들이 알고리즘의 핵심적인 이해를 방해한다.
ex) c언어 표현
추상자료형이란?
- 어떤 시스템의 간략화된 기술 또는 명세이다.
- 시스템의 정말 핵심적인 구조나 동작에만 집중하며 자료형에서 필수적이고 중요한 특징만 골라 단순화시키는 작업이다.
- 그 자료형이 어떤 데이터를 다루고 그 데이터에 어떤 연산이 필요한지를 간략히 정리한 것으로 데이터의 연산이 무엇(what)인가를 정의하고 이들을 어떻게(how) 구현할 것인지는 정의하지 않는다.
- 가능한 한 그 자료형의 핵심적인 연산만을 다루려 함.
ex)
효율적인 알고리즘이란?
- 실행시간이 짧으면서(시간 효율성) 메모리와 같은 컴퓨터의 자원(공간효율성)들을 적게 사용하는 알고리즘이다.
실행시간 측정 방법
- 효율성을 측정하는 가장 단순하지만 확실한 방법으로 2개의 알고리즘을 프로그램으로 만들어 실제로 컴퓨터에서 실행시키고 실행시간을 측정하는 것.
- 알고리즘을 반드시 구현해야하며 반드시 같은 조건의 하드웨어와 소프트웨어를 사용해 실행시간을 측정해야 한다.
- 실험하지 않는 입력에 대한 실행시간을 주장할 수 없다.
알고리즘의 복잡도 분석
- 복잡도 분석은 구현하지 않고 알고리즘의 효율성을 평가하는 방법으로 처리시간을 직접 측정하는 대신에 알고리즘의 연산 횟수를 대략적으로 계산하는 방법이다.
- 시간복잡도와 공간복잡도를 분석해야 하는데 공간복잡도보다는 시간복잡도를 분석하는데 집중하는 편이 좋다.
시간복잡도(연산자의 사용 빈도수)
- 산술, 대입, 비교, 이동의 기본적인 연산을 고려
- 연산자의 사용 빈도수
- 연산의 실행횟수는 입력의 크기 n에 대한 함수 형태
- 알고리즘 수행에 필요한 연산의 개수를 계산
- 연산의 수를 n에 대한 함수 -> 시간복잡도 함수, T(n)
ex)
복잡도의 점근적 표기
- 복잡도 함수를 최고차항만 계수없이 취해 단순하게 표현하는 방법
- "얼마나 빨리 증가하는가?"만을 나타낸다. 즉, 증가속도만을 표현한다
1) 빅 오 표기법
- O(g(n))으로 표기하며 증가 속도가 g(n)과 같거나 낮은 모든 복잡도 함수를 포함한다.
- 처리시간의 상한을 의미
ex) n^2보다 빨리 처리될 수 있지만 절대로 그보다 시간이 더 걸릴 순 없다.
2) 빅 오메가 표기법
- Ω(g(n))은 증가속도가 g(n)과 같거나 높은 모든 복잡도 함수를 포함한다.
- 함수의 하한을 의미
ex) 아무리 빨리 처리하더라도 n^2 이상의 시간은 반드시 걸린다는 것을 의미
3) 빅 세타 표기법
- θ(g(n))은 증가속도가 g(n)과 같은 복잡도 함수만을 포함한다.
- 상한인 동시에 하한
- 처리시간을 정확이 구할 수 있을 때 사용한다.
빅오 표기법 종류와 순서
- 상수 < 로그 < 선형 < 선형로그 < 2차 < 3차 < 지수 < 팩토리얼 순이다.
최선, 평균, 최악의 경우 시간복잡도
- 최선의 경우 : 실행시간이 가장 적은 경우이며 알고리즘 분석에서 큰 의미는 없다.
- 평균적인 경우 : 알고리즘의 모든 입력을 고려하고 각 입력이 발생하는 확률을 고려한 평균적인 실행시간을 의미하지만 산출 하기 어렵다.
- 최악의 경우 : 자료집합중에서 알고리즘의 실행시간이 가장 오래 걸리는 경우로 가장 중요하게(널리)사용되며 계산하기 쉽고 응용에 따라서 중요한 의미를 지닌다.
쉽게 배우는 C 자료구조 | 생능출판사
코딩을 조금이라도 해 보았다면 프로그래밍이 자료(data)를 주로 다루는 것임을 알 수 있을 것이다. 우리가 프로그램을 개발할 때 가장 먼저 해야 할 일은 처리할 자료를 컴퓨터가 잘 다룰 수 있
www.booksr.co.kr
'자료구조' 카테고리의 다른 글
| 트리 (0) | 2024.07.26 |
|---|---|
| 자료구조 - 연결리스트 (0) | 2024.07.19 |
| 자료구조 - 스택, 큐, 덱 (0) | 2024.07.09 |
| 배열 (2) | 2024.07.03 |
| 알고리즘 기초 (0) | 2024.07.02 |
