[이산수학] 알고리즘을 통한 문제 해결

알고리즘을 통해 여러 문제를 해결하는 방법을 알아보고 해당 문제들이 실생활에 적용되는 방법을 알아보기

알고리즘?

알고리즘

알고리즘이란 특정한 일을 수행하는 명령어들의 유한 집합

수학에서는 문제를 풀기 위해 정의나 정리를 활용 = 컴퓨터에서는 수행 가능한 효율적인 알고리즘 사용

주어진 문제를 해결하기 위해 필요한 여러 가지 단계들을 체계적으로 명시해 놓은 것 → ‘어떤 문제를 해결하는 한 방법의 상세한 특징을 기술하는 것’

알고리즘의 7가지 주요 특성

1. 입력 : 문제를 풀기 위한 입력
2. 출력 : 문제를 해결했을 때 답이 나와야함
3. 유한성 : 유한 번의 명령이 수행된 이후에는 끝이 나야함
4. 정확성 : 주어진 문제를 정확하게 해결해야 함
5. 확정성 : 각 단계가 실행된 후에는 결과가 확정됨
6. 일반성 : 같은 유형의 문제에 모두 적용
7. 효율성 : 정확하면서 효율적이어야함

순서도, 유사코드, 언어 등 여러 가지 방법으로 표현 가능

→ 대신 누구나 이해할 수 있도록 명확하게 기술하는 것이 중요

어떤 문제에 대한 알고리즘은 여러 가지가 있을 수 있으며 컴퓨터 프로그램의 경우에는 어떤 알고리즘이 가장 효율적인지 선택해야함

수행 시간, 메모리 용량, 자료의 종류, 프로그래머의 성향에 따라 알맞은 알고리즘 선택

알고리즘의 효율성

알고리즘의 효율성을 비교하기 위해 일반적인 계산과는 다르게 for 문을 이용하여 해당 문제 해결의 방법이 다른 문제에도 적용이 가능해짐 → 효율적

알고리즘 분석

알고리즘에 대한 평가와 비교는 컴퓨터 프로그램을 통한 문제 해결에 있어서 매우 중요한 관심 분야

1. 어떤 문제의 해결에 있어서 주어진 알고리즘을 사용하는 데 드는 비용이 얼마인가 ?
2. 그 문제를 해결하는 데 비용이 가장 적게 드는 알고리즘은 무엇인가?

→ 여기서 비용은 연산하는 데 필요한 시간과 장소의 크기

주어진 문제를 해결하는 방법에서 비용이 가장 적게 드는 알고리즘을 찾기 위해 효율성 분석이 필요

알고리즘 수행 시 시간 복잡성과 공간 복잡성의 두 가지 요소를 검토

알고리즘의 복잡성

빅오

빅오 표현을 사용하여 알고리즘의 복잡성을 측정

O를 사용하여 표시하여 사용

O(1)<O(log2n)<O(n)<O(n log2n)<O(n^2)<O(n^3)<…<O(2^n)<O(n!)

재귀 함수의 복잡성

재귀 함수를 이용하여 주어진 문제를 해결할 경우의 복잡성 → 그 전에 있던 함수에 영향을 받음

→ 해당 함수의 복잡성을 통해 재귀 함수의 복잡성을 구할 수 있음

탐색 알고리즘

탐색

주어진 파일 또는 원소들 중에서 어떤 특정한 원소를 찾는 것

→ 순차 탐색과 이진 탐색을 통해 찾을 수 있음

순차 탐색

해당 배열에 있는 특정한 원소를 찾기 위하여 배열의 처음 원소부터 차례로 모든 원소를 비교하여 탐색 → O(n)의 시간 복잡도

이진 탐색

배열 가운데의 원소 값과 찾으려는 값을 비교하여 비교된 결과에 따라 왼쪽 원소의 배열 또는 오른쪽 원소의 배열 중에서 다시 찾기를 계속함 → O(log2n)의 시간 복잡도

분할 정복 알고리즘

전체 집합을 찾으려는 원소와 비교하여 부분 집합으로 나누어 찾는 알고리즘으로 큰 문제를 작은 문제로 나누어 해결이 가능함

정렬 알고리즘

정렬

정렬은 임의로 나열되어 있는 데이터들을 주어진 항목에 따라 크기 순서대로 늘어놓는 것

해당 알고리즘 수행 후에 다른 작업에 응용이 가능함 → 데이터 탐색 / 항목 비교

버블 정렬

이웃한 두 개의 원소를 비교하여 순서가 서로 다르면 원소의 자리를 바꾸고 그렇지 않으면 그 위치에 그대로 놓음 → O(n^2)

퀵 정렬

모든 정렬 방법 중에서 평균 수행 시간이 가장 빠른 방법

피벗 키를 기준으로 원소를 두 부분으로 나누고 나누어진 부분에서 다시 퀵 정렬로 재귀하면서 정렬을 수행

평균 수행시간은 O(nlog2n)이며 최악의 경우가 O(n^2)

병합 정렬

크기가 1인 정렬된 두 파일을 병합하여 크기가 2인 파일들을 생성함 이때 하는 병합 과정을 반복하여 한 개의 파일을 만들어내는 방법

두 개의 서로 다른 정렬된 배열을 합하여 하나의 정렬된 배열로 만드는 병합 방식은 2-way 병합 과정

평균 수행시간은 O(nlog2n)

힙 정렬

자료를 정리할 때 모든 자료들을 동시에 처리하지 않고 모든 자료 중에서 가장 큰 자료를 찾아 출력

→ 나머지 자료 중에서 앞의 과정을 반복하여 가장 큰 자료를 찾아 출력시키며 정렬하는 방법

평균 수행 시간은 O(nlog2n)

이처럼 알고리즘을 통해 문제 해결을 할 수 있으며 컴퓨터의 프로그램에 적용되는 사례를 알아보았음