자료구조와 알고리즘

Bor·2021년 10월 15일

목록 보기

1/7

🧱 자료구조와 알고리즘 🧱

1. 자료구조 🧱 (복합 vs 선형)

자료구조란? 컴퓨터에서도 자료들을 정리하고 조직화 하는 여러 구조들이 있다. 이를 자료구조라고 부른다. 또한 자료구조는 숫자나 문자와 같은 단순 자료구조와 여러 자료들을 한꺼번에 보관하는 컨테이너와 같은 복합 자료구조로 나눌 수 있다! 우리가 공부해볼 것은 복합 자료구조

또한 복합 자료구조는 형태에 따라서 다시 두 가지로 나뉜다.

선형 자료구조 🥡 : 항목을 순서적으로 나열하여 저장하는 창고. 이들은 항목들을 접근하는 방법에 따라 다시 세분화된다. 스택, 큐, 덱 항목의 접근이 맨 앞(전단)이나 맨 뒤(후단)로 제한된다. 이전에 프로그래밍을 해봤다면 들어봤을 리스트는 가장 자유로운 선형자료구조. 임의의 위치에 항목을 삽입하거나 삭제할 수 있다.

비선형 자료구조 🧶 : 선형보다 복잡한 연결관계를 갖는다.
-트리: 조직도, 폴더구조 처럼 계층을 표현하기에 적합
-힙 트리: 우선순위 큐를 효율적으로 구현할 수 있다.
-이진 탐색트리나 AVL트리는 탐색을 위한 트리구조
-그래프: 지도, 인터넷 망 등 가장 복잡한 연결 관계를 표현할 수 있다.

이러한 다양한 자료구조는 배열 구조와 연결된 구조의 두 가지 방법으로 표현할 수 있다. 또한 많은 알고리즘들은 순환이나 반복 구조를 이용해 구현할 수 있다. 앗 반복과 순환은 무엇이 다를까? 순환은 recursive로 단순 반복이 아니라 자기 자신을 다시 호출해서 문제를 해결하는 것이다.

💻 알고리즘이란? 💻

알고리즘이 저를 여기로 이끌었습니다? 그렇다면 알고리즘이란 무엇일까? 우선 우리가 사용하는 프로그램은 무엇으로 이뤄져 있을까? 프로그램은 대부분 데이터를 처리하고 그 결과를 제공. 이 때 데이터는 자료구조를 이용해 표현된다. 또한 이를 이용해 주어진 문제를 처리하기 위한 효과적인 절차가 필요. 이처럼 어떤 문제를 해결하는 절차를 알고리즘(algorithm)이라고 한다. 결국 프로그램은 자료구조와 알고리즘으로 구성되어 있다고 볼 수 있다.

만약 사전에서 단어를 찾는다고 하면 이 배열이 자료구조에 해당하고, 단어를 찾는 방법이 알고리즘에 해당. 자료구조와 알고리즘은 밀접한 관계가 있다. (맞다! 알고리즘 선수과목이 자료구조다!!) 더 좋은 알고리즘을 사용하기 위해서는 대부분 더 복잡한 자료구조를 사용해야 한다.

📧 알고리즘에도 조건이 있다!

특히 컴퓨터에서는 알고리즘을 특정한 일을 수행하는 명령어들의 집합으로 볼 수 있다. 이 때 명령어란 컴퓨터에서 수행되는 문장들을 의미한다. 잠깐! 조금 거시적으로 보자! 사용하는 프로그래밍 언어와는 관련이 없다. 그렇지만 또 모든 명령어가 알고리즘은 아니다.

📧 알고리즘의 조건

입력 : 0개 이상의 입력이 존재해야 한다.

출력: 1개 이상의 명령이 존재해야 한다.

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

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

유효성: 각 명령어들은 실행 가능한 연산이어야 한다.

📧 알고리즘 구현 방법

알고리즘의 기술 방법에는 (1) 자연어로 표현, (2)흐름도로 표현, (3) 유사코드로 표현 (4) 파이썬(프로그래밍 언어)로 표현하는 방법이 있다.

1.2 📇 추상 자료형

📇 추상 자료형(Abstract Data Type, ADT)이란?

프로그래머가 추상적으로 정의한 자료형. 추상 자료형은 어떤 자료들과 자료에 가해지는 연산들을 구체적으로 표시한다. 이때 추상의 의미는 어떤(what?) 자료나 연산이 제공되는가 만을 정의하고, 어떻게(how?)구현되는 지는 저의하지 않는다. 추상자료형은 세부사항들은 감추고 사용자 프로그램에게는 간단한 📇 인터페이스만을 제공한다. 그래서 구현 방법이 변경되도더라고 인터페이스만 정확하게 지켜진다면 기존과 동일하게 사용할 수 있다. 이것이 정보은닉(information hiding)의 기본개념이다.

1.3 💬 알고리즘의 성능 분석

알고리즘 테스트를 볼 때, 시간도 함께 출력이 되고 설계 방법에 따라 큰 차이가 나기도 한다. 알고리즘의 효율성은 그러한 계산속도와 메모리 사용량으로 평가할 수 있다. 즉, 좋은 알고리즘은 시간도 짧게 소모되며 메모리와 같은 컴퓨터의 자원들을 적게 사용하는 것이다. 실행시간이 일반적으로 메모리공간보다 더 중요하게 인식된다. 파이썬에서 시간은 다음과 같이 측정할 수 있다.

import time 
start = time.time()

<code>

end = time.time()

이런 성능 측정은 매우 직관적이다. 그런데 하드웨어, 소프트웨어 환경에 따라서 동일하지 못하다. 또한 성능 비교에 사용했던 데이터가 아니라 다른 데이터라면 이에 따라 결과가 매번 달라질 수 있어 일관도게 실행시간을 주장할 수 없다.

💬 알고리즘 복잡도 분석이란?

구현하지 않고 효율성을 비교하는 것은 복잡도 분석(complexity analysis) 으로 가능하다. 입력의 개수를 n이라 할 때, n이 증가함에 따라서 실행시간이 어떤 혀애로 증가하는지만을 분석하는데, 모든 입력에 대해 실행 하드웨어나 소프트웨어 환경에 관계 없이 알고리즘의 효율성을 평가할 수 있다.

절대적인 실행 시간이 아니라 알고리즘을 이루고 있는 연산들의 횟수를 분석하다. 이들은 보통 입력 개수 n에 영향을 받는데, 연산의 수를 n의 함수로 나타낸것을 시간복잡도 함수라고 하고 T(n)이라고 표기한다.

사실 연산들(덧셈, 곱셈, 대입 등)마다 처리시간이 약간 다르다. 그러나 시간복잡도 함수를 구할 때 이것은 중요하지 않으며, 동일한 시간이 걸린다고 가정한다.

💬 빅오표기법

시간복잡도 함수 T(n)은 입력 개수 n에 대한 상당히 복잡한 수식으로 나타날 수 있다. 그러나 n이 커질수록 차수가 가장 큰 항의 영향이 절대적이된다. T(n) = n² + n +1 을 생각해보자

n=1 1+1+1 = 3 (n²항이 33.3%)

n=100 10000+100+1 = 3 (n²항이 99%)

결국 우리는 함수 전체 항이 아니라 최고차항만을 고려하면 될 것임을 짐작하게 한다. 이는 불필요한 정보를 제거하고 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 빅오 표기법이라고 하는데, 다음과 같이 정의된다.

💬 빅오표기법
두개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n에 대해서 |f(n)| <= c|g(n)|을 만족하는 상수 c와 n이 존재하면 f(n) = O(g(n))이다.

여기서 빅오표기법은 n에 따른 함수의 점근적인 상한을 나타낸다.

💬 빅오메가와 빅세타 표기법

빅오표기법에는 한 가지 문제가 있다. f(n) = 2n+1인 경우 O(n) 알고리즘이지만, 사실은 O(n²) 알고리즘이기도 하다. 빅오표기법은 상한을 표기한 것이므로 상한은 여러개가 존재할 수 있다. 빅오메가는 어떤 함수의 하한을 표시하는 방법이며, 빅세타는 동일한 함수로 상한과 하한을 만들 수 있는 경우를 나타낸다.

💬 입력 데이터에 따른 성능 차이

대부분의 경우 알고리즘에 최대한 불리한 입력 데이터를 사용하는 최악의 경우의 실행 시간이 가장 중요하다.

1.4 시간 복잡도 분석: 🔗 순환 알고리즘

순환알고리즘을 공부해보고 시간 복잡도를 분석을 적용해보자. 순환(recursion), 또는 재귀 호출이란 어떤 함수가 자신을 다시 호출해 문제를 해결하는 기법.

🔗 순환알고리즘이란?

순환은 본질적으로 순환문제나 그러한 자료구조를 다루는 프로그램에 적합하다. 예를 들어 정수의 팩토리얼(factorial) 은 다음과 이런 순환과 적합하다.

def factorial(n):  #순환적으로 구현한 factorial 함수
	if n==1 : return 1  #종료조건: 순환을 멈추는 부분
    	else : return n * factorial(n-1) # 자기 자신을 순환적으로 호출

많은 경우 순환은 반복(iteration)구조로 변환할 수 있다.

순환구조
n! = n(n-1)!

def factorial(n): #반복 구조로 구현한 Factorial 함수
	result = 1
    	for k in range(n, 0, -1): #k: n, n-1 ... 0
        	result = result * k 
        return result

반복 알고리즘은 for루프가 n번 반복하므로 시간 복잡도는 O(n)로, 순환의 시간 복잡도와 동일함. 순환은 트리와 같은 특정한 문제에 대해 반복에 비해 훨씬 명확하고 간결하지만 호출의 부담에 의해 반복보다 느리다. 결국 순환 알고리즘은 이해하기 쉽다는 것과 쉽게 프로그래밍할 수 있다는 장점. 대신 수행 시간과 기억 공간 사용에 있어서는 비효율적인 경우가 많다.

🔗 순환이 더 빠른 예도 있다: 거듭제곱 구하기

def power_iter(x,n):
    result = 1.0
    for i in range(n):
        result = result * X
    return result

이러한 것은 순환구조를 이용해 간단히 구현할 수 있다.

def power(x, n):
    if n ==0: return 1
    elif (n%2) == 0:
        return power(x*x, n//2) #정수의 나눗셈 
    else:
        return x * power(x*x, (n-1)//2) #n이 홀수

이 알고리즘이 순환적으로 호출될 때마다 문제의 크기는 절반씩 줄어든다.

🔗 순환이 훨씬 느린 경우가 많다. 피보나치 수열의 계산

보통 순환을 사용하면 코드가 단순화되고 가독성이 높아지지만, 이것 때문에 같은 계산을 반복해야 한다면 문제가 있을 것. 대표적인 예가 피보나치 수열.

def fib(n):
    if n == 0 : return 0
    elif n ==1 : return 1
    else : 
    	return fib(n-1) + fib(n-2)	 #순환호출

위의 함수는 단순하고 이해하기쉽게 구현되었지만 매우 비효율적. fib(6)을 호출하면 fib(4)가 두 번 반복하여 호추로딘다. 근본적인 이유는 중간에 계산된 값을 기억하지 않고 다시 계산하기 때문이다. 이는 O(2^n)으로 매우 비효율적이다. 이 또한 반복으로 구현할 수 있다. 코드는 다음과 같다.

def fib_iter(n):
    if(n<2) : return n 
    
    last = 0
    current = 1 
    for i in range(2, n+1):
    	tmp = current 
        current += last
        last = tmp 
    return current

3.1 리스트란?

리스트는 가장 자유로운 선형 자료구조

리스트 또는 선형 리스트는 항목들이 차례대로 나열되어 있는 선형 자료구조이다. 리스트의 항목들은 순서 또는 위치를 가진다. 리스트는 "항목들 사이에서 순서가 있다"는 점에서, 원소의 중복도 허용하지 않는 집합(set)과는 다르다. 집합에서는 원소에서 순서 개념이 없다.

항목들이 순서대로 나열되어 있고 각 항목들은 위치를 갖는다. 리스트는 임의의 위치에서도 항목의 삽입과 삭제가 가능하다. (스택, 큐 등 전단 후단, 임의의 위치에서 삽입과 삭제가 가능하다)

파이썬 리스트는 동적 배열로 구현되었다

기본 아이디어는 필요한 양보다 넉넉한 크기의 메모리를 사용하는 것. 실제로 크기가 3인 리스트가 필요하더라도 내부적으로 내부적으로 용량이 10인 배열을 할당하고 앞의 세 항목을 사용. C언어 배열과 달리 리스트의 크기와 리스트의 용량을 정확히 구분해야 함. 만약 항목을 계속 추가해 리스트의 크가와 용량이 모두 10이 되고 이제 남은 공간은 없다고 가정. 파이썬 리스트는 동적 배열(dynamic array)의 개념을 이용. 추가적인 공간이 필요하면 기존의 메모리를 모두 버리고 더 큰 새로운 메모리를 할당해 사용.

이와 같이 파이썬의 리스트는 용량을 늘릴 수 있어 편하지만 메모리의 낭비를 감수해야 한다. 이에 비해 튜플은 용량을 변경할 수 없으므로 모ㅔ모리 측면에서 더 효율적이라 볼 수 있다.

파이썬 리스트의 시간 복잡도

앞으로 다양한 자료구조를 구현할 때 연산들의 시간 복잡도를 정확히 분석하려면 먼저 파이썬 리스트 자체의 연산들에 대한 시간 복잡도를 알아야 한다.

append() 연산의 시간 복잡도

남은 용량이 있다면 바로 처리된다. 뒤에 남는 공간이 있다면, 시간 복잡도는 O(1)으로 볼 수 있다. 만약 내부적으로 새로운 배열을 할당하고 기존 항목들을 모두 복사해야한다면 O(n)그러나 매우 가끔 발생한다.

insert() 연산의 시간 복잡도

A.insert(0,'n')연산을 생각해보자. 항목을 바로 맨 앞에 끼워넣을 수 없다. 위의 그림처럼 먼저 한 칸씩 뒤로 이동시킨 후 0번째 항목에 값을 복사해야 한다. 시간복잡도는 당연히 O(n)이다. 파이썬 리스트는 후단 삽입은 효율적이지만 중간 전단 삽입은 이동이 발생해서 비효율적이다.

pop() 연산의 시간 복잡도

이것은 삭제연산 pop에서도 마찬가지다. 만약 s.pop(0)으로 삭제하면 모든 항목들을 앞으로 당겨야.

클래스로 구현하는 것이 더 좋은 방법이다

여러 개의 리스트를 사용하려면 어떻게 할까? 물론 모든 함수의 매개 변수에 배열을 추가하는 것도 방법이다. 자료구조를 구현하는 가장 좋은 방법은 클래스이다. 클래스는 어떻게 만들까?

필요한 클래스를 선언한다.

전역변수로 선언되었던 데이터를 멤버변수로 클래스에 넣는다. 그 방법은 생성자(constructor)로 불리는 __init()함수에서 그 변수를 선언하는 것

일반함수로 구현된 자료구조의 연산을 클래스의 멤버변수(또는 메소드)로 바꾸어 클래스에 넣는다. 이때 클래스의 멤버함수임을 나타내기 위해 첫 번째 매개변수로 self가 추가되어야 한다. (c++에서의 this와 비슷한 의미)

클래스의 멤버함수에서 객체 자신의 데이터를 사용하거나 멤버 함수를 호출하기 위해 self. 을 앞에 넣어준다. 예를 들어, 멤버 함수에서 x=10은 새로운 변수 x를 만드는 것이고, self.x = 10은 클래스의 데이터 x에 값을 할당하는 것. 클래스 안에서 isEmpty()는 일반함수 self.isEmpty()는 그 클래스의 멤버 함수를 말한다.

Bor

다음 포스트