Part 1. 데이터 구조 - 1장 데이터 구조와 알고리즘, 자료형, 빅 오 표기법

데이터 구조 : 데이터를 구성하고 저장하는 방법을 설명, 데이터를 식별하는 방법을 제공, 데이터의 관계를 보여주는 개념 

알고리즘 : 문제를 해결하기 위해 사용하는 일련의 단계. 

데이터 구조와 알고리즘의 관계 : 서로 다른 개념 이면서 상호 보완적이다. 데이터 구조는 알고리즘이 다루는 데이터를 구성하며, 알고리즘이 데이터를 처리하고 사용자가 원하는 완전한 정보를 산출하는 과정에서 필요한 부분을 제공한다. 

 

 

* 부동 소수점 수

: 소수를 표현 할 수 있다. 소수점 이라고 부르는 작은 점(.) 의 위치가 어딘가 떠다니는 것처럼 움직이기 때문에 부동점 (floating point) 이라는 이름이 붙었다. 

 

* 프로그래밍에서 함수는 매개변수(파라미터) 또는 인수라고 하는 데이터를 입력으로 사용하며 때로는 결과를 반환 하기도 하고, 아무런 결과도 반환하지 않을 수 있다. 이를 void 함수라고 한다. 

 

매개 변수 : 함수를 정의할 때 사용하는 변수를 뜻함 

인수 : 함수를 호출하며 전달하는 매개변수의 실제 값을 뜻함 

 

 

재귀

실행 도중 자기 자신을 호출하는 함수인 재귀 함수를 기본 적으로 제공하거나 직접 정의 할 수 있다. 이 재귀 함수는 보통 특정 조건을 충족 할 때까지 끊임 없이 동작한다. 결국 자기 자신을 호출하는 횟수의 한계인 최대 재귀 깊이 (maximum recursion depth ) 를 초과해 스택 오버프로우 에러가 발생 할 수 있다. 

 

 

알고리즘의 세가지 유형 

 

1) 분할 정복 알고리즘 ( divide and conquer algorithm ) 
큰 문제를 여러개의 작은 문제로 나눠 해결하고 결과를 결합해 하나의 해결방법을 얻는 알고리즘 이다.

 

2) 탐욕 알고리즘 ( greedy algorithm ) 

실행되는 순간마다 최상의 결정(가장 적합한 동작)을 내리는 알고리즘 이다. ( 근사치를 구함) 

 

3) 동적 프로그래밍 ( dynaic programming ) = 동적 계획 법  

과거에 내린 결정이 앞으로의 결정에 영향을 주는 알고리즘 이다. 탐욕 알고리즘과 동적 프로그래밍 알고리즘 모두 문제를 더 작은 단위로 나누는데 중점을 둔다는데 공통점이 있지만, 탐욕 알고리즘은 특정 순간에 최적인 해결방법을 찾고 동작 프로그래밍 알고리즘은 문제를 해결하는 다양한 해결 방법을 찾아 저장한 후 나중에 재사용 한다는 점에 차이가 있다. (최적화를 구함 ) 

 

 

알고리즘의 효율성 분석

1) 시간 복잡도 ( time complexity)
주어진 입력에 따라 알고리즘이 문제를 해결할 때 걸리는 시간을 뜻. 알고리즘의 성능이 얼마나 효율적인지를 알 수 있음.

2) 공간 복잡도 ( space complexity)

알고리즘이 문제를 해결할 때 점유하는 컴퓨터의 메모리 공간을 뜻한다. 널리 사용되는 편은 아님. 

자원이 제한된 시스템에서 동작하는 프로그램을 구현하는 것과 같이 특별한 경우에 사용하는 분석 방법이다. 

 

* 시간 복잡도를 훨씬 더 자주 사용 

* 알고리즘의 시간복잡도를 분석하는 방법은 두가지, 실제적인 방법과 수학적인 방법이 있다. 실제적인 방법은 입출력 데이터의 양이 알고리즘 동작에 미치는 영향을 관찰하고 기록 하여 얼마나 효율 적인지 판단. 하지만 이는 정확성이 떨어지고 사용범위가 제한적임. 이를 피하기 위해 수학적인 방법 사용해야함. 알고리즘의 효율성을 수학적으로 판단하는 방법은 점근적 분석 (asymptotic analysis) 이라고도 한다. 이 분석 방법의 본질은 수학적으로 알고리즘 성능의 한계를 증명하는 것이므로 실제적인 방법 보다 많은 시간 절약 가능. 구체적으로는 알고리즘의 성능이 최악이 되는 경계를 판단하거나 알고리즘의 평균 성능을 찾으며, 알고리즘의 점근적 증가율 비교를 위해 빅오 표기법을 사용. 

 

 

알고리즘의 효율성을 설명할때, 빅오메가, 리틀 오메가, 빅오, 리틀오, 세타 등 다양한 표기법이 존재. 

 

오메가 표기법 Ω : 알고리즘 실행하는데 걸리는 최소 시간을 측정

세타 표기법 : 알고리즘 실행하는데 걸리는 최소 및 최대 시간을 모두 측정 

빅오 표기법

대문자 O 는 시간 복잡도의 정도를 나타내는 표기법인 차수 (order) ( 복잡도의 차수 order of complextity) 를  뜻함. 

알고리즘을 실행 하는 데 걸리는 최대시간 측정. 알고리즘의 실행 시간이 최악인 경우를 나타 내는 것. 

 

 

O(1)	상수형 알고리즘이며, 데이터 입력량과 무관하게 실행 시간이 일정하다.
O(n)	선형 알고리즘 이며, 데이터 입력량에 비례하여 실행 시간이 늘어난다.
O(logn)	로그형 알고리즘 이며, 시간이 선형적으로 증가하면 n 이 기하급수적으로 증가한다. 이는 데이터 이벽량이 늘어날 수록 단위 입력당 실행 시간이 줄어든다는 뜻이다.
O(nlogn)	선형-로그형 알고리즘이며, 데이터 입력랑이 n 배 늘어나면 실행시간이 n배 조금 넘게 늘어난다.
O(n^2)	2차 알고리즘 이며, 데이터 입력량의 제곱에 비례하여 실행 시간이 늘어난다.
O(2^n)	지수형 알고리즘 이며, 데이터 입력이 추가될 때마다 실행 시간이 2배로 늘어난다.
O(n!)	계승(팩토리얼)형 알고리즘 이며, 데이터 입력이 추가될 때마다 실행 시간이 n배로 늘어난다.

 

알고리즘 성능이 좋은 순서대로 나열 ( 좋음 <-> 나쁨 ) 

O(1)

O(logn)

O(n)

O(nlogn)

O(n^2)

O(2^n)

O(n!)

 

 

 

 

출처 : 코드없는 알고리즘과 데이터 구조