알고리즘 학습

1장. 문제 해결

이 작품은 AI를 사용하여 번역되었습니다. 여러분의 피드백과 의견을 환영합니다: [e-mail]

이 장에서는 학습 내용을 살펴봅니다:

• 입문 문제를 해결하는 여러 알고리즘.

• N 크기의 문제 인스턴스에서 알고리즘의 성능을 고려하는 방법.

• 주어진 문제 인스턴스를 풀 때 키 연산이 호출된 횟수를 계산하는 방법입니다.

• 문제 인스턴스의 크기가 두 배가 될 때 증가 순서를 결정하는 방법.

• 알고리즘이 N 크기의 문제 인스턴스에서 실행하는 키 연산 수를 세어 시간 복잡도를 추정하는 방법.

• N 크기의 문제 인스턴스에서 알고리즘에 필요한 메모리 양을 결정하여 공간 복잡도를 추정하는 방법.

시작해보자!

알고리즘이란 무엇인가요?

알고리즘의 작동 원리를 설명하는 것은 이야기를 들려주는 것과 같습니다. 각 알고리즘은 일반적인 솔루션을 개선하는 새로운 개념이나 혁신을 도입합니다. 이 장에서는 알고리즘의 성능에 영향을 미치는 요소를 설명하기 위해 간단한 문제에 대한 몇 가지 해결책을 살펴봅니다. 그 과정에서 알고리즘의구현과 무관하게 알고리즘의 성능을 분석하는 데 사용되는 기술을 소개하지만, 항상 실제 구현에서 얻은 경험적 증거를 제시할 것입니다.

참고

알고리즘은 예측 가능한 시간 내에 올바른 결과를 반환하는 컴퓨터 프로그램으로 구현된 단계별 문제 해결 방법입니다. 알고리즘에 대한 연구는 정확성(이 알고리즘이 모든 입력에 대해 작동하는가?)과 성능(이 문제를 해결하는 가장 효율적인 방법인가?) 모두와 관련이 있습니다.

문제 해결 방법의 예를 통해 이것이 실제로 어떤 모습인지 살펴봅시다. 정렬되지 않은 목록에서 가장 큰 값을 찾고자 한다면 어떻게 해야 할까요? 그림 1-1의 각 Python 목록은문제 인스턴스, 즉 알고리즘에 의해 처리된 입력(원통형으로 표시)이며, 정답은 오른쪽에 표시됩니다. 이 알고리즘은 어떻게 구현될까요? 다른 문제 인스턴스에서 어떻게 작동할까요? 백만 개의 값 목록에서 가장 큰 값을 찾는 데 필요한 시간을 예측할 수 있나요?

그림 1-1. 알고리즘이 처리하는 세 가지 문제 사례

알고리즘은 단순한 문제 해결 방법 그 이상입니다. 프로그램은 예측 가능한 시간 내에 완료되어야 합니다. 기본 제공 Python 함수 max() 는 이미 이 문제를 해결합니다. 이제 임의의 데이터가 포함된 문제 인스턴스에서 알고리즘의 성능을 예측하기 어려울 수 있으므로 신중하게 구성된 문제 인스턴스를 식별하는 것이 좋습니다.

표 1-1은 목록에 오름차순 정수가 포함된 경우와 내림차순 정수가 포함된 경우의 두 가지 종류의 문제 인스턴스에 대해 max() 시간을 측정한 결과를 보여줍니다. 컴퓨팅 시스템 구성에 따라 표에서 다른 결과가 나올 수 있지만, 다음 두 문장을 확인할 수 있습니다:

• 오름차순 값의 ...