[칼럼] 컴퓨터 공학적 방법론

컴퓨터 공학과 방법론, 그렇다 알고리즘이다.

알고리즘이 무엇인지와 중요성, 특징들을 알아보고 공부에 적용시켜보는 것이 이 글의 목적이다.

What is Algorithm?

알고리즘이 뭔가? 작동원리? 코딩? 인공지능? 등 별별 어중간한 답들을 할 것이라 예상한다.

일반적으로 다음과 같은 세 조건을 만족시켜야 한다.

1. 알고리즘은 모호하지않은 일련의 절차나 명령의 집합이다

2. 알고리즘의 모든 절차는 컴퓨터에 의하여 수행 가능해야 한다.

3. 알고리즘은 반드시 종결하는 절차여야 한다.

항상 만족시키는 것은 아니다. 가령 CCTV용 컴퓨터의 경우 3번의 반례라고 들 수 있다.

다시 돌아와서, 알고리즘은 예외적인 경우를 제외하고 저 조건을 만족시켜야 한다고 말했다.

그렇다면, 과연 저 조건들이 전부일까? 아니다.

주어진 문제를 해결하는 방법은 여러 가지가 존재할 수 있다.

예를 들어, 수능 수학 문제의 기하적인 풀이라던지, 대수적인 풀이 등을 생각해보자.

알고리즘처럼 모호하지 않은 일련의 풀이 과정, 반드시 종결한다는 공통점을 가진다. 

(2번은 주로 컴퓨터에서 다루는 경우에만 적용하니 따지지 않는다.)

하지만 이러한 문제의 해결 방법이 알고리즘이기 위해서는 다른 방법에 비해 상대적으로 효율성을 가져야한다.

즉, 알고리즘은 효율성을 요구한다.

문제를 해결하기 위해 효율적인 일련의 절차나 명령이 알고리즘이다.

결국, 우리가 문제를 해결하기 위해 알고리즘을 찾아야 한다.

알고리즘은 '잘 정의된 기본절차'들을 이용하여 실현된다.

수학의 경우에는 기본 개념이라고 생각하면 된다.

국어의 경우는 명료하지 않으나, 개념어와 문장의 구조 등이라고 생각된다.

이해하기 쉽게 비유를 들어보겠다.

라는 책을 인용했다. 이처럼 기호로 특정 행동들을 정의 해두었다.

이 기호들이 지시하는 것에 익숙해지면, 복잡한 종이 3장으로 용접기 등등을 할 수 있다.

위와 같이 기본 절차들이 잘 정의된 경우, 누구라도 같은 결과를 낼 수 있다.

기본 절차들이 잘 정의되어야 다른 응용의 경우라도 알고리즘을 쉽게 적용시킬 수 있는 것이다.

컴퓨터 공학에서는, 알고리즘을 프로그램 언어로 표현한 결과물이 프로그램이고 따라서 프로그램 언어는 알고리즘을 표현하기 위한 수단으로 이해한다.

마치, 구조 독해 방법론을 기호로 표시하며 읽는 것이 구조 독해가 되고 따라서 기호는 구조 독해의 수단이 된다는 것과 비슷하다.

How to find Algorithm

구조 독해, 그거 누가 가르쳐줘요?

알고리즘은 어떻게 찾는가

문제를 해결하는 방법에 대해서는 오~래전 부터 연구되어 왔다.

1945년 수학자 조지 폴야(George Polya)는 "폴야의 문제 해결 과정(Polya's Problem Solving Problem Steps)"을 발표했다.

1. 주어진 문제의 이해

2. 주어진 문제를 해결하기 위한 구체적 방법

3. 찾은 방법에 따라 실현

4. 해결 방법의 신뢰성 검증

2번의 경우가 우리가 찾는 알고리즘이다. 그런데 폴야의 문제 해결 과정이 항상 순서대로 수행되는 것은 아니다.

종종 수학에서 대충 때려넣어 보고 대략적인 그래프 전개나 방향성을 잡는 경우가 그러하듯이 주어진 문제를 이해하기 위해 3번과 4번을 거칠 수도 있다.

위에서 말했듯, 수학 문제의 풀이가 다양한 것처럼 알고리즘의 문제 해결 방식도 다양하다.

하지만, 알고리즘은 정확하게 해결할 수 있고, 목적에 맞고, 효율적이어야 한다.

알고리즘의 시간 복잡도와 공간 복잡도를 분석해 상대적으로 더 효율적인 알고리즘을 고를 수 있다.

시간의 경우에는, 어떤 알고리즘이 수행하는데 걸리는 평균 시간과 최악 시간을 생각해 볼 수 있다.

정말 쉬운 문제에서는 5초컷 내지만, 어려운 문제에서는 10분이 걸리는 극단적인 경우와

평균 시간과 최악 시간의 차가 크지않은 무난한 경우를 생각해보자. 

두 경우를 비교해서 유리한 쪽으로 번갈아 가며 사용하는 것이 이득이다.

공간의 경우, 21 29 30 혹은 준킬러 문제에서 풀이과정이 얼마나 여백을 잡아 먹는가 또는 독해 표시가 얼마나 지저분한가 등등을 고려해볼 수 있다.

그렇다면 문제를 해결하는 알고리즘을 응용하여 유용한 풀이로 써먹어 보자.

1. 분할 정복 알고리즘

주어진 문제의 입력을 분할이 불가능할 때까지 분할하여 나온 부분문제를 해결하여, 얻은 부분해를 취합하여 원래의 문제의 해를 얻는 알고리즘이다.

대표적인 예로 파급효과 책에는 다음과 같은 내용이 적혀있다.

'킬러 같은 경우 문제를 한꺼번에 다 읽고 풀려고 하지 말고 한 문장씩 끊어 가면서 해줄 수 있는 행동을 취해야 한다.'

2.그리디 알고리즘 & 동적 계획 알고리즘

Greed, 욕심이라는 뜻에 맞게 데이터 간 관계를 고려하지 않고 가능한 해들 중에서 '욕심내어' 최소 혹은 최댓값을 가진 데이터를 선택한다.

쉽게 말해, 분기 별로 그때마다 최적인 선택을 한다. 구하기 쉬운 조건들부터 처리하는 것이라고 생각할 수 있다.

만약, 어려운 조건 하나를 해결하면 모두 풀리는 문제라고 하면 효율성이 떨어진다.

동적 계획 알고리즘의 경우도 비슷하나, 작은 부분문제를 해결하여 큰 부분문제를 해결하는데 이용하는 방식의 차이가 있다. 최적화된 풀이를 찾는데 쓸 수 있다.

3. 백트래킹 기법

간단하다. 답을 찾는 중 막히면 되돌아가서 다시 찾는다.

미로에서 노빠꾸로 오른쪽만 가다가 막히면 다시가서 길을 찾는 것으로 생각할 수 있다.

대부분의 길을 탐색하기에 이러한 방법으로 사고과정을 정립해 나간다면 매우 튼튼할 것이다.

하지만 그만큼의 시간과 노력이 필요하기에 효율성은 떨어질 수 있다.

한 번쯤은 어떻게 하면 효율적으로 내가 문제를 풀 수 있을까, 시간을 쓸 수 있을까, 공부할 수 있을까 등을

고민해 본다면, 혁신을 느낄 수 있을지 모르겠다.

올해 개정된 국어의 기술 뒷부분에도 있을지 모르겠으나, 오르비 설립자 라끄리님의 칼럼인 '어떻게 3억 연봉을 받는 사람이 될 것인가?'를 한 번 읽어보자. (본인 칼럼을 읽지 않더라도 읽는 걸 추천한다. 100배 더 좋은 글이다)

https://orbi.kr/0003806708