5. 계산횟수 추정하기 - 완전탐색과 이분법적 탐색
문제해결을 위한 알고리즘 입문
이전 강좌에서는 다항식 함수, 지수함수, 로그함수 등 다양한 함수를 배웠습니다. 여기까지는 수학에 대한 이야기가 주였지만, 이제부터는 알고리즘에 대해 내용으로 넘어가겠습니다. 이번에는 계산량(계산횟수 등)을 추정하는 방법에 대해 설명하고 계산량 평가에서 중요한 "O표기법" 개념을 소개합니다.
⑴ 계산횟수의 중요성
독자는 "컴퓨터"라는 단어를 들었을 때 어떤 이미지를 떠올리시는지요? 인간보다 압도적으로 계산속도가 빨라 다양한 문제를 해결할 수 있는 만능 기계라는 이미지를 떠올리는 사람이 많을 것입니다. 실제로 인간이 1시간이 걸리는 계산을 컴퓨터는 100만분의 1초라는 매우 짧은 시간 안에 끝낼 수 있습니다.
하지만, 컴퓨터의 계산속도에도 한계가 있어, 일반 가정용 컴퓨터의 경우 1초에 약 10억회밖에 계산할 수 없을 것으로 알려져 있으며, 나중에 설명하는 '비효율적인 알고리즘'을 사용하면 데이터 크기가 조금만 커지면 쉽게 계산할 수 있습니다. 횟수가 1경회를 넘어가고 안타깝께도 몇 시간을 기다려도 계산결과가 나오지 않습니다. 그러면 힘들게 만든 장문의 프로그램이 무용지물이 될 것입니다.
따라서, 프로그램을 작성하기 전에 '어느 정도의 계산횟수가 될지', '실제로 실행하면 어느 정도의 시간에 계산이 끝날지'를 평가하는 것이 중요해 집니다.
⑵ 계산횟수란?
계산횟수는 '답이 나오기까지 하는 연산횟수'입니다. 예를 들어, 1 + 2 + 3 + 4 + 5 + 6을 단순히 하나씩 더하는 방식으로 계산할 떄는 아래와 같이 5번 덧셈을 하기 때문에 계산횟수는 5번이 됩니다.
1 + 2 =3 → 3 + 3 = 6 → 6 + 4 = 10 → 10 + 5 = 15 → 15 + 6 = 21
또한 비슷한 방법으로 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8을 계산하면 7회, 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10을 계산하면 9회 덧셈을 하게 됩니다.
이제 문자식을 이용하여 이를 일반화해 봅시다. 정수 N을 알고 있을 떄, 1부터 2N까지의 정수를 모두 더한 값을 구하려면 몇 번 계산이 필요할까요? 앞의 예제처럼 하나씩 더하는 방식으로 계산하면 2N - 1 계산을 수행합니다. 각 N에 대한 계산횟수는 아래와 같습니다.
이렇게 간단한 문제라면 정확한 계산횟수를 알 수 있겠지만, 실제 프로그래밍 문제는 더 복잡하고, 2N - 1의 '-1'이나 'N에 붙은 2'와 같은 디테일한 부분까지 정확하게 추정하는 것은 매우 어렵습니다. 또한, 극한까지 프로그램 속도를 높이려는 경우를 제외하고는 2N번과 3N번의 차이는 그다지 중요하지 않습니다. 그래서 '대략 N번의 계산을 하고 있다'와 같이 대략적인 계산횟수만 추정하는 방법이 있습니다. 이는 이번 강좌의 마지막에서 소개할 '랜도우 O표기법'과 관련되어 있습니다.
⑶ 계산횟수 예시①: 상수 시간
이제부터 계산횟수라는 개념에 익숙해지기 위해 몇 가지 구체적인 예제를 소개합니다.
아래와 같은 문제를 생각해 봅시다.
문제 5-1
이 문제는 정수 N을 입력받아 2 * N + 3의 값을 출력하는 프로그램을 작성하면 해결할 수 있습니다. 이제 프로그램 계산횟수를 계산해 봅시다. 입출력을 제외하면 프로그램은 아래와 같은 계산과정을 수행합니다.
먼저 2 * N을 계산합니다.
1의 결과와 3을 더합니다.
총 2번의 계산을 하고 있지만, 대략적인 횟수만 고려하는 상황에서는 2번이나 1번이나 크게 다르지 않기 떄문에 계산횟수는 '대략 1회'라고 할 수 있습니다. 이런 계산횟수가 되는 알고리즘은 상수시간 알고리즘이라고 하며, 실행시간이 입력데이터에 의존하지 않는 등의 특징이 있습니다.
2N + 3의 값을 출력하는 Python 프로그램
⑷ 계산횟수 예시②: 선형시간
다음 문제를 생각해 봅시다.
문제 5-2
이 문제를 푸는 방법으로는 '1이 X 또는 Y의 배수인지 아닌지', '2가 X 또는 Y의 배수인지 아닌지"...와 같은 식으로 하나씩 알아보고 방법을 생각해 볼 수 있습니다. 이 알고리즘은 아래 코드와 같이 구현할 수 있습니다. 이제 계산 횟수를 이론적으로 계산해 봅시다.
for문 루프의 첨자 i가 취할 수 있는 값은 1, 2, 3, ..., N의 N가지가 있습니다. N, N의 N가지이므로 '계산횟수는 대략 N번이다'라고 할 수 있습니다. 이런 계산횟수가 되는 알고리즘은 (N에 대해) 선형 시간이라고 하며, 입력 데이터 크기가 10배, 100배로 증가하면 실행시간이 약 10배, 100배로 늘어나는 특징이 있습니다. 참고로 단일 for문 루프튼 이런 계산횟수가 되는 경우가 많습니다.
X 또는 Y의 배수 갯수를 출력하는 Python 프로그램
⑸ 계산횟수 예시③: 완전탐색 계산횟수
문제 5-3
이 문제를 푸는데 있어 중요한 지식하나를 알려드립니다. 일반적으로 모든 가능한 패턴을 모두 찾아보는 방법을 완전탐색(Brute-Force Search)이라고 합니다. 완전탐색은 가장 간단한 알고리즘 중 하나이기 때문에, 문제를 풀 때는 먼저 완전탐색을 해도 현실적인 시간 내에 실행이 끝날 수 있는지를 검토하는 것이 중요합니다.
이제 2장의 카드 문제를 완전탐색으로 풀어봅시다. 카드의 쓰기 패턴 수를 N의 공식으로 표현하면,
가지이므로 계산횟수는 '대략
번이다'라고 할 수 있습니다.
가 되는 이유는 아래 그림과 같이 카드 쓰기 패턴을 정사각형으로 배열했을 때의 크기가 N X N이 되는 것을 생각하면 쉽게 이해할 수 있습니다.
여기서 본 문제의 제약조건은 N ≤ 1000이므로, 최대 대략
번의 계산을 수행해야 합니다. 반면에 가정용 컴퓨터의 계산속도는 초당
정도이므로, 아래 코드와 같이 구현하면 이 문제의 실행시간 제한인 2초이내에 프로그램 실행이 완료됩니다. 프로그램 실행시간은 이런식으로 추정할 수 있습니다.
2장의 카드 완전탐색
계산횟수가 대략
회인 알고리즘은 입력데이터의 크기가 10, 1000배로 증가하면 실행시간이 약 100, 10000배로 늘어나는 특징이 있습니다. 아래 표는 N에 대한
의 값을 나타낸 것으로
이상이 되는 부분은 노란색으로,
이상되는 부분은 빨간색으로 처리했습니다. 컴퓨터 계산속도를 고려하면 N=10000 정도라면 1초 이내에 계산이 끝나지만, N = 100000이상이 되면 시간이 오래걸리는 것을 알 수 있습니다. 참고로 이중 for문 루프틑 이런 계산 횟수가 되는 경우가 많습니다.
⑹ 계산횟수 예시④: 완전탐색과 지수시간
문제 5-4
카드 선택방법을 모두 탐색하는 것을 생각해 봅시다. 이 때 조사해야 할 패턴의 수는 얼마나 될까요? 실제로 세어 봅시다.
예를 들어, N = 1인 경우 '카드1을 선택한다', '카드1을 선택하지 않는다'의 2가지를 조사하면 됩니다. 또한, 아래 그림처럼 N=2의 경우 4가지, N=3의 경우 8가지를 조사해야 합니다. 이 정도의 탐색패턴 수라면 수계산으로도 쉽게 문제를 풀수 있을 것입니다.
하지만, 카드수가 조금 늘어나면 패턴수가 급격히 증가합니다. 아래 그림은 N=4,5인 경우의 선택 예시로 N=4인 경우 16가지, N=5인 경우 32가지를 조사해야 합니다. 이 시점에서 수작업으로 문제를 푸는 것은 상당히 번거로울 것입니다. 이제 N이 1씩 증가하면 2→4→8→16→32→…로 2배씩 증가하므로 N에 대한 패턴수는 아래와 같은 식으로 표현할 수 있습니다.
따라서, 이 문제를 완전탐색으로 풀었을 떄의 계산횟수는
라고 할 수 있습니다. 앞에서 설명했던 내용을 토대로
번이 되는 이유는 적분의 법칙을 적용하면 알 수 있지만, 나중에 다루기 때문에 여기서는 다루지 않습니다.
컴퓨터는 매우 빠른 계산을 할 수 있기 때문에 32가지 정도라면 문제가 되지 않습니다. 하지만, N을 더늘려보면 어떨까요? 탐색패턴수는 아래와 같으면 N=30이상에서는 아무리 빠른 컴퓨터라도 '지수함수'앞에서는 속수무책입니다.
그렇다면, 구체적으로 얼마나 시간이 걸릴까? 1초에 109개의 패턴을 조사할 수 있다고 가정하고 계산하면 이 문제의 제약조건의 상한인 N = 60에서는
1년에 액 3200만초가 걸리니 36년 이상 걸려서야 실행이 완료되는 셈입니다. 정말 그런 일이 있을까요? 라고 생각하는 독자가 있다면 필자가 올린 예시를 통해 작성해보면 N=40의 시점에서 전혀 답이 나오지 않을 것입니다. 이런 상황에서는 동적계획법을 사용하는 알고리즘을 효율화할 필요가 있습니다.
⑺ 계산횟수 예시⑤: 이분탐색과 대수시간
앞에서 계산시간이 오래 걸리는 알고리즘의 예를 소개했지만, 그 반대의 경우도 있습니다. 다음 문제를 생각해 봅시다.
바로 떠올릴 수 있는 방법으로는 "1이하입니까?", "2이하입니까?", "3이하입니까?"등 순서로 Yes가 돌아올 때까지 질문하는 방법입니다. 예를 들어, "6이하입니까?"라는 질문에서 처음으로 Yes가 나온다면, 그 대답은 6이라는 것을 알 수 있습니다. 이 알고리즘을 선형탐색법이라고 합니다.
하지만, 이 방법은 효율성이 떨어지고, 예를 들어 홍길동이 떠올린 숫자가 8이라면 아래 그림처럼 8번 질문이 필요합니다.
그래서 우선 "4이하입니까?"라는 선택지의 중간에 구분하는 질문을 던지는 것을 생각해 봅시다. 그러면 Yes/No 중 어느 쪽이 나오더라도 처음 8가지 선택지가 4가지로 좁혀집니다.
Yes의 경우: 답은 1, 2, 3, 4중 하나임을 알 수 있습니다.
No의 경우: 답이 5, 6, 7, 8중 하나임을 알 수 있습니다.
두번째 이후의 질문에 대해서는 다음 그림과 같이 '선택지를 반으로 나누는 질문'을 반복하면 선택지의 수가 8→4→2→1로 줄어들어 어떤 경우라도 3번의 질문으로 답을 맞출 수 있게 됩니다. 이런 방법을 이분탐색법이라고 합니다.
이제 문제 설정을 조금 일반화해 봅시다. 홍길동이 1이상 N이하의 정수를 떠올렸을 때 계산 횟수는 어떻게 될까요? 우선 간단한 예시로 비부정수(음수가 아닌 정수)B를 사용하여
와 같이 줄어들기 때문에 질문 횟수는 B회이며,
이므로 질문횟수를 N의 공식으로 표현하면
이 됩니다.
처음소개한 N = 8 예시에서는 질문 횟수가
회가 되는 것을 확인할 수 있습니다.
그렇다면, N이
의 형태로 표현되지 않는 경우는 어떨까요? 사실 질문횟수가
회가 되는 것으로 알려져 있으며 각 N에 대한 질문횟수는 다음과 같으며, N = 10000000까지 늘려도 여전히 20번 질문만 필요합니다. 로그함수
은 증가속도가 느려 계산횟수로는 매우 효율적입니다.
⑻ Landau의 O표기법 도입
지금까지 다양한 계산횟수에 대해 소개하면서 아래와 같은 표현을 사용했습니다.
'대략'이라는 단어를 사용하지 않고도 Landau의 O기법을 사용하여 표현할 수 있습니다. 예를 들어, 앞에서 설명했던 알고리즘의 경우 '대략 N번' 대신 '이 알고리즘의 계산량은 O(N)번입니다.' 또는 '이 알고리즘은 O(N)시간으로 동작한다'라고 표현할 수 있습니다. 상당히 난이도가 높지만 엄밀하게 설명하면 아래와 같습니다.
그러나, 실용적으로는 이런 어려운 것을 생각할 필요가 없습니다. 대부분의 경우 계산량 T(N)을 나타내는 O기법의 내용 P(N)은 다음과 같은 절차에 의해 결정됩니다.
N이 큰 값이 되었을 떄 T(N) 중 가장 중요한 항을 제외한 나머지 항을 지웁니다.
상수배를 지웁니다.
최종적으로 남은 것이 내용 P(N)입니다.
예를 들어, 계산횟수가
인 경우 각 항의 값은 아래와 같습니다.
분명히
항이 계산횟수의 병목현상이 발생합니다. 이것이 N보다
가 더 중요한 이유입니다. 다른 경우도 마찬가지입니다. 다음은 3가지 구체적인 예제에 대해 계산량을 O기법으로 표현하는 과정을 아래와 같이 설명합니다. 참고로 계산량 오더에 내용에 대수함수가 포함된 경우, 관례적으로 O(log N)과 같이 바닥을 생략한 형태로 쓰는 경우가 많습니다.
⑼ 계산량 및 알고리즘 예시
아래 표는 이 강좌에서 다루는 알고리즘을 포함한 대표적인 알고리즘을 계산량별로 정리한 표입니다. 다양한 성능을 가진 알고리즘이 있음을 알 수 있습니다.
⑽ 계산량 관련 주의사항
마지막으로 계산량과 관련된 몇가지 주의사항을 정리합니다.
시간 계산량과 영역 계산량
계산량을 평가하는 방법으로는 알고리즘의 계산횟수를 의미하는 시간계산량과 처리하는 메모리 사용량을 의미하는 영역 계산량 2가지가 자주 사용됩니다. 예를 들어, 입력 데이터의 크기 N에 대해 대략
바이트의 메모리를 사용하는 경우, '이 알고리즘의 영역 계산량은
이다'라고 말합니다. 이 강좌에서는 단순히 계산량이라고 표시할 때는 시간계산량을 의미합니다.
최악의 계산량과 평균 계산량
입력데이터의 크기가 같더라도 경우에 따라서는 계산횟수가 전혀 다른 경우가 있습니다. 또한 난수를 이용한 알고리즘의 경우 난수의 운에 따라 계산횟수가 변동하는 경우도 있습니다. 그래서 일반적으로 가장 나쁜 경우의 계산시간을 추정하는 경우가 많은데, 이를 최악의 계산량이라고 합니다. 한편 평균적인 경우의 계산량을 평균 계산량이라고 합니다. 대부분의 알고리즘에서 평균 계산량과 최악의 계산량은 일치합니다.
여러 변수가 병목현상이 발생하는 경우
계산량은 여러 변수가 병목현상이 될 수 있습니다. 예를 들어, 1부터 N까지의 합을 계산한 후, 1부터 M까지의 합을 계산하는 문제를 생각해 봅시다. 하나씩 더했을 때 계산횟수는 N+M-2회이지만, N, M 모두 병목현상이 발생할 수 있으므로 O(N + M)시간이라고 표기합니다.
⑾ 연습문제
문제 5-1
문제 5-2
다음 프로그램의 계산량을 O기법으로 표현해 주세요.
문제 5-3
문제 5-4
알고리즘 D를 구현한 프로그램을 N = 10, 12, 14, 16, 18, 20으로 실행해보니 다음 표와 같은 실행시간이 나왔습니다. 알고리즘 D의 계산량은 어느 정도일까요? 여기서 N은 데이터의 크기(예: 카드 갯수)라고 가정합니다.
문제 5-5
어떤 사전에는 약 10만개의 단어가 사전순으로 나열되어 있습니다. 이 사전에서 특정 단어를 찾고 싶을 때, 예를 들어, a → aardvark → aback → abacus → abalone → abandon →…와 같이 단어를 하나하나 찾아보면 시간이 많이 걸립니다. 어떤 방법을 사용하면 효율적일지 생각해 봅시다. (힌트: 이분법)
© 2024 ZeR0, Hand-crafted & made with Damon JW Kim.
Profile: https://gaebal.site
AI/LLM개발 및 강의/컨설팅 문의: https://naver.me/GalVgGKH
