[Section 1] 자료구조와 알고리즘의 이해

자료구조와 알고리즘 미리 보기

[INTRO.] 자료구조와 알고리즘

0. INTRO

파이썬의 기본 문법과 컴퓨터에 대한 기본을 이해한다면, 데이터를 어떻게 저장하고 구성하는 것이 결국 프로그램의 핵심이라는 것을 이해할 수 있을 것이다. 이러한 관점에서 자료구조는 데이터를 어떻게 저장하거나 구성할 것이지에 대한 고민이며, 알고리즘은 그 데이터를 어떻게 처리할 것인가에 대한 고민이라 할 수 있다.

1. 일반적인 자료 구조의 종류

자료구조는 통상적으로 선형 구조와 비선형 구조로 나눌 수 있다. 우리는 선형구조와 비선형 구조로 자료를 독특한 형태로 구성하거나 저장하는 것이 가능하다. 선형 구조의 예로는 리스트(Lists), 스택(Stacks), 그리고 큐(Queues)가 존재한다. 비선형 구조의 예로는 트리(Trees)와 그래프(graphs)가 존재한다. 

 

* 아래의 개요도를 참고하자.

자료구조 개요도

2. 알고리즘의 이해

알고리즘은 구성된 자료를 바탕으로 주어진 문제에 대한 해답(혹은 조건에 맞는 자료)을 어떤 방식으로 찾아낼 것인지에 대한 고민이라 할 수 있다. 같은 문제더라도 해답을 구하는 방법은 개발자에 따라서 천차만별이다. 그리고 자료 구조의 형태에 따라 같은 알고리즘(코드)으로 문제를 접근해도 프로그램의 동작 시간이 달라질 수 있다.  물론 반대의 경우도 마찬가지이다. 따라서 데이터의 양이 많아질수록, 좋은 코드를 짜기 위해서는 자료구조의 형태를 정확히 이해하고 그에 걸맞은 알고리즘을 짜야 효율적인 프로그램을 제작할 수 있는 것이다. 

 

그렇다면 알고리즘이 좋은 알고리즘인지에 대한 분석은 어떻게 할 수 있을까?

 

이에 대한 답은 두 가지로 하나는 이미 앞에서 제시했다. 바로 시간이 적게 걸리는 알고리즘이 좋은 알고리즘이자 코드이다. 이렇게 시간을 가지고 알고리즘을 분석하는 것을 지칭하는 용어가 바로 시간 복잡도(Time complexity)이다. 

 

그렇다면 또 다른 알고리즘 분석방법은 무엇인가? 그것은 바로 메모리의 사용량에 따른 분석방법이다.

 

모든 프로그램은 어떠한 값을 얻기 위해서 계산 혹은 데이터의 할당과 같은 지시(instruction)를 내리고 이 과정은 메모리의 할당을 필요로 한다. 메모리의 영역은 무한하지 않기 때문에 메모리를 적게 사용해야 좋은 코드라 할 수 있으며, 이렇게 메모리를 기준으로 알고리즘을 분석하는 것을 지칭하는 용어가 바로 공간 복잡도(Space complxity)이다. 

 

 

* 다음 강의는 성장률입니다.

[Section 1] 알고리즘의 분석 _ 성장률(Rate of Growth)