brunch

연재 중 알고리즘과 수학 01화

라이킷 10 댓글

You can make anything
by writing

C.S.Lewis

계정을 잊어버리셨나요?

by ZeRO Nov 23. 2024

1. 알고리즘과 수학의 관계

문제해결을 위한 알고리즘 입문

⑴ 알고리즘이란?

알고리즘은 '문제를 해결하기 위한 절차'를 의미합니다. 한글 4글자로 되어 있어 다소 추상적이고 어려운 단어처럼 느껴질 수 있지만, 사실 매우 친숙한 단어입니다. 1부터 100까지의 정수를 모두 더하는 문제를 예로 들어봅시다.

① 알고리즘 예시㉠ : 하나하나 더하는 방법　

가장 간단한 방법은 아래 그림과 같이 '1 + 2 = 3', '3 + 3 = 6', '6 + 4 = 10'...과 같이 하나씩 더하는 방법입니다. 초등학교 3학년이 배우는 덧셈을 반복하는 것일 뿐인데, 이것도 훌륭한 알고리즘입니다. 하지만 이 방법으로 계산기를 사용하지 않고 계산을 해보면 99번의 덧셈을 해야 하는데, 계산을 잘하는 사람이라도 5~10분 이상은 걸릴 것입니다.

② 알고리즘 예시㉡ : 변형을 통해 한번에 계산방법

다음으로 다른 알고리즘(계산 절차)을 생각해 봅시다. 1부터 100까지의 숫자는 '1과 100', '2와 99', '3과 98'... '50과 51'... '50과 51'과 같이 '총합이 101이 되는 50쌍의 쌍'으로 분해할 수 있습니다. 그러면 구하고자 하는 답이 101 × 50 = 5050이라는 것을 쉽게 알 수 있습니다. 산수 '공식'의 형태로 표현하면,

1 + 2 + 3 +4 + ... + 100

= (1 + 100) + (2 + 99) + (3 + 98) + (4 + 97) + ... + (50 + 51)

= 101 + 101 + 101 + 101 + ... + 101

= 101 x 50

= 5050

가 됩니다. 알고리즘 예시 ㉠에서는 99번의 계산이 필요했던 것을 '101 × 50' 한 번으로 줄일 수 있으므로, 이 알고리즘이 더 효율적인 알고리즘이라고 할 수 있습니다.

③ 다양한 문제를 해결하는 알고리즘이 있다!

지금까지 다룬 것은 간단한 계산 문제이지만, 알고리즘의 적용 범위는 훨씬 더 넓습니다. 예를 들어 다음과 같이 생활 속 다양한 문제를 풀 수 있습니다.

강남역에서 종로역까지의 최단 경로를 구하기

5000원 이내의 쇼핑으로 가장 많은 칼로리를 섭취할 수 있는 방법 찾기

일정 기간 동안 유원지의 총 입장객 수를 빠르게 계산하기

기말고사 결과를 성적순으로 정렬하기

가장 적은 장수의 지폐로 대금을 지불하는 방법을 구하기

가능한 한 많은 영화를 볼 수 있는 방법을 구하기

사전에서 “technology”의 의미를 찾아보기

특히 마지막 사전의 예는 친숙합니다. 예를 들어 첫 페이지부터 'a→aardvark→aback→abacus→abalone→abandon→...'과 같이 단어를 하나하나 찾아보면 technology를 찾는데 수십 분이 걸립니다. 따라서 효율적인 검색을 위해 '어느 정도 위치를 예측하여 검색 범위를 좁혀가면서 검색하기' 등의 방법을 사용할 수 있습니다.

④ 알고리즘의 개선이 중요하다!

알고리즘은 세상의 문제를 해결하기 위해 필요하지만, 모든 알고리즘이 다 좋은 것은 아닙니다. 예를 들어 이번 첫 번째 '알고리즘 예시㉠'과 같이 비효율적인 알고리즘은 많은 데이터를 처리하는 데 시간이 오래 걸립니다. 현대의 컴퓨터는 사람보다 훨씬 빠르게 계산을 할 수 있지만, 이 또한 한계가 있습니다. 예를 들어, 일반 PC의 경우 (측정 방법이나 연산 종류에 따라 다르지만) 초당 10억 번 정도밖에 계산할 수 없습니다. 이렇게 빠르게 계산할 수 있다면 어떤 문제도 순식간에 풀 수 있을 것 같지만, 꼭 그렇지는 않습니다.

☞ 계산 횟수의 “폭발”　

계산 횟수가 매우 커지는 예로는 다음과 같은 문제를 들 수 있습니다. 간단한 방법으로 모든 선택지를 순서대로 시도해 보는 방법을 생각해 볼 수 있습니다.

비슷한 문제를 나중에서 다루기 때문에 지금 당장 이해할 필요는 없지만, 물건의 수가 하나 늘어나는 것만으로도 선택 방법의 수는 2배가 됩니다. 그리고 물품이 60개가 되면 선택 방법은 115경개(1조 1150000배) 이상이 되며, 이를 모두 조사하는 것은 매우 힘들어집니다.

☞ 더 나은 알고리즘으로 개선하는 것이 중요하다!

이러한 문제에서는 컴퓨터의 계산 속도 한계를 쉽게 넘어설 수 있습니다. 따라서 더 적은 계산 횟수로 동일한 결과를 얻을 수 있는 알고리즘으로 개선하는 것이 요구되는 경우가 있습니다. 세상의 많은 문제들은 이미 알려진 알고리즘을 적용하면 효율적으로 풀 수 있기 때문에 전형적인 알고리즘을 학습하는 것이 중요합니다.

⑵ 알고리즘에 수학이 필요한 이유

앞서 알고리즘과 그 중요성에 대해 알아보았다. 하지만 알고리즘을 배우기 위해서는 전제되는 수학적 지식과 수학적 고찰도 중요합니다. 이번에는 수학이 중요한 이유를 세 가지로 나누어 설명하겠습니다.

① 알고리즘 이해와 수학

먼저 알고리즘 자체를 이해하기 위해서는 수학이 필요합니다. 친숙한 예로 '원주율 π ≒ 3.14의 값을 가능한 한 좋은 정확도로 구하라'는 문제를 생각해봅시다.　

사실 한 변이 1cm인 정사각형 영역 위에 무작위로 점을 찍고, 왼쪽 아래쪽 모서리를 중심으로 반경 1cm의 원 안에 들어간 점의 비율에 4를 곱하면 원주율의 근사치를 계산할 수 있습니다. 예를 들어 아래 그림의 경우 20개 중 16개가 원 안에 들어갔으므로 계산되는 값은 16 ÷ 20 × 4 = 3.2로 거의 정확하게 계산됩니다.

그런데 왜 이렇게 간단한 알고리즘으로 거의 정확한 값을 계산할 수 있는 것일까요? 그 이유를 이해하기 위해서는 수학의 한 분야인 통계학의 기본을 알아야 합니다. 이 강좌에서 배우는 다른 알고리즘에 대해서도 마찬가지입니다. 예를 들어 동적 계획법의 배경에는 '수열의 점증식'이 있고, 너비 우선 탐색의 배경에는 '그래프 이론'이 있습니다.

② 알고리즘 성능 평가와 수학

다음으로 알고리즘의 성능을 추정하기 위해서는 '계산 횟수' 혹은 '계산량'이라는 개념이 중요한데, 이를 이해하기 위해서도 수학이 필요합니다. 예를 들어 앞서 소개한 '1부터 100까지의 정수를 모두 더하세요'라는 문제를 다루었습니다. 그리고 하나씩 더하면 99번의 계산이 필요해 비효율적이라는 것을 설명했습니다. 이를 '1부터 1000까지의 정수를 모두 더하세요'라는 문제로 바꾸면, 하나씩 더하면 999번의 계산이 필요합니다. 하지만 많은 프로그래밍 문제에서는 100이나 1000뿐만 아니라 어떤 경우에도 올바르게 동작해야 하기 때문에 100이나 1000이라는 숫자를 N으로 바꾸어 '1부터 N까지의 정수를 모두 더하세요'와 같은 형태로 문제를 작성하는 경우도 있습니다. 이때 계산 횟수를 N의 수식으로 표현하면 N- 1회가 되는데, 이 때 중학교에서 배우는 문자 수식과 함수를 사용합니다.

또한, 지금 당장 이해할 필요는 없지만, 앞에서 소개한 알고리즘에 따라 계산횟수가 2N과 같은 지수함수, log N과 같은 로그함수가 될 수 있습니다. 이는 고등학교에 가면서 배우는 내용이지만, 알고리즘을 잘 활용하기 위해서는 증가속도등 각각의 특징도 이해해야 합니다.

③ 논리적 사고력과 수학

더 나은 알고리즘을 생각해내는 능력을 향상시키기 위해서는 사물을 논리적으로 사고하는 논리적 사고력과 고찰력이 필요합니다. 예를 들어 앞에서 소개한 계산 문제에서는 '합이 101이 되는 쌍으로 나누기'와 같은 고민이 필요했습니다. 그 외에도 아래 그림과 같이 수를 블록으로 간주하고 적절히 등적분 변형을 하는 등의 고민을 사용할 수도 있습니다.