1.1 자료구조와 알고리즘
자료구조란?
컴퓨터 과학에서 자료구조는 일반적으로 데이터에 효율적으로 접근하기 위해 선택되는 데이터 조직 및 저장 형식이다. 더 정확하게 말하면, 데이터 구조는 데이터 값, 그들 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 연산의 집합이다. 즉, 데이터에 대한 대수적 구조다.
컴퓨터 프로그램은 자료(data)를 처리하고 있고 이들 자료는 자료구조(data structure)를 사용하여 저장된다. 그리고 문제를 처리하는 절차인 알고리즘(algorithm)이 필요하다.
알고리즘이란?
컴퓨터 과학에서 알고리즘은 수학적으로 엄격한 명령어의 유한한 시퀀스로, 일반적으로 특정 종류의 문제들을 해결하거나 계산을 수행하는 데 사용된다.
정의
- 입력: 0개 이상의 입력이 존재해야 한다.
- 출력: 1개 이상의 출력이 존재해야 한다.
- 명백성: 각 명령어의 의미는 모호하지 않고 명확해야 한다.
- 유한성: 한정된 수의 단계 후에는 반드시 종료돼야 한다.
- 유효성: 각 명령어들은 종이와 연필, 또는 컴퓨터로 실행 가능한 연산이어야 한다.
1.2 추상 자료형
자바의 자료형 분류
- Primitive type
- byte (1 byte, -128~127)
- short (2 bytes, -32,768~32,767)
- int (4 bytes, -2^31~2^31-1)
- long (8 bytes, -2^63~2^63-1)
- float (4 bytes, 부동 소수점)
- double (8 bytes, 부동 소수점)
- char (2 bytes, 유니코드 문자)
- boolean (1 byte, true/false)
- Reference type
- Class
- Class (incl Array, String, Collections)
- Interface (incl lambda)
- Record
- Enum
- Annotation
- Exception
- Class
추상화(Abstraction)
추상화란 소프트웨어 시스템의 복잡성에 대처하기 위한 방법론 중의 하나로, 어떤 시스템의 간략화된 기술 또는 명세로서 시스템의 핵심적인 구조나 동작에만 집중하는 것이다.
중요하지 않은 구현 세부 사항을 제거하는 정보은닉기법이 추상 자료형(ADT)으로 발전되었다.
추상 자료형(ADT: Abstract Data Type)
ADT는 실제적인 구현으로부터 분리되어 정의된 자료형을 말한다.
ADT에서는 데이터나 연산이 무엇인지는 정의되지만 어떻게 구현할 것인지는 정의되지 않는다.
알고리즘의 성능 분석
알고리즘의 복잡도 분석방법
알고리즘 복잡도 분석은 구현하지 않고도 모든 입력을 고려하는 방법이고 실행 하드웨어나 소프트웨어 환경과는 관계없이 알고리즘의 효율성을 평가할 수 있다.
시간 복잡도 함수
연산의 수를 입력의 개수 n의 함수로 나타낸 것을 시간 복잡도 함수라고 하고 T(n)이라고 표기한다.
빅오 표기법
빅오 표기법을 사용하면 시간 복잡도 함수의 증가에 별로 기여하지 못하는 항을 생략함으로써 시간복잡도를 간단하게 표시할 수 있다.
정의
두개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n>n0에 대하여 |f(n)| <= c|g(n)|을 만족하는 2개의 상수 c와 n0가 존재하면 f(n)=O(g(n))이다.
빅오 표기법 의외의 표기법
빅오 표기법은 상한을 표기한 것이므로 상한은 여러 개가 존재할 수 있다. 빅오 표기법은 최소 차수 함수로 표기되었을 경우만 의미가 있다.
빅오 표기법의 이와 같은 문제점을 보완하기 위하여 빅오메가와 빅세타 표기법이 있다.
빅오메가 표기법은 하한을 표시하는 방법이고, 빅세타 표기법은 동일한 상한과 하한을 표기하는 방법이다.
최선, 평균, 최악의 경우
알고리즘의 효율성은 주어지는 자료집합에 따라 최선(best), 평균(average), 최악(worst)의 경우로 나누어서 평가할 수 있다.
