알고리즘 기본

알고리즘을 시작하는 가장 좋은 방법은 코드를 작성해보는 것입니다.

본격적인 알고리즘 학습에 들어가기 전에 몸풀기를 해보겠습니다.

관계연산자로 대소 비교

C++의 문법을 배웠다면 기본적인 사항이지만 관계연산자는 참, 거짓을 반환합니다.

A=10, B=5에서 A < B는 거짓, A > B 는 참, A == B 는 거짓입니다. C++에서 = 는 RValue를 LValue 에 대입하는 할당연산자(assignment operator)이고, == 는 오른쪽 값과 왼쪽값을 비교하는 관계연산자입니다.

알고리즘에서는 프로그램의 흐름을 제어하기 위해서 비교하는 일을 많이 하니까 의미를 분명히 알고 시작하는게 좋습니다.

세 값의 최댓값 구하기

두 값의 최대값은 비교연산자로 구할 수 있습니다. 그렇다면 세 값의 최대값은 어떻게 구할까요?

아래의 코드는 세 정수의 최대값을 구합니다.

#include <iostream>

using std::cout;
using std::endl;

int main() {
	
	int a1, a2, a3;
	int max;

	a1 = 5;
	a2 = 9;
	a3 = 7;

	cout << "세 정수의 최댓값을 구한다" << endl;
	cout << a1 << ", " << a2 << ", " << a3 << endl;

	max = a1;

	if (a2 > max) max = a2;
	if (a3 > max) max = a3;

	cout << "최대값을 구했다. " << max << endl;

	return 0;
}

세 정수의 최댓값을 구한다
5, 9, 7
최대값을 구했다. 9

값이 세개 있다면 변수가 세 개입니다. 여기다가 최대값을 나타내는 변수를 하나 더 사용합니다.

초기값은 자연수만 고려하면 0을 넣어줘도 상관은 없습니다만, 음수를 구하려면 첫번째 변수값을 할당하는게 좋습니다. 그러면 이미 하나의 값에서 출발하는 것이기 때문에 2번만 비교하면 됩니다.

이게 세 값의 최댓값을 구하는 전부입니다. 어렵지 않습니다. if문에서 부호를 반대로 바꾸면 최소값도 찾아낼 수 있습니다.

정수의 부호 판단하기

조건판단과 분기

정수를 양수, 음수, 0 을 기준으로 판단합니다.

if 문을 사용해도 되고 if else 문을 사용해도 되고 중첩 if 문을 사용해도 됩니다. 음수, 양수, 0 은 서로 겹치지 않고 하나의 정수는 하나의 부호만 갖습니다.

여기서는 간단하게 나타내기 위해 if문만 사용했습니다.

#include <iostream>

using std::cout;
using std::endl;

void findSign(int num) {
	if (num > 0)
		cout << num << "은 양수입니다" << endl;
	if (num < 0)
		cout << num << "은 음수입니다" << endl;
	if (num == 0)
		cout << num << "은 0입니다" << endl;
}

int main() {
	
	int b1 = 7;
	int b2 = -5;
	int b3 = 0;

	findSign(b1);
	findSign(b2);
	findSign(b3);
	
	return 0;
}

7은 양수입니다
-5은 음수입니다
0은 0입니다

하나의 if문은 프로그램의 흐름을 두개로 나눌 수가 있습니다. 여기에 if 문을 여러개 사용하면 그 많큼 다양한 가지치기를 할 수 있습니다. 한글 교재에서는 잘 보이지 않는데 실제로 영어권 사용자들은 branching 이라는 단어를 사용합니다. if branch (if 가지) else branch (else 가지) 처럼 나무의 뿌리에서 뻣어나간다는 아이디어를 갖습니다.

나무의 뿌리는 하나입니다. main 이 root 라는 뿌리라고 생각하면 if 문은 하나의 branch 가 됩니다. 이 branch 를 여러개 만들면 가지가 무성한 멋진 나무가 됩니다.

if 문의 목적은 어떠한 조건을 판단하기 위함만이 아닙니다. 멋진 가지(branch)로 분기하기 위한 조건을 만드는 것입니다. 위의 코드는 음수, 양수, 0이라는 세개의 가지(branch)로 분기합니다. 위에서 설명한 것 처럼 방법은 여러가지 입니다. if else 문 if 중첩문 삼항연산자 등의 방식을 사용할 수 있습니다.

문법이 다른 것에 알고리즘의 성능차이가 있을 수도 있습니다. 그러나 무엇보다 중요한 것은 목적입니다. 무엇을 위해 분기를 하는가? 라는 질문을 if 문에서 분기하기 전에 해보는 것은 좋은 습관입니다.

순서도

순서도는 흐름도(Flow Chart)라는 일의 진행과정을 단계별로 나눈 표 입니다.

프로그램을 작성하기 위해서 매우 유용한 도구입니다. 흐름도를 잘 정의하면 개발 진척상황을 확인할 수 있어서 체계적인 관리가 가능합니다.

또 알고리즘의 학습 중에 어려운 문제를 풀 때 순서도를 그리면 훨씬 이해가 빠릅니다.

루프(반복문)

C++의 반복문은 for 와 while 을 사용합니다. 다른 프로그래밍 언어에서도 문법은 약간씩 다르지만 비슷한 반복문을 사용합니다. 컴퓨터 프로그램의 반복문을 루프(loop)라고 하는데 루프를 할 줄 알게 되면 비로소 프로그래밍의 파워를 알게됩니다.

예를 들어 1부터 1억까지 더하는 코드는 아래와 같습니다.

#include <iostream>

using std::cout;
using std::endl;

int main() {
	
	__int64 sum = 0;

	for (int i = 1; i <= 100000000; i++)
	{
		sum += i;
	}
	
	cout << "1부터 1억까지 더하기 결과" << endl;
	cout << sum << endl;

	return 0;
}

1부터 1억까지 더하기 결과
5000000050000000

1억뿐 아니라 100억 1000억 등 천문학적 숫자를 더하는데 필요한 노동은 0을 몇개 더 추가하는 것 밖에 없습니다.

아마 50년 쯤 전에는 이런 일들은 사람이 직접 했을 것입니다. 우리나라도 불과 수십년전에는 주판으로 직접 계산했을 법한 일입니다.

이제는 좀 흔해진 말이지만 0과1 밖에 모르는 컴퓨터가 어떻게 알파고와 같은 인공지능을 만들어 낼 수 있는지 많은 사람들이 궁굼해합니다. 디테일한 기술은 복잡하겠지만 기본은 이 CPU의 가공할만한 연산 파워에서 나옵니다.

for 문이나 while 문이나 문법이 쉬워보이지만 실제로는 아주 무시무시한 놈입니다. 아직 인간은 for 문의 능력을 모두 활용하지 못하고 있습니다. 컴퓨터 프로그래밍의 길로 나간다면 for문은 가장 중요한 기술이므로 루프 테크닉을 완전히 마스터하기 위해서 많은 알고리즘 연습이 필요합니다.

2차원 배열을 표현하거나, 간단한 구구단 구현부터 도형 그리기 등 기본적인 예제부터 만들어 보는게 좋습니다.

이 세상에 효율적인 알고리즘이란게 있긴 합니다. 이는 자원이 제한된 실세계에서 중요한 항목입니다. 교과서에는 주로 그런 예제들이 실려있습니다.

그러나 비효율적인 알고리즘이라도 스스로 찾아내고 구현해보는 것은 학습자에게 매우 권장할만 합니다. 백날 남의 알고리즘을 카피할 뿐 자신의 언어로 알고리즘을 작성하지 못한다면 평생 남의 아이디어를 구현하는 프로그래머에 불과할 뿐 입니다.

뭐 그런 프로그래머가 직업적으로 나쁘다는 뜻은 아닙니다만, 현재의 추세로 보면 단순 코더(coder) 프로그래머(programmer) 들은 인공지능이 빠른 시일내에 대체할 것으로 예측되고 있습니다. 이미 간단한 자연어를 프로그래밍 언어로 변경해주는 인공지능 번역기 프로젝트가 상당히 진척되고 있습니다.

요새는 개발자가 모자르다고 난리라는데 이것도 인공지능이 도입되서 사람들이 필요없다 싶으면 또 쉽게 내보내는게 기업의 특징이죠. 그리고 요즘 IT인력이 부족하다는 것은 설계를 하는 엔지니어의 부족을 의미하지 프로그래머가 아닙니다.

단순 사무직은 이미 밀려나고 있는 것입니다. 이런 현상이 불과 몇십년 전에도 있었습니다. 엑셀과 같은 회계 자동화 프로그램이 발달하면서 주판을 튕기던 상고출신 경리들은 자연스럽게 산업현장에서 도태되기 시작했습니다. 왜냐? 데이터 입력과 연산 과정이 자동화 되었기 때문입니다.

회계란 모일 회 자와 계산의 계 자로 이루어진 단어입니다. 모아서 계산하는 것은 컴퓨터의 전문영역입니다. 1억개가 아니라 10억개도 요즘의 개인 PC로 처리하는데 한 1초가 걸립니다.

이는 모두 반복이 가능한 컴퓨터의 특성에서 나왔습니다.

구구단 예제 C++

간단한 예제니 직접 구현해 보고 왜 저런 결과가 나왔는지 생각해봅니다.

아래의 예제는 계산 한개 씩 한줄에 출력합니다.

한줄에 한 단을 출력하는 방식으로 바꿔봅니다. 이런 사소한 응용을 하는 것이 알고리즘 학습의 기본입니다. 지금은 오픈소스를 거의 마음대로 사용할 수 있는 시대입니다.

타인이 작성한 코드는 내가 이해하는 범위내에서 응용할 수 있습니다. 이해했는지 확인 가능한 방법은 변형해보는 것입니다. 어디까지 남의 소스를 뜯어 고칠 수 있는가? 훌륭한 프로그래머가 되기 위해서 상당히 중요한 덕목입니다.

그리고 좋은 프로그래머가 되야 설계가 가능한 엔지니어가 될 수 있겠죠?

#include <iostream>

using std::cout;
using std::endl;

int main() {
	
	for (int i = 2; i <= 9; i++)
	{
		for (int j = 1; j <= 9; j++)
		{
			cout << i << "*" << j << "=" << i * j << endl;
		}
		cout << "------" << endl;
	}
	return 0;
}

2*1=2
2*2=4
2*3=6
2*4=8
2*5=10
2*6=12
2*7=14
2*8=16
2*9=18
------
3*1=3
3*2=6
3*3=9
3*4=12
3*5=15
3*6=18
3*7=21
3*8=24
3*9=27
------
4*1=4
4*2=8
4*3=12
4*4=16
4*5=20
4*6=24
4*7=28
4*8=32
4*9=36
------
5*1=5
5*2=10
5*3=15
5*4=20
5*5=25
5*6=30
5*7=35
5*8=40
5*9=45
------
6*1=6
6*2=12
6*3=18
6*4=24
6*5=30
6*6=36
6*7=42
6*8=48
6*9=54
------
7*1=7
7*2=14
7*3=21
7*4=28
7*5=35
7*6=42
7*7=49
7*8=56
7*9=63
------
8*1=8
8*2=16
8*3=24
8*4=32
8*5=40
8*6=48
8*7=56
8*8=64
8*9=72
------
9*1=9
9*2=18
9*3=27
9*4=36
9*5=45
9*6=54
9*7=63
9*8=72
9*9=81
------

요약

기본 알고리즘이라고 하기엔 다소 부족하지만 알고리즘의 세계로 들어가기 위한 몇가지 준비운동을 해봤습니다. 알고리즘에 들어가기 전에 C++ 기초 코스 정도는 마쳐두는게 확실히 도움이 될 것 입니다.

스무디 코딩에서는 누구나 쉽게 배울 수 있는 프로그래밍을 추구합니다. 다만 C++ 과 알고리즘의 학습에 있어서는 좀 진지한 각오가 필요합니다.

C++ 과 알고리즘을 이해하는 것은 컴퓨터의 생태계 그 자체를 직접 다룬다는 것을 의미하므로 기본적으로 타이트한 학습이 필요합니다. C++ 과정의 초기에 이야기했지만 어려운 것을 배우는데는 다 이유가 있고 성취감이나 본인이 가져가는 보상이 다른 언어와는 다른 측면이 있습니다.

static 이고 unmanaged 에 그 의미가 들어있습니다.

이제 몸을 조금 풀어봤으니 다음 학습에는 본격적으로 자료구조부터 알아보겠습니다.

이전 학습

다음 학습

외부참고문서