자료구조 & 알고리즘

˙자료구조

 ▷ 자료구조는 데이터에 대하여 크게 3가지로 탐구

   - 저장(INSERT) : 데이터를 어떻게 저장할 것인지?

   - 탐색(SEARCH) : 데이터를 어떻게 탐색할 것인지?

   - 삭제(DELETE) : 데이터를 어떻게 삭제할 것인지?

 

 ▷ 자료구조는 크게 단순구조와 선형구조, 비선형 구조, 파일 구조로 구성

   - 단순구조 : Program에서 사용되는 기본적인 데이터 타입

   - 선형구조 : 저장되는 자료의 전후 관계가 1:1 (리스트, 스택*, 큐*)

   - 비선형 구조 : 데이터 항목 사이의 관계가 1:N 또는 N:M (트리, 그래프)
   - 파일 구조 : 서로 관련된 Field로 구성된 레코드의 집합인 파일에 대한 자료구조

 

 요청 또는 데이터 등에 대한 요소를 구조적으로 표현하는 방법과 이에 대한 도구이다. 보다 편리하게 접근하고, 변경하기 위한 조직적인 방법으로, 각 프로세스에 대한 분석을 한 후에, 효율적인 구조를 세우기 위하여 적합한 자료구조 선택이 중요하다. 요청 또는 데이터 등에 대한 CURD 등의 작업을 보다 효율적으로 구성한다.

 

 ▷ 자료구조를 구현하기 위해서는 알고리즘이 필요

   - 자료구조의 알고리즘 : 데이터를 저장하고 탐색하는 방법에 대한 고려

   - 자료구조를 이용한 알고리즘 : 자료구조를 활용하여 어떠한 문제를 해결하고자 하는 행위

 

˙알고리즘

 ▷ 알고리즘의 조건으로는 입력, 출력, 명확성, 유한성, 효율성 등이 충족

   - 입력 : 외부에서 요청(제공)되는 자료의 수가 0개 이상 존재

   - 출력 : 적어도 2개 이상의 서로 다른 결과가 출력되어야 함(모든 입력에 하나의 출력이 되면 안 됨)

   - 명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 함

   - 유한성(종결성) : 유한 번의 명령어를 수행 후 종료

   - 효율성 : 모든 과정에 대하녀 명백하게 실행 및 검증 가능한 것이어야 함

 

 ▷ 좋은 알고리즘에 대한 분석 기준은 정확성, 작업량, 기억 장소의 사용량, 최적성, 복잡도 등으로 판단

   - 정확성 : 적당한 입력에 대하여 유한 시간 내에 명확한 답을 출력하는 것에 대한 기준

   - 작업량 : 전체적인 알고리즘 내에서 수행되는 연산들에 대한 작업의 측정량

   - 기억 장소 사용량 : 수행에 필요한 저장(요청 및 데이터)의 공간

   - 복잡도(Big - O Notation)

 

 요청 또는 데이터 등을 입력받아 의도하고자 하는 값으로 출력하는 정의된 계산 절차로, 알고리즘은 일반적으로 이슈에 대한 해결이나 방법론을 제시하는 행위 또는 과정(데이터 등에 대한 입력을 어떠한 출력으로 반환)이다. Program에서 알고리즘은 입력된 요청 또는 데이터 등을 통하여 출력될 값을 얻기 위한 계산과정을 의미한다.

 

˙알고리즘 복잡도 : Big-O (빅오) 표기법

 어떠한 목적을 달성하거나 결과물을 도출하기 위하여 사용될 수 있는 알고리즘은 다르지만, 시간 복잡도가 가장 낮고 효율적인 알고리즘을 선택하여 사용하여야 한다. 알고리즘의 실행시간은 입력 값의 크기나 크기에 따른 함수의 증가(사용) 량에 따른 것으로 확인 가능하다.

 

 - Big-O (빅오) 표기법은 불필요한 연산을 제거하여 알고리즘 분석을 보다 쉽게 하기 위한 목적으로 사용

 - Big-O (빅오) 표기법으로 측정할 수 있는 복잡성에는 시간 복잡도와 공간 복잡도가 존재

 

˙알고리즘 복잡도 : Big-O (빅오) 표기법 - 시간 복잡도

 알고리즘을 수행하기 위하여 Process들이 수행하여야 하는 연산과 함수 등에 대한 수치이다. 정렬 알고리즘(버블, 힙, 퀵, 선택, 쉘 등) 또는 자료구조(배열, 스택, 해시, 트리 등) 비교에 따라 시간 복잡도 표현 가능하다.

1        O(1)    # 상수
2n + 20  O(n)    # n
3n^2     O(n^2)  # n^2

O(1)        # 상수 : 문제를 해결하는데에 한 단계만 처리하면 되는 경우
O(log n)    # 로그 : 문제를 해결하는데에 필요한 단계들이 특정 요인에 의하여 줄어드는 경우
O(n)        # 직선적 : 문제를 해결하기 위한 단계의 수와 입력에 대한 값이 1:1인 경우
O(n log n)  # 선형로그 : 문제를 해결하기 위한 단계의 수가 N * (log2N)번 만큼인 경우
O(n^2)      # 2차시간 : 문제를 해결하기 위한 단계의 수는 입력 N의 제곱인 경우
O(C^n)      # 지수시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수 C의 N 제곱인 경우

Complexity (복잡성)	1	10 (x10)	100 (x10)
O(1)	1	1	1
O(log N)	0	2	5
O(N)	1	10	100
O(N log N)	0	20	461
O(N^2)	1	100	10000
O(2^N)	1	1024	1267650600228229...
O(N!)	1	3628800	...

 

 - O(1)

def function():
    print("function")

 

 - O(N)

def function(b):
    for a in b:
        print(a)

 

 - O(N^2)

def function(b):
    for a in b:
        for c in b:
            print(a, c)

 

˙알고리즘 복잡도 : Big-O (빅오) 표기법 - 공간 복잡도

 공간에 대한 개념으로 알고리즘 동작시 공간이 얼마나 필요한지에 대한 수치이다. 상대적으로 시간 복잡도보다는 덜 중요하지만, 효율적인 알고리즘 사용을 위해서라면 확인 필요하다.

 

 

 

 * 스택 : 한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료구조

 * 큐 : 기본적인 자료구조 중 한 가지로, 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out) 형식의 자료구조