[자료 및 알고리즘] 1. 자료구조와 알고리즘 (파이썬)

[1-1] 자료구조와 알고리즘

 

자료구조란?

 

자료를 정리하고 보관하기 위해 사용되는 구조들을 칭함

(Ex. 스택, 큐, 트리, 그래프 등등)

 

 

자료구조의 분류

 

자료 구조는 우선 숫자나 문자와 같은 단순 자료구조와  여러 자료를 한꺼번에 보관하는 복합 자료구조로 나뉨.

그 중에서도 우리가 배울 복합 자료구조는 선형 자료구조와 비선형 자료구조로 나뉜다.

 

 

선형 자료구조와 비선형 자료구조의 가장 큰 차이는 순서이다. 

 

선형 구조는 자료들을 일렬로 나열하여 저장하므로 순서가 있지만,

비선형 구조는 한 줄로 세우기 어려운 복잡한 관계의 자료 (Ex. 회사의 조직도 혹은 컴퓨터 폴더)를

나타내기 때문에 순서와 거리가 멀다.

 

모든 자료구조는 배열을 이용하거나 연결된 구조로 표현할 수 잇다.

 

알고리즘이란?

 

쉽게 말하면 문제를 푸는 방법 혹은 단계적인 절차를 뜻한다.

 

프로그램은 자료구조와 알고리즘으로 이루어져있다. 

 

이해하기 위해 예시를 들어보자.

영어 사전에서 단어를 찾을 때 두 가지 방법이 있다.

 

방법 1 : 첫 페이지부터 모든 단어를 뒤져보는 방법

방법 2 : 사전이 알파벳순으로 정렬되어 있는 것을 이용하여 한 문자씩 시작하는 위치를 찾아 뒤져보는 방법

 

우리는 방법 2를 많이 사용한다. 시간이 적게 드는 더 좋은 방법이라고 생각하기 때문이다.

그렇지만 방법 2는 단어들이 배열되어 있는 자료구조가 있어야 하는 조건이 있다.

 

알고리즘의 조건 5가지

 

1. 입력 : 0개 이상의 입력이 존재하여야 한다.

2. 출력 : 1개 이상의 출력이 존재하여야 한다.

3. 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다.

4. 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 한다.

5. 유효성 : 각 명령어들은 실행 가능한 연산이어야 한다. (Ex. 0으로 나누지 않는 연산)

 

알고리즘의 기술 방법

 

알고리즘을 기술하는 방법에는 4가지가 있다.

 

1. 자연어

특징 : 읽기 쉽지만 단어들을 정확하게 정의하지 않으면 의미가 모호하다.

 

2. 흐름도

특징 : 직관적이며 이해하기 쉽다. 하지만 복잡한 알고리즘은 그리기 상당히 복잡해진다.

 

3. 유사 코드

특징 : 자연어보다는 체계적이고 프로그래밍 언어보다는 덜 엄격한 방법이다.

언어에서 발생하는 불필요한 표현들을 생략 가능 => 알고리즘의핵심적인 내용에만 집중 가능하다.

 

4. 특정 언어

구현시의 사항들이 알고리즘의 핵심적인 내용들의 이해를 방해한다.

하지만 파이썬은 C나 자바보다 훨씬 간결한 표현이 가능하며, 유사 코드와 다르게 실행이 가능하다.

 

[1-2] 추상 자료형

 

추상 자료형이란?

 

(Abstrat Data Type => ADT)

프로그래머가 추상적으로 정의한 자료형을 의미한다.

= 자료구조가 어떤 자료를 다루고, 어떤 연산이 제공되는지를 기술한다.

(단, 어떻게 (How?) 구현하는지는 정의하지 않는다 = 자세히 구현까지는 하지 않는다!!)

 

예시를 들어서 '가방'이라는 자료구조가 있다고 하자.

가방에는 휴대폰이나 지갑, 동전 등 다양한 물건을 넣을 수 있다. => 데이터

 가방으로 물건 넣기와 물건 꺼내기, 물건 개수 알아보기 등 다양한 기능을 할 수 있다. => 연산

 

Bag 추상 자료형을 정의하고 구현 (예시)

 

데이터 :

중복된 항목을 허용하는 자료의 모임. 항목들 사이에 순서는 없지만 서로 비교할 수 있어야 한다.

 

연산 : 

Insert(e) : 가방에 항목 e를 넣는다.

Remove(e) : 가방에 e가 있는지 검사하여 있으면 이 항목을 꺼낸다.

Contains(e) : e가 들어있으면 True를, 없으면 False를 반환한다.

Count(e) : 가방에 들어 있는 항목들의 수를 반환한다.

 

 

데이터들은 배열 구조인 리스트 사용, 연산들은 파이썬의 함수로 구현!!

 

#bag에 항목 e가 있는지 검사하는 bool 함수
def Contains(bag, e) :
	return e in bag

#bag에 e를 넣는 함수
def Insert(bag, e) :
	bag.append(e)

#bag에 e를 빼는 함수
def Remove(bag, e) :
	bag.remove(e)

#bag에 들어있는 항목의 수를 반환하는 함수
def Count(bag):
	return len(bag)

 

위의 코드는 Bag의 주요 연산을 일반 함수로 구현한 예이다.

함수의 매개변수 중 bag는 파이썬의 리스트라고 가정한다.

또한 이 코드에서는 in과 len()함수 그리고 리스트와 관련된 함수 ( append() , remove() ) 들을 사용하였다.

 

이제 아래 코드를 추가 작성하여 실행을 확인해보자.

 

myBag=[]
Insert(myBag,'휴대폰')
Insert(myBag,'지갑')
Insert(myBag,'손수건')
Insert(myBag,'빗')
Insert(myBag,'자료구조')
Insert(myBag,'야구공')
print('가방속의 물건:',myBag)

Insert(myBag,'빗')
Insert(myBag,'손수건')
print('가방속의 물건:',myBag)

 

아래 사진처럼 떴다면 성공이다.

 

 

[1-3] 알고리즘의 성능 분석

 

알고리즘의 실행시간을 측정하기

 

좋은 알고리즘의 기준 => 실행시간

 

import time
#시각 측정 함수를 사용하기 위하여 time 모듈을 사용함

myBag=[]

start=time.time()
insert(mybag,'축구공')
#아무 코드 들어왔다고 가정
end=time.time()

print("실행시간 = ",end-start)

 

위의 코드는 실행시간을 측정하는 코드의 예이다.

 

하지만 같은 문제를 해결하는 서로 다른 코드를 실행시간으로만 비교하는 데에는 문제가 있다.

동일한 하드웨어 환경이나 소프트웨어 환경이 아니라면 비교하기 어렵다.

또한 직접 구현해야하므로 코드를 짜고 실행하고 과정이 엄청 길다.

(실행하는 과정에서 피보나치 수열 같은 실행시간이 긴 코드는 또 엄청 기다려야 함)

 

이 문제를 해결하기 위하여 '복잡도 분석'이라는 개념을 배움

 

알고리즘의 복잡도

 

직접 구현하지 않고도 효율성을 평가하는 방법이다.

알고리즘이 수행하는 연산의 횟수를 측정하여 비교한다.

 

(시간 복잡도 분석 : 수행 시간 분석, 공간 복잡도 분석 : 필요한 메모리 공간 분석)

 

연산의 횟수는 입력의 크기 n의 함수로 나타낸다

= T(n)으로 나타내고, 이를 복잡도 함수라고 한다.

 

예를 들어보자.

자연수 1부터 n까지의 합을 구하는 두 가지 코드를 보고 복잡도 함수로 나타내 보자.

 

calc_sum1(n)
	sum<-0
    for i<-1 to n then
    	sum<-sum+i
    return sum

 

위 코드는 1부터 n까지 직접 더한 방법이다. (유사코드)

sum에다가 0을 대입하는 연산 1번이 실행될 것이다.

또한 i를 더해서 대입하는 연산 총 2번이 for문에 의해 n번 실행될 것이다.

(반복제어 연산 = i에다가 값을 넣는 행위는 무시)

그래서 총 연산 횟수는 2n+1일 것이고, 이게 T(n)이 될 것이다.

 

calc_sum2(n)
    sum<-n*(n+1)/2
    return sum

 

위 코드는 공식을 활용한 예이다 (유사코드)

대입 연산, *, +와 /가 사용되어 총 4번 연산을 수행한다.

따라서 T(n)은 4가 될 것이다.

 

 

두 연산을 비교해보면 위 사진과 같이

처음에는 1부터 하나씩 다 더한 것이 효율적일지 몰라도,

n의 값이 커져 무한에 가까워질수록 후자가 더 효율적이게 된다.

 

복잡도의 점근적 표기

 

증가속도만을 이용하여 표기하는 방법이다.

아래 사진의 두 복잡도 함수를 비교해보자.

n이 무한대에 가까워지면 최고차항을 제외한 나머지 항의 효과는 거의 없는 것이나 마찬가지이다.

 

 

요약하자면,

T(n) = 65536n + 20000000 이여도 점근적 표기로는 n이다.

다른 예시로 T(n)에 n^3+n^2이여도 점근적 표기로는 n^3이다.

 

점근적 표기는 다시 3가지로 나눌 수 있는데,

빅오 표기법, 빅오메가 표기법, 빅 세타 표기법으로 나눌 수 있다.

 

빅오 표기법 : 증가속도가 같거나 낮은 모든 복잡도 함수를 포함한다. (상한을 의미한다)

 

빅오메가 표기법 : 증가속도가 같거나 높은 모든 복잡도 함수를 포함한다. (하한을 의미한다)

Ex. 오메가 2(n^3)+n은 아무리 빨리 처리하더라도 n^2이상의 시간이 걸린다.

 

빅세타 표기법 : 증가속도가 같은 복잡도 함수들만 포함한다. (상한이면서 하한을 의미한다)

 

보통은 빅오 표기법을 주로 사용한다.

 

 

최선,  평균, 최악의 경우

 

이 경우가 적용되는 경우를 예시로 들자면, '배열에서 자료를 찾는 과정'을 들 수 있다.

 

세 가지 경우로 나누어 보자

 

최선의 경우 :

맨 처음 딱 원하는 항목을 찾았다고 하면,

T(n) = 1로 O(1)이 될 것이다.

 

최악의 경우 :

맨 마지막에 있거나 배열에 아예 없는 경우가 될 것이다.

모두 한번 씩 배열을 돌아보며 연산을 수행할 것이므로,

T(n) = n일 것이고 O(n)이 될 것이다.

 

평균의 경우 : 

모든 경우를 생각 했을 때 n가지 경우가 나올 것인데, 이것을 모든 경우의 T(n)을 더해 평균값을 낸 것이다.

T(n)은 (n(n+1) / 2) / n이 될 것이고,  정리하면 O(n)이 될 것이다.

 

최악의 경우가 가장 중요!!  이 경우를 고려해야 현실에서 사용할 때 문제가 되는 것을 방지할 수 있기 때문

 

위의 3가지 경우들을 생각하지 않아도 되는 경우로는 '배열 안의 모든 값을 더해 평균 내기'가 있을 것이다.

모든 배열의 값을 무조건 꺼내야 하기 때문에, 최선과 최악 등이 필요가 없다. 

 

[1-4] 시간 복잡도 분석 : 순환 알고리즘

 

순환이란?

 

순환이란 어떤 함수가 자기 자신을 다시 호출하여 문제를 해결하는 프로그래밍 기법이다.

 

반복 vs 순환

 

팩토리얼 (!)을 예시로 들어보자.

def factorial_iter(n) :
	result=1
    for k in range(1,n+1) :
    	result=result*K
    return result

 

위 코드는 반복적 구조이다.

 

def factorial(n) :
	if n==1 :
            return 1
    else :
    	return n*factorial(n-1)

 

이 코드는 n=1이 될 때까지 하나씩 줄어가면서, 호출을 한다.

즉 순환적 구조이다.

 

두 구조는 시간 복잡도가 O(n)으로 동일하다.

대부분의 순환은 반복으로 바꾸어서 작성할 수 있다.

 

순환을 사용하면 열 문제를 쉽게 해결할 수 있다.

'하노이의 탑' 같은 문제도 순환을 사용하면 해결하기 쉽다.

 

[참고 자료]

https://pyorang56.tistory.com/40

Week 3 (재귀) - 문제 1914번 (하노이 탑)

 

 

순환 알고리즘의 복잡도 계산

 

예시로 하노이 탑을 생각해보자.

 

T(n) = 2T(n-1) + 1

T(1) = 1

 

시간 복잡도가 위와 같이 될 것이다.

 

 

#bag에 항목 e가 있는지 검사하는 bool 함수
def Contains(bag, e) :
	return e in bag

#bag에 e를 넣는 함수
def Insert(bag, e) :
	bag.append(e)

#bag에 e를 빼는 함수
def Remove(bag, e) :
	bag.remove(e)

#bag에 들어있는 항목의 수를 반환하는 함수
def Count(bag):
	return len(bag)

#bag에 들어 있는 항목의 수를 반환하는 함수
def numOf(bag,e) :
	return len(bag)

myBag=[]
"""
Insert(myBag,'휴대폰')
Insert(myBag,'지갑')
Insert(myBag,'손수건')
Insert(myBag,'빗')
Insert(myBag,'자료구조')
Insert(myBag,'야구공')
print('가방속의 물건:',myBag)

Insert(myBag,'빗')
Insert(myBag,'손수건')
print('가방속의 물건:',myBag)
"""

 

import time

#순환적인 방법
def fib(n) :
    if n==1 or n==2 :
        return 1
    else :
        return fib(n-1)+fib(n-2)

#반복적인 방법
def fib_iter(n)  :
    if n==0 or n==1 :
        return n
    else :
        result=0
        temp1=1
        temp2=0
        for i in range(0,n-1) :
            result=temp1+temp2
            temp2=temp1
            temp1=result
        return result

def time_out(n) :
    start=time.time()
    fib(n)
    end=time.time()
    return end-start

def time_out_iter(n) :
    start=time.time()
    fib_iter(n)
    end=time.time()
    return end-start
    

#===============================================

print('Fibonacci반복(5) = ',fib_iter(5))
print('Fibonacci순환(5) = ',fib(5))

for i in range(1,40) :
    print('n= ',i,'    반복:  ',time_out_iter(i),' 순환:  ',time_out(i))