알고리즘 기초

<알고리즘이란?>

주어진 문제(problem)의 모든 사례(instance)를 일괄적으로 해결하는 단계별 명령의 목록.

프로그래밍 언어 및 알고리즘을 실행하게되는 하드웨어와는 독립된 '추상적 실체'이다.

 

컴퓨터과학의 기본 핵심은 문제해결을 위한 컴퓨터 활용이며, 컴퓨터과학자는 주어진 문제를 해결하는 알고리즘을 개발한다. (그러나 컴퓨터로 해결이 불가능한 문제도 존재하므로, 컴퓨터과학은 문제해결책뿐만 아니라 해결책이 존재하지 않는 문제에 대한 연구도 포함한다.) 이때 해결이 가능한 문제를 계산가능한(computable) 문제라고 말한다.

*특정 컴퓨터나 특정 프로그래밍언어에 의존하는 해결책이 아니라 어느 정도의 기본만 갖추고 있는 컴퓨터나 프로그래밍언어를 이용하면 해결할 수 있는 문제를 의미함에 주의해야함

 

주어진 (해결가능한) 문제는 적절한 API(애플리케이션 프로그래밍 인터페이스)를 조합하여 해결한다. 하지만 각각의 API를 어떻게 구현하는가는 관심대상이 아니며 필요한 API의 기능과 활용법을 익혀두는 것만이 우리가 할 일이다. 이런 의미에서 컴퓨터과학을 추상화(abstraction)에 대한 연구라 부르기도 한다.

 

추상화 예시, sprt() 제곱근 함수

예를 들어, 제곱근을 계산하는 함수 sqrt()는 math 모듈에 정의되어 있으며 아래와 같이 활용한다.

>>> import math
>>> math.sqrt(16)
4.0
>>>

위 코드는 절차적 추상화(procedural abstraction)를 보여준다. 즉, sqrt() 함수가 어떻게 정의되었는가는 전혀 중요하지 않다. 대신 제곱근을 계산하는 함수라는 사실과 어떻게 활용하는가를 알기만 하면 된다. 이런 의미에서 함수를 블랙박스(black box)로 이해한다.

---

<프로그래밍>

프로그래밍은 특정 프로그래밍언어를 이용하여 컴퓨터에서 실행 가능한 프로그램으로 작성하는 과정이다.

문제 해결을 위한 알고리즘은 문제의 사례들을 표현하는 데에 필요한 데이터(data), 그리고 의도한 결과를 생성하는 데 필요한 과정(step)을 묘사한다.

프로그래밍 언어의 필수 구성요소

의도한 결과를 생성하는 과정을 묘사하는 데에 필요한 프로그래밍 언어의 필수 구성요소는 다음과 같다.

• 명령문의 순차 처리
• if...else... 등의 조건 선택 처리
• for, while 등의 명령문 반복 처리

기본 자료형

대부분의 프로그래밍언어는 아래 데이터에 대한 자료형(data type)과 연산 함수를 제공한다.

• 정수(integer)
• 문자열(string)
• 부동소수점(floating point)
• 불리언값(Boolean) - 참과 거짓

위 자료형과 관련된 연산 함수는 예를 들어 사칙연산, 논리 연산자 등이 포함된다.

원칙적으로는 언급된 필수 구성요소와 기본 자료형만을 이용하여 모든 문제를 해결할 수 있다. 하지만 복잡한 문제를 순전히 필수 구성요소와 기본 자료형만을 이용하여 해결하는 일은 매우 복잡하고 비효율적이다. 따라서 알고리즘의 복잡도와 효율성을 높혀주는 방법과 도구가 요구된다.

---

<추상 자료형과 자료구조>

문제와 문제 해결과정의 복잡도를 조절하기 위해 문제 영역에 대한 모델을 잘 설정하면 보다 효율적으로 문제를 해결할 수 있다. 이렇듯 문제와 연관된 영역(domain)에 대한 모델을 설정하는 것 또한 추상화이다.

추상 자료형

추상 자료형(Abstract data type, ADT)은 특정 데이터 및 그 데이터와 관련된 함수를 하나로 묶어 묘사하는 대상을 의미한다. 이와같이 추상 자료형을 정의하는 방식을 데이터 추상화라고 한다. 앞서 소개한 절차적 추상화의 경우처럼 사용자의 입장에서 데이터와 함수가 어떻게 구현되었는가는 중요하지 않다. 대신에 해당 데이터가 무엇을 표현하며 관련 함수의 기능이 무엇인가만이 중요하다. 이런 의미에서 데이터 추상화를 데이터 캡슐화(encapsulation)라고 부르기도 한다.

데이터 추상화(데이터 캡슐화, encapsulation)

자료구조

자료구조는 구현된 추상 자료형을 가리킨다. 자료구조를 구현하는 방식은 다양하지만, 기본적으로 구현 방식과 무관하게 의도한 데이터와 함수의 기능을 제공하기만 하면 알고리즘이 정상적으로 작동된다. 그렇지만 한정된 자원을 효율적으로 활용하기 위해 가능한 알고리즘의 효율성이 높도록 구현해야할 것이다.

---

<알고리즘 학습의 의의>

다양한 알고리즘의 학습을 통해 유사한 문제를 해결하는 능력을 향상시킬 수 있다.

예를들어, 제곱근을 계산하는 함수 sqrt()를 구현하는 다양한 방식이 존재한다. 하지만 구현 방식에 따라 동일한 결과를 계산하는 데에 필요한 시간과 메모리 소모량에 많은 차이가 발생할 수 있다. 이런 차이점은 사용된 알고리즘을 비교 분석하는 방식으로 확인할 수 있다.

문제를 해결하는 알고리즘이 존재하지만 해당 알고리즘을 실행할 때 적절한 시간 내에 실행이 멈추지 않는 경우도 존재하기에 그런 알고리즘을 구별해내는 일이 아예 해결책이 존재하는 문제를 구별해 내는 일처럼 중요하다.

문제를 해결하는 알고리즘을 작성하는 능력 뿐만 아니라 다양한 알고리즘을 분석, 비교하여 가장 좋은 알고리즘을 선택하는 능력 또한 매우 중요하다.