..

Search

73) 알고리즘

73) 알고리즘

알고리즘


STL 알고리즘 함수

STL의 목적은 일반적인 알고리즘에 대한 효율적인 구현을 제공하는 것입니다.

따라서 STL은 이러한 알고리즘을 STL 알고리즘 함수나 STL 컨테이너의 멤버 함수를 사용하여 구현하고 있습니다.

 

STL 컨테이너는 반드시 필요한 기능만을 포함하고 있으며, 동작하는데 필요한 모든 기능을 가지고 있지는 않습니다.

따라서 STL 컨테이너는 알고리즘을 제공하는 많은 전역 함수와 함께 사용해야만 제 기능을 발휘할 수 있습니다.

이렇게 제공되는 STL 알고리즘 함수는 반복자를 통해 임의의 컨테이너에 같은 방법으로 적용됩니다.

 

대부분의 알고리즘 함수는 algorithm 헤더 파일과 numeric 헤더 파일에 정의되어 있습니다.


STL 알고리즘의 분류

STL 알고리즘은 기능별로 다음과 같이 구분할 수 있습니다.

 

1. 읽기 알고리즘(algorithm 헤더 파일)

2. 변경 알고리즘(algorithm 헤더 파일)

3. 정렬 알고리즘(algorithm 헤더 파일)

4. 수치 알고리즘(numeric 헤더 파일)


읽기 알고리즘

STL 읽기 알고리즘 함수는 컨테이너를 변경하지 않으며, 컨테이너의 지정된 범위에서 특정 데이터를 읽기만 하는 함수입니다.

STL에서 제공하는 대표적인 읽기 알고리즘 함수는 다음과 같습니다.

 

1. find()

2. for_each()

 

find() 함수는 두 개의 입력 반복자로 지정된 범위에서 특정 값을 가지는 첫 번째 요소를 가리키는 입력 반복자를 반환합니다.

for_each() 함수는 두 개의 입력 반복자로 지정된 범위의 모든 요소를 함수 객체에 대입한 후, 대입한 함수 객체를 반환합니다.


변경 알고리즘

STL 변경 알고리즘 함수는 컨테이너를 변경하지 않으며, 컨테이너의 지정된 범위에서 요소의 값만을 변경할 수 있는 함수입니다.

STL에서 제공하는 대표적인 변경 알고리즘 함수는 다음과 같습니다.

 

1. copy()

2. swap()

3. transform()

 

copy() 함수는 두 개의 입력 반복자로 지정된 범위의 모든 요소를 출력 반복자가 가리키는 위치에 복사합니다.

swap() 함수는 두 개의 참조가 가리키는 위치의 값을 서로 교환합니다.

transform() 함수는 두 개의 입력 반복자로 지정된 범위의 모든 요소를 함수 객체에 대입한 후, 출력 반복자가 가리키는 위치에 복사합니다.


정렬 알고리즘

STL 정렬 알고리즘 함수는 컨테이너의 지정된 범위의 요소들이 정렬되도록 컨테이너를 변경하는 함수입니다.

모든 정렬 알고리즘 함수는 올바른 정렬을 위해 임의 접근 반복자를 사용합니다.

따라서 임의 접근이 가능한 컨테이너만이 사용할 수 있습니다.

 

STL에서 제공하는 대표적인 정렬 알고리즘 함수는 다음과 같습니다.

 

1. sort()

2. stable_sort()

3. binary_search()

 

sort() 함수는 두 개의 임의 접근 반복자로 지정된 범위의 모든 요소를 서로 비교하여, 오름차순으로 정렬합니다.

stable_sort() 함수는 두 개의 임의 접근 반복자로 지정된 범위의 모든 요소를 서로 비교하여, 값이 서로 같은 요소들의 상대적인 순서는 유지하면서 오름차순으로 정렬합니다.

binary_search() 함수는 sort() 함수를 사용하여 오름차순으로 정렬한 후에, 전달된 값과 같은 값이 있으면 참(true)을 반환하고 없으면 거짓(false)을 반환합니다.


수치 알고리즘

수치 알고리즘 함수는 다른 알고리즘 함수와는 달리 numeric 헤더 파일에 정의되어 있습니다.

대표적인 수치 알고리즘 함수는 다음과 같습니다.

 

1. accumulate()

 

accumulate() 함수는 두 개의 입력 반복자로 지정된 범위의 모든 요소의 합을 반환합니다.


연습문제