[알고리즘] 1_1 알고리즘 기본

1-1 데이터 형

 - 변수들이 가질 수 있는 값의 종류 

1-2 시스템 정의 데이터형 

 - 원시 데이터형 - int, float, char, double, bool 등 

1-3 사용자 정의 데이터형

 - 시스템 정의 데이터형으로 충분하지 않을 때 대부분의 프로그래밍 언어는 사용자가 직접 데이터형을 정의할 수 있게 해준다.

   ex) C/C++의 구조체, Java 의 클래스

1-4 데이터 구조

 - 효율적으로 데이터를 사용하기 위해 컴퓨터에 데이터를 저장하고 정리하는 특별한 방법

  ( 일반적인 데이터 구조에는 배열, 파일, 연결 리스트, 스택, 큐, 트리, 그래프 등 )

 항목을 정리하는 방법에 따라 두가지로 나뉨

   - 1) 선형 데이터 구조 : 항목들이 순차적 차례에 따라 접근되지만 순차적으로 저장되어야 하는 것은 아니다 

     ( 예를들어 연결 리스트의 경우처럼 )  ex) 연결 리스트, 스택, 큐

   - 2) 비선형 데이터 구조 : 항목들이 비선형의 차례로 저장/접근 된다.

        ex) 트리, 그래프

1-5 추상 데이터형 ( Abstract Data Type ; ADT )

 - 문제를 푸는 과정을 단순화시키기 위해 데이터 구조와 연산을 합쳐 놓은 것을 추상 데이터형이라고 하는데 ADT는 두 부분으로 구성된다.

  1. 데이터의 선언

  2. 연산의 선언

 - 주로 사용되는 ADT에는 연결 리스트, 스택, 큐, 우선순위 큐, 이진 트리, 딕셔너리, 서로 소 집합, 해시 테이블, 그래프 등 다수가 있다.

 - 예를들어 스택은 데이터를 데이터 구조에 저장할 때 LIFO 방식을 사용한다. 스택에서 주로 상요하는 연산에는 항목 꺼내기, 스택의 맨 위에 있는 항목 찾기, 스택 안의 개수 찾기 등이 있다.

 - ADT를 정의할 때는 구체적인 구현은 신경 쓰지 않아도 된다. 실제 사용할 때의 구현이 중요하다.

1-6 알고리즘이란?

 - 오믈렛을 만드는 과정에 대해 생각해보자, 오믈렛을 만들기 위한 일반적인 과정은 다음과 같다.

1) 프라이팬을 준비한다.

2) 기름을 준비한다.

  a. 기름이 있는가?

    i. 있을 경우, 프라이팬에 붓는다.

    ii. 없을 경우, 기름을 살 것인가?

       1. 살 거면 가서 사온다.

       2. 안 살거면 여기서 끝낸다.

3) 스토브를 켠다.,

다음은 주어진 문제 ( 오믈렛 만들기 ) 에 대해 풀기 위한 단계별 과정을 제시한 것이다.

알고리즘은 다음과 같이 정의할 수 있다.

---------------------------------------------------------------------------------------------------------------------------------------------------

 알고리즘은 주어진 문제를 풀기 위한 단계별 지시사항들이다.

---------------------------------------------------------------------------------------------------------------------------------------------------

1.7 왜 알고리즘을 분석하는가?

 - 시간과 공간적으로 어느 것이 효율적인지 알 수 있게 해주기 때문

1.8 알고리즘 정렬의 목적

 - 주로 수행시간으로 비교하지만 다른 요인들로 비교할 때도 있다. (예를 들어 메모리, 개발자의 수고 등)

1.9 수행 시간 분석이란 무엇인가?

 - 문제의 크기( 입력의 크기 )가 증가함에 따라 처리 시간이 얼맘나 증가하는지를 분석하는 것

 - 일반적으로 다음과 같은 종류의 입력들을 볼 수 있다.

    - 배열의 큭기

    - 다항식의 차수

    - 행렬의 항목 개수

    - 이진으로 표현된 입력의 비트 수

    - 그래프에서 정점과 간선

1.10 어떻게 알고리즘을 비교하는가?

 - 실행 시간? 컴퓨터에 따라 실행 시간이 달라지기 때문에 좋은 기준은 아니다.

 - 실행된 구문의 수? 프로그래밍 언어나 프로그래머의 스타일에 따라 구문의 수는 달라지므로 좋은 기준은 아니다.

 - 이상적인 해법? 주어진 알고리즘의 수행 시간을 입력 크기 n에 따른 함수 f(n)으로 표현하고 수행 시간에 따라 이 함수들을 비교한다고 생각해보자, 이러한 비교는 기계의 속도나 프로그래밍 스타일 등에 무관할 것이다.

1.11 증가율이란 무엇인가?

 - 함수의 연산에서 입력하는 값에 따라 수행 시간이 증가하는데, 이 비율을 증가율이라고 한다.

 - 자동차와 자전거를 사기 위해 상점에 갔다고 가정해보자. 친구가 뭘 사러 왔냐고 묻는다면 보통 차를 사러 왔다고 할 것이다.

   왜냐하면 차의 비용이 자전거의 비용과 비교해서 훨씬 크기 때문이다. 

( 자전거의 비용을 자동차의 비용과 비교하여 근사치를 구하므로 )

---------------------------------------------------------------------------------------------------------------------------------------------------

총 비용 = 자동차의 비용 + 자전거의 비용

총 비용 ~ 자동차의 비용 ( 근사치 )

---------------------------------------------------------------------------------------------------------------------------------------------------

앞의 예에서 자동차의 가격과 자전거의 가격을 함수의 항으로 표현할 때 주어진 함수에서 차수가 낮은 항들은 상대적으로 덜 중요하므로 \

( 입력 크기 n이 아주 클 경우 ) 무시할 수 있다. 다음 예에서 n⁴, 2n², 100n, 500을 어떤 함수에서 각각의 비용이라 할 때 근사치는 n⁴ 가 된다.

n⁴가 가장 큰 증가율을 갖기 때문이다.

n⁴ + 2n² + 100n + 500 ~ n⁴

1.12 많이 사용되는 증가율

시간 복잡도	명칭	예
1	상수형	연결 리스트의 맨 앞에 항목 추가하기
logn	로그형	정렬된 배열에서 항목 찾기
n	선형	정렬되지 않은 배열에서 항목 찾기
nlogn	선형로그형	n개의 항목을 분할 정ㅇ복 방식으로 병합 정렬하기
n²	2차형	그래프에서 두 개의 정점 간의 최단 거리 구하기
n³	3차형	행렬 계산하기
2ⁿ	지수형	하노이의 탑 문제

다음 그림은 다양한 증가율 사이의 관계를 보여준다