Data Structure & Algorithm

Data Structure & Algorithm

Data Structure

Data Structure는 자료구조, 데이터구조 이다.
데이터 또는 대량의 데이터를 처리 하기 위해
데이터의 특성에 따라 데이터를 구조화 해서
효율적으로 관리하기 위한 것이다.

데이터에 대한 효율적인 접근과 조작하기 위한 것이다.
특정한 목적에 부합하는 자료구조는 존재하지 않는다.
상황에 따라 자료구조의 장점을 이해해서 사용하는 것이 자료구조이다.

예를들어 책을 넣어서 가지고 간다고 생각해보자.
이때 책을 넣을 수 있는 도구로는 가방, 상자, 캐리어 등의 도구가 있다고 했을 때 가장 좋은 것은 가방일 것이다. 들고 다니기 편하며, 책을 넣고 다니기 가장 좋은 도구이다.

여기서 책은 데이터가 되고, 도구들은 자료구조가 된다. 캐리어나, 상자 등에 넣어서 책을 들고 다닐 수도 있지만, 그러기에는 너무 비효율적일 것이다.

이렇듯 데이터의 상황에 맞는 자료구조를 이해하고 사용하는 하는 것이 중요하다.

자료구조 종류

• Primitive
  기본 데이터 타입이다.
  Integer, Float, String, Boolean

• Non-Primitive
  데이터 저장구조가 아닌 목적에 맞게 효과적으로 저장하는 자료구조
  Array, List, Tuple, Dictionary, Set, File

• Linear Data Structure
  선형 구조(자료의 전후 관계가 1:1)이다.
  Stack, Queues

• Non-Linear Data Structure
  비선형 구조(자료의 관계가 1:n, n:m)이다.
  Graphs, Tree

Algorithm

Algorithm은 문제를 풀기 위한 방법을 의미한다.
특정 문제에 입력을 하면 그에 대한 출력을 얻을 수 있는 것이다.
Algorithm은 프로그래밍(우리가 구현한 코드)으로 되어 있다.

예로 두개의 수를 입력 받았을 경우 합을 구하는 프로그램을 구현해보자.

def sum(a,b):
	return a+b

a,b = map(int,input().split())
result = sum(a,b)
print(result)

두개의 입력을 합을 구한다는 문제를 해결 하는 간단한 알고리즘이다.
입력으로 a,b가 주어지면 그에 대한 출력으로 a+b 를 한다.

Algorithm의 복잡도

문제를 해결하는 방법을 Algorithm이라고 했다.
하지만 문제를 해결하는 방법은 여러개 있을 수 있다. 반드시 하나의 방법으로만 해결되는 문제는 없다. 그렇다면, 이런 해결방법 중 어떤 방법이 좋은 방법인지 판단을 할 필요가 있다.

그러기 위해서 사용되는 것이 Algorithm의 복잡도이다.

예를 들어 1부터 10까지 더하는 문제를 해결하기 위한 방법으로는 무엇이 있을까?

첫번째 for문을 돌면서 다 더하는 방법이 있을 수 있다.
두번째 공식을 사용해서 총 합을 구하는 방법도 있을 수 있다.

이렇게 여러 방법 중 어떤 방법이 더 효율적인지 판단하기 위한 기준으로
Algorithm의 복잡도가 있다.

Algorithm의 복잡도는 시간복잡도, 공간복잡도가 있다.

• 시간복잡도
  알고리즘의 실행 시간
  반복문에 좌우된다.

• 공간복잡도
  알고리즘의 메모리 사용 정도
  

현대의 기술로 대용량 메모리등이 등장하면서 Algorithm의 복잡도는 시간복잡도에 중점적으로 초점이 맞추어져있다.

Algorithm 성능표기법

알고리즘의 성능표기법으로는 Big-O표기법, 오메가표기법, 세타표기법이 있다.

• Big-O표기법
  알고리즘의 최악의 실행 시간을 표기
  가장 일반적으로 사용된다.
  아무리 최악의실행 시간이어도, 이 정도의 성능은 기대한다는 의미

• 오메가표기법
  알고리즘의 최상의실행 시간을 표기

• 세타표기법
  알고리즘의 평균실행 시간을 표기

Big-O표기법

O(n) 입력 n에 따라 결정되는 시간 복잡도
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)

입력 n에 따라 기하 급수적으로 시간복잡도가 늘어 날 수 있다.
단순하게 입력 n에 따라 얼마만큼의 실행되는지 계산하면 된다.

1부터 n까지의 합을 구하는 알고리즘을 구현해 보자.

방법1

def sum(n):
	total = 0
    for number in range(1,n):
    	total = count + number
	
    return(total)

방법2

def sum(n):
	totol = n(n + 1) / 2
    return total

방법1의 경우 한번의 반복문이 실행된다. 이경우는 덧셈을 n의 수만큼 하게 된다. 그러므로 시간 복잡도는 O(n)이다.

방법2의 경우 반복문은 없다. 이 경우는 입력받은 상수가 어떻든 상수회 실회한다. 그러므로 시간 복잡도는 O(1)이다.

알고리즘이 다를 뿐 출력결과는 같다.
하지만 알고리즘의 복잡도 측면에서 방법2가 더 나은 방법이라고 할 수 있다.

참고

https://www.fun-coding.org/DS&AL1-2.html
https://www.fun-coding.org/Chapter08-timecomplexity.html