[자료구조&알고리즘] 1-1 자료구조와 알고리즘의 개념과 정의

## 이 문서는 성균관대학교 성재필 교수님의 강의인 인공지능을 위한 알고리즘과 자료구조를 정리한 내용입니다.

강의 목표

1.Discuss key data structures and algorithems essential for solving problems with computers

2.Programming skills -Translate your idea into languages that computers can understand

3.Computational thinking -Problem formulation(abstraction) -solution expression(automation) -solution execution and evaluation(analysis)

Intro

우리가 어떤 문제를 해결하기 위해서는 맞닥드리는 자료들에 따라서 그 자료에 적합한 자료구조를 선택해야 한다. 예를 들어, 아래와 같은 성적을 처리한다고 했을때, 여러 과목을 수강하고 있기 때문에 다양한 교과목의 점수를 이름과 매칭 시켜 기록하기 위해서는 array형태가 적합하다고 할 수 있다.

name	math	english	physics
kim	100	50	20
lee	20	30	50

하지만 조직도를 표현할때는 Tree형태가 적합하다고 할 수 있으며, 지하철 노선도와 같은걸 표현하려면 Graph와 같은 자료구자가 적합하다고 할 수 있고, 데이터에 따라 부적합한 자료구조를 선택하게 되면 문제를 해결하는데 그 복잡도가 더욱더 올라간다. 따라서 적접한 자료구조를 정하는 것이 굉장히 중요하다.

자료구조란 무엇인가?

자료구조는 말 그대로 자료의 구조이며, 자료구조를 이루는 것들은 자료의 그 값으로 3,4,5 같은 숫자들이나, ‘허재필’과 같은 문자열들과 같은 자료의 값 그 자체와 자료들의 간의 관계를 포함한다. 또 이런 자료들에 가해질 수 있는 오퍼레이션들 역시 우리가 통상적으로 자료구조라는 범위안에 포함을 시켜놓고 있다. 예를들어 ‘서울’에서 ‘부산’으로 도시명을 바꾸는 작업을 했다라고 한다면, 값이 바뀌게 되는 수정의 오퍼레이션이 되는 것이다.

• 컴퓨터로 어떤 자료를 나타내기 위해서는 abstraction 즉 추상화라는 과정을 거치게 되는데, 이는 필수적인 요소만 남겨놓은 채 너무 디테일한 내용들을 제거시키는 과정을 이야기 한다.

예시로, 수도권 지하철노선도를 보면, 오른쪽 사진은 지하철 노선도를 실제 지도에 mapping을 해 놓은 것이며 많은 정보를 담고 있다. 따라서 지도의 사진을 오른쪽에 나와있는 것과 같이 약도형태로 필요 없는 디테일한 정보들을 삭제하고, 이 문제를 해결하기 위해서 꼭 필요한 정보들을만 남기는 과정을 수반하게 된다.

즉, 자료구조는 앞에서 말한것과 같이 자료의 값, 자료들의 관계성, 그리고 자료들의 가해질 수 있는 어떤 Operation들을 포함하며 자료구조에서 필수적이라고 할 수 있는 것은 아래의 표처럼 정리가 될 수 있다.

먼저 Primitive한 자료구조라고 얘기하면 일반적으로 Programming language에서 가장 기본적으로 제공하는 데이터 구조이다. 예를 들면, 정수형이라든지, 실수형, 아니면 문자 하나를 기록할 수 있는 Character와 같은 것을 Primitive한 자료 구조라고 할 수 있다.

반면에 Non-primitive한 것들은 그것의 모양에 따라서 linear,non-linear,files와 같이 구분해서 부를 수 있으며, linear한 자료구조는 자료가 선형으로 펄쳐져 있으며, 첫번째부터 끝까지 자료가 여러 개 있다고 했을 때, 첫번째부터 쭉 나열이 되어 있는 형태인 array나 list. list의 어떤 특정한 constraint를 추가한 stack이나 queue가 있다.

non-linear한 자료구조는 자료의 모양이 선형적이지 않은 모든것을 이야기하며, tree나 graph등을 non-linear한 자료구조라고 할 수 있다.

알고리즘은 무엇일까?

"An algorithm a sequence of computational steps that transform the input into the output"

알고리즘의 정의는 어떤 주어진 input을 적절한 output으로 변환하기 위한 어떤 컴퓨터가 수행할 수 있는 operations들의 Sequence이다.

알고리즘을 표현할 때, 함수, 수학에 나오는 함수와 굉장히 연관을 지어서 많이 이야기 하는데, f(x)라고 얘기하면 input이 x가 들어가면 f(x)가 나오게 되는 것과 같은 원리이다.

예를 들어, f는 x+2다. 그러면 f(x)에 x를 2를 넣으면 답은 4가 나오게 되는 것 처럼, 입력 2에 대해서 출력 4가 나오고 그 안에서 컴퓨터가 주어진 x에 더하기 2를 하는 operation과 같이 알고리즘은 함수와 굉장히 비슷하다.

여기서 알고리즘과 instance라는 개념이 있는데, instance는 어떤 특정 알고리즘의 입력이 되는 어떤 데이터를 얘기한다.

"An instance of a problem consists of the input needed to compute a solution to the problem"

위에서 예를 들은 input 2는 우리가 가지고 있는 알고리즘의 instance가 되는 것이다. 당연하게도, 알고리즘으로 문제를 해결하기 위해서 필요한 모든 정보가 instance에 포함되어 있어야 한다.

어떤 알고리즘이 옳다라고 이야기 할 때는 두가지 조건을 만족해야 한다.

(1) 이 알고리즘의 모든 가능한 인풋 인스턴스에 대해서 정답을 내야 한다.

(2) 이 알고리즘이 반드시 종료되어야 한다.

ex. Sorting Problem

어떤 숫자나 문자를 정렬하는 알고리즘을 갖고 있다고 했을때, input은 N개의 숫자 혹은 N개의 오브젝트 같이 서로 비교가 가능한 N개의 인풋을 줬을 때 아웃풋은 이 인풋을 재배치해주는 결과값일 것이다. 예를 들어, Input이 1,5,2,3,7라 한다면 Output은 1,2,3,5,7이 될 것이며, 문자가 나,다,가로 입력이 왔을 때, ㄱ~ㅎ 순서대로 가,나,다로 Output이 나올 것이다.

*우리가 얘기하는 프로그램과 알고리즘은 과연 같은 것인가? 어떤 프로그램들은 종료가 되면 안되는 프로그램이 있다. 예를 들어, OS, Windows나 linux같은 이런 OS들은 사용자가 종료하라고 하기 전까지 종료를 하면 안되기 때문에 프로그램과 알고리즘은 꼭 같지는 않다.