18.1 — 선택 정렬(Selection sort)을 이용한 배열 정렬
정렬이 필요한 이유
배열 정렬이란 배열 안에 있는 데이터들을 특정한 순서대로 보기 좋게 나열하는 과정을 말합니다. 정렬은 우리가 컴퓨터를 사용하는 일상생활 곳곳에서 아주 유용하게 쓰이고 있어요. 예를 들어, 이메일 프로그램은 보통 가장 최근에 받은 메일을 먼저 보여주기 위해 시간순으로 이메일을 정렬합니다. 연락처 목록을 볼 때는 이름이 가나다순이나 알파벳순으로 정렬되어 있죠? 그래야 원하는 사람의 이름을 찾기 훨씬 쉬우니까요. 이렇게 화면에 정보를 띄워주기 전에 데이터를 미리 찾기 쉽게 다듬는 것이 바로 정렬의 역할입니다.
정렬은 사람뿐만 아니라 컴퓨터가 데이터를 검색할 때도 훨씬 빠르고 효율적으로 일할 수 있게 도와줍니다. 이름 목록에서 특정 이름이 있는지 확인해야 하는 상황을 상상해 볼까요? 만약 이름이 뒤죽박죽 섞여 있다면, 컴퓨터는 그 이름이 있는지 확인하기 위해 배열의 처음부터 끝까지 하나하나 전부 다 검사해야만 합니다. 데이터가 엄청나게 많다면 이 작업은 시간이 아주 오래 걸리고 힘든(비용이 많이 드는) 작업이 될 거예요.
하지만 이제 이름들이 알파벳순으로 예쁘게 정렬되어 있다고 생각해 보세요. 이 경우에는 우리가 찾는 이름보다 알파벳 순서가 더 뒤에 있는 이름을 마주치는 순간, 검색을 바로 멈추면 됩니다! 그 뒤에 남은 이름들은 전부 우리가 찾는 이름보다 알파벳 순서가 늦을 것이 확실하기 때문에, 굳이 끝까지 찾아볼 필요조차 없는 것이죠.
사실 이렇게 이미 정렬된 배열 안에서 데이터를 찾는 데는 훨씬 더 훌륭하고 똑똑한 방법들이 존재합니다. 아주 간단한 검색 방법만 사용하더라도 100만 개나 되는 데이터 속에서 단 20번만 값을 비교해보고 원하는 것을 찾아낼 수 있을 정도니까요! 물론 단점도 있습니다. 애초에 흩어진 배열을 순서대로 '정렬'하는 작업 자체가 컴퓨터에게는 꽤 번거로운 일입니다. 그래서 데이터를 여러 번 반복해서 검색해야 하는 상황이 아니라면, 검색 한 번 빨리 하겠다고 굳이 정렬을 먼저 하는 것은 오히려 손해일 수도 있습니다.
어떤 경우에는 정렬을 해두는 것만으로도 아예 '검색' 자체가 필요 없어지기도 합니다. 학생들의 시험 점수 중에서 가장 높은 1등 점수를 찾는다고 해볼까요? 점수가 막 섞여 있다면 모든 점수를 다 훑어봐야 1등 점수를 알 수 있습니다. 하지만 이미 점수가 순서대로 정렬되어 있다면, 그냥 맨 앞자리나 맨 뒷자리(오름차순이냐 내림차순이냐에 따라 다름)만 쏙 확인하면 끝납니다. 찾고 자시고 할 것도 없죠!
정렬은 어떻게 이루어질까?
정렬은 보통 두 개의 데이터를 짝지어 서로 비교해 본 다음, 우리가 정해둔 기준에 맞지 않으면 두 데이터의 위치를 서로 바꾸는(swap) 과정을 계속 반복하면서 이루어집니다. 어떤 정렬 방식을 선택하느냐에 따라 이 데이터들을 비교하는 순서가 달라지고, 어떤 순서로 정렬할지
(예: 작은 것부터 큰 것으로 가는 오름차순, 큰 것부터 작은 것으로 가는 내림차순)에 따라 자리를 바꾸는 기준이 달라집니다.
C++에서는 두 데이터의 자리를 바꿀 때, C++ 표준 라이브러리의 <utility> 헤더에 미리 만들어져 있는 std::swap()이라는 함수를 아주 편리하게 사용할 수 있습니다.
#include <iostream>
#include <utility>
int main()
{
int x{ 2 };
int y{ 4 };
std::cout << "Before swap: x = " << x << ", y = " << y << '\n';
std::swap(x, y); // x와 y의 값을 서로 바꿉니다.
std::cout << "After swap: x = " << x << ", y = " << y << '\n';
return 0;
}
이 프로그램을 실행하면 화면에 다음과 같이 출력됩니다:
Before swap: x = 2, y = 4
After swap: x = 4, y = 2
std::swap()을 거치고 난 후, x와 y가 가진 값이 서로 완벽하게 맞바뀐 것을 볼 수 있습니다!
선택 정렬 (Selection sort)
배열을 정렬하는 방법은 아주 여러 가지가 존재합니다. 그중에서도 선택 정렬(Selection sort)은 아마도 정렬 방법 중에서 가장 이해하기 쉬운 녀석일 것입니다. 비록 속도는 다른 정렬 방법들에 비해 조금 느린 편이지만, 작동 원리가 매우 직관적이라서 초보자들에게 정렬의 개념을 가르칠 때 아주 좋은 교재가 됩니다.
선택 정렬을 이용해서 숫자를 가장 작은 것부터 가장 큰 것 순서(오름차순)로 줄 세우는 과정은 다음과 같습니다:
- 배열의 맨 처음(인덱스 0)부터 시작해서 끝까지 쭉 훑어보며 가장 작은 값을 찾습니다.
- 찾은 가장 작은 값을 배열의 맨 첫 번째 자리(인덱스 0)에 있는 값과 서로 자리를 바꿉니다.
- 이제 첫 번째 자리는 완성되었으니 신경 쓰지 말고, 그다음 자리(인덱스 1)부터 시작해서 위 1번과 2번의 과정을 남은 배열 끝까지 계속 반복합니다.
쉽게 말해, 전체에서 제일 작은 녀석을 골라내서 맨 앞에 갖다 놓고, 남은 애들 중에서 제일 작은 녀석을 골라내서 두 번째 자리에 갖다 놓는 작업을 계속하는 거예요. 데이터가 바닥날 때까지 말이죠!
5개의 숫자가 들어있는 배열을 통해 이 과정이 어떻게 진행되는지 직접 눈으로 따라가 봅시다. 처음 배열의 상태입니다.
{ 30, 50, 20, 10, 40 }
먼저, 첫 번째 자리(인덱스 0)부터 시작해서 제일 작은 숫자를 찾습니다.
{ 30, 50, 20, 10, 40 } (여기서 제일 작은 숫자는 10이네요!)
이 제일 작은 숫자 10을 첫 번째 자리(인덱스 0)에 있던 30과 서로 바꿉니다:
{ 10, 50, 20, 30, 40 }
이제 맨 앞자리(10)는 제대로 된 주인을 찾았으니 무시해도 좋습니다. 남은 숫자들 중 두 번째 자리(인덱스 1)부터 시작해서 제일 작은 숫자를 찾습니다:
{ 10, 50, 20, 30, 40 } (남은 애들 중 제일 작은 숫자는 20이네요!)
이 20을 두 번째 자리(인덱스 1)에 있던 50과 자리를 바꿉니다:
{ 10, 20, 50, 30, 40 }
이제 앞의 두 자리 정렬이 끝났습니다. 세 번째 자리(인덱스 2)부터 시작해서 제일 작은 숫자를 또 찾습니다:
{ 10, 20, 50, 30, 40 } (이번엔 30이 제일 작네요!)
30을 세 번째 자리(인덱스 2)에 있던 50과 바꿉니다:
{ 10, 20, 30, 50, 40 }
네 번째 자리(인덱스 3)부터 남은 숫자 중 제일 작은 것을 찾습니다:
{ 10, 20, 30, 50, 40 } (40이 제일 작습니다!)
40을 네 번째 자리(인덱스 3)에 있던 50과 바꿉니다:
{ 10, 20, 30, 40, 50 }
마지막으로 다섯 번째 자리(인덱스 4)에서 가장 작은 숫자를 찾습니다:
{ 10, 20, 30, 40, 50 } (혼자 남은 50이네요)
50을 다섯 번째 자리에 있는 값(자기 자신)과 바꿉니다 (사실상 아무 변화가 일어나지 않습니다):
{ 10, 20, 30, 40, 50 }
짜잔! 정렬이 모두 끝났습니다!
{ 10, 20, 30, 40, 50 }
여기서 한 가지 눈치채셨나요? 맨 마지막에 남는 1개는 항상 자기 자신과 자리를 바꾸게 되므로(쓸데없는 행동이죠), 굳이 마지막까지 검사할 필요 없이 배열의 맨 끝부분 바로 앞까지만 반복 작업을 해주면 됩니다.
C++로 구현한 선택 정렬
지금까지 배운 선택 정렬 알고리즘을 C++ 코드로 똑같이 옮겨 적어보겠습니다:
#include <iostream>
#include <iterator>
#include <utility>
int main()
{
int array[]{ 30, 50, 20, 10, 40 };
constexpr int length{ static_cast<int>(std::size(array)) };
// 배열의 요소를 하나씩 차례대로 훑고 지나갑니다
// (단, 맨 마지막 요소는 그 앞까지 정렬하는 동안 알아서 자기 자리를 찾을 테니, 마지막 요소 바로 앞까지만 반복합니다)
for (int startIndex{ 0 }; startIndex < length - 1; ++startIndex)
{
// smallestIndex는 이번 한 바퀴를 돌면서 찾아낸 '가장 작은 요소'의 위치(인덱스)를 기억할 변수입니다
// 처음 시작할 때는 현재 살펴보고 있는 첫 번째 요소가 가장 작다고 일단 가정합니다
int smallestIndex{ startIndex };
// 그런 다음, 배열의 나머지 뒷부분을 쭉 살펴보면서 더 작은 요소가 숨어있는지 찾아냅니다
for (int currentIndex{ startIndex + 1 }; currentIndex < length; ++currentIndex)
{
// 만약 우리가 지금까지 제일 작다고 생각했던 것보다 더 작은 요소를 발견하게 된다면
if (array[currentIndex] < array[smallestIndex])
// 진짜 제일 작은 요소의 위치를 새로운 위치로 업데이트해서 기억해둡니다
smallestIndex = currentIndex;
}
// 위 과정을 다 거치고 나면, smallestIndex는 남은 배열 부분에서 '진짜로 가장 작은 요소'의 위치를 가리키게 됩니다
// 이제 우리가 처음에 가정했던 시작 위치의 요소와 진짜 가장 작은 요소를 서로 맞바꿔 줍니다 (이로써 제자리를 찾아갑니다)
std::swap(array[startIndex], array[smallestIndex]);
}
// 이제 전체 배열이 예쁘게 정렬되었을 테니, 잘 작동하는지 화면에 쭉 출력해서 확인해 봅니다
for (int index{ 0 }; index < length; ++index)
std::cout << array[index] << ' ';
std::cout << '\n';
return 0;
}
코드를 처음 보시는 분들이 여기서 가장 헷갈려 하는 부분은 바로 반복문(for 문) 안에 또 다른 반복문이 들어있는 구조일 것입니다. 이를 '중첩 반복문'이라고 부릅니다.
바깥쪽에 있는 반복문(startIndex)은 우리가 정렬해서 꽂아 넣을 자리를 맨 앞에서부터 한 칸씩 뒤로 이동시키는 역할을 합니다. 바깥쪽 반복문이 한 칸 이동할 때마다, 안쪽에 있는 반복문(currentIndex)이 맹활약하면서 아직 정렬되지 않은 나머지 뒷부분을 전부 훑어보고 그중 가장 작은 녀석의 위치를 찾아냅니다.
안쪽 반복문이 가장 작은 녀석의 위치를 smallestIndex에 잘 기억해 두었다가 작업이 끝나면, 그 녀석을 바깥쪽 반복문이 가리키고 있던 현재 자리(startIndex)의 값과 교체합니다. 그리고 바깥쪽 반복문은 다음 칸으로 이동하여 이 전체 과정을 반복하는 원리입니다.
팁: 만약 위에 있는 코드가 머릿속에 잘 안 그려진다면, 이면지를 한 장 꺼내서 샘플 배열을 하나 적어두고 직접 손으로 따라가 보는 것이 최고입니다. 종이 맨 위에 정렬되지 않은 처음 배열의 숫자들을 적으세요. 그리고
startIndex,currentIndex,smallestIndex라는 이름표를 달아둔 화살표를 그려서 각각 어떤 숫자를 가리키고 있는지 표시해 보세요. 코드가 한 줄 한 줄 실행될 때마다 화살표를 직접 옮겨보고, 바깥쪽 반복문이 한 바퀴 끝날 때마다 그다음 줄에 새롭게 변화된 배열의 모습을 그려 나가다 보면 원리가 아주 쉽게 이해될 거예요.
사람들의 이름을 정렬할 때도 작동하는 방식은 완전히 똑같습니다. 단지 배열의 종류를 숫자를 담는 int에서 문자를 담는 std::string으로 슬쩍 바꿔주고, 안에 숫자가 아닌 이름들을 채워 넣어주기만 하면 된답니다.
std::sort 함수 사용하기
배열을 정렬하는 일은 프로그래밍을 하다 보면 밥 먹듯이 아주 자주 일어나는 일입니다. 그래서 C++에서는 우리가 일일이 복잡한 정렬 코드를 짜지 않아도 되도록, C++ 표준 라이브러리 안에 std::sort라는 이름의 강력하고 편리한 정렬 함수를 기본적으로 제공해 줍니다. 이 함수는 <algorithm> 헤더를 추가해서 사용할 수 있고, 아래처럼 아주 간단하게 부려먹을 수 있습니다.
#include <algorithm> // std::sort를 사용하려면 이 헤더가 필요합니다
#include <iostream>
#include <iterator> // std::size를 사용하려면 이 헤더가 필요합니다
int main()
{
int array[]{ 30, 50, 20, 10, 40 };
// 마법의 주문! 배열의 처음부터 끝까지 알아서 정렬해 줍니다.
std::sort(std::begin(array), std::end(array));
for (int i{ 0 }; i < static_cast<int>(std::size(array)); ++i)
std::cout << array[i] << ' ';
std::cout << '\n';
return 0;
}
이 std::sort 함수를 별다른 조건 없이 그대로 실행시키면, 기본적으로 작은 것부터 큰 것으로 가는 오름차순으로 배열을 척척 정리해 줍니다. 보이지 않는 내부에서는 우리가 앞에서 배웠던 선택 정렬처럼 두 데이터를 작다(<) 기호를 사용해 짝지어 비교하고, 순서가 엇갈려 있으면 서로 자리를 휙휙 바꿔가며 영리하게 정렬을 수행한답니다.
이 편리한 std::sort에 대한 더 깊고 재미있는 이야기는 나중에 다른 장에서 다룰 예정이니 기대해 주세요!
18.2 — 이터레이터(반복자) 소개
배열이나 여러 데이터가 모여 있는 구조에서 데이터를 '처음부터 끝까지 하나씩 살펴보는 일(반복, Iterating)'은 프로그래밍에서 정말 흔하게 하는 작업입니다. 우리는 지금까지 이 작업을 하기 위해 여러 가지 방법을 배웠습니다. 인덱스와 반복문을 사용하는 방법(for 문, while 문), 포인터와 포인터 연산을 사용하는 방법, 그리고 아주 간편한 '범위 기반(range-based) for 문'을 사용하는 방법 말이죠.
#include <array>
#include <cstddef>
#include <iostream>
int main()
{
// C++17에서는 arr 변수의 타입이 std::array<int, 7>로 자동 추론됩니다.
// 만약 이 예제를 컴파일할 때 오류가 발생한다면, 아래 주의 사항을 확인하세요.
std::array arr{ 0, 1, 2, 3, 4, 5, 6 };
std::size_t length{ std::size(arr) };
// 명시적인 인덱스를 사용하는 while 문
std::size_t index{ 0 };
while (index < length)
{
std::cout << arr[index] << ' ';
++index;
}
std::cout << '\n';
// 명시적인 인덱스를 사용하는 for 문
for (index = 0; index < length; ++index)
{
std::cout << arr[index] << ' ';
}
std::cout << '\n';
// 포인터를 사용하는 for 문 (참고: ptr을 증가시켜야 하므로 const가 될 수 없습니다)
for (auto ptr{ &arr[0] }; ptr != (&arr[0] + length); ++ptr)
{
std::cout << *ptr << ' ';
}
std::cout << '\n';
// 범위 기반 for 문
for (int i : arr)
{
std::cout << i << ' ';
}
std::cout << '\n';
return 0;
}
주의 사항
이 레슨의 예제들은 '클래스 템플릿 인수 추론'이라는 C++17의 편리한 기능을 사용합니다. 쉽게 말해, 초기화하는 값을 보고 컴파일러가 알아서 타입을 유추해 주는 기능입니다. 위 예제에서 컴파일러가std::array arr{ 0, 1, 2, 3, 4, 5, 6 };을 보면, 우리가std::array<int, 7> arr { 0, 1, 2, 3, 4, 5, 6 };을 만들고 싶어 한다는 것을 찰떡같이 알아챕니다.
만약 여러분의 컴파일러가 C++17을 지원하지 않는 설정이라면 "arr 앞에 템플릿 인수가 누락되었습니다" 같은 오류가 뜰 수 있습니다. 이럴 때는 레슨 0.12를 참고해 C++17을 활성화하는 것이 가장 좋습니다. 만약 버전을 올릴 수 없다면, 코드를 명시적인 타입이 적힌 형태로 바꿔주세요. (예:std::array arr{ 0, 1, 2, 3, 4, 5, 6 };부분을std::array<int, 7> arr { 0, 1, 2, 3, 4, 5, 6 };로 수정)
데이터에 접근하기 위해서만 인덱스를 사용하는 경우라면, 인덱스 방식은 불필요하게 코드를 많이 쳐야 합니다. 게다가 이 방식은 배열처럼 요소에 '직접 접근(번호표를 보고 바로 찾아가는 것)'이 가능한 구조에서만 쓸 수 있습니다. 리스트(list) 같은 다른 데이터 구조에서는 인덱스로 바로 찾아가는 것이 불가능하거든요.
포인터와 포인터 연산(포인터에 숫자를 더해서 다음 칸으로 이동하는 것)을 사용해 반복하는 방법은 코드가 복잡해 보이고, 이 규칙을 잘 모르는 사람에게는 매우 헷갈릴 수 있습니다. 또한 이 방법은 배열처럼 메모리상에 데이터가 '다닥다닥 연속으로' 붙어있을 때만 제대로 작동합니다. 리스트, 트리, 맵 같은 구조에서는 데이터가 연속해 있지 않기 때문에 쓸 수 없습니다.
고급 학습자를 위한 내용
메모리에 연속으로 붙어있지 않은 데이터 구조라도, 포인터 연산(덧셈/뺄셈) 없이 그냥 포인터 자체만으로 반복할 수 있는 경우도 있습니다. 예를 들어 연결 리스트(Linked list)에서는 각 데이터가 다음 데이터를 가리키는 포인터를 가지고 있어서, 이 꼬리물기 포인터를 따라가며 하나씩 살펴볼 수 있습니다.
범위 기반 for 문은 아주 흥미롭습니다. 데이터를 하나씩 꺼내오는 복잡한 과정이 우리 눈에는 안 보이게 숨겨져 있거든요. 게다가 배열, 리스트, 트리, 맵 등 종류를 가리지 않고 모든 구조에서 다 잘 작동합니다. 도대체 어떻게 이게 가능한 걸까요? 바로 '이터레이터(Iterator)'를 사용하기 때문입니다.
이터레이터 (반복자)
이터레이터(Iterator)는 컨테이너(배열의 값들이나 문자열의 글자들처럼 데이터를 담아두는 바구니) 안을 처음부터 끝까지 돌아다니며, 지나가는 길에 있는 각 데이터에 접근할 수 있게끔 특별히 만들어진 도구입니다. 비유하자면 데이터 창고를 안내해 주는 '가이드'와 같습니다.
하나의 컨테이너가 여러 종류의 이터레이터를 제공할 수도 있습니다. 예를 들어 어떤 배열은 앞에서부터 뒤로 걸어가는 '정방향 이터레이터'를 제공하기도 하고, 뒤에서부터 앞으로 거꾸로 걸어가는 '역방향 이터레이터'를 제공하기도 합니다.
알맞은 이터레이터를 하나 만들기만 하면, 프로그래머는 데이터가 메모리에 어떻게 저장되어 있는지, 앞으로 어떻게 걸어갈지 고민할 필요가 없습니다. 그냥 이터레이터가 제공하는 간단한 조작법만 쓰면 됩니다.
특히 C++의 이터레이터들은 보통 사용법이 다 똑같습니다. operator++ (플러스플러스 기호)를 쓰면 다음 데이터로 이동하고, operator* (별표 기호)를 쓰면 지금 가리키고 있는 데이터를 꺼내옵니다. 이 통일된 사용법 덕분에 우리는 아주 다양한 종류의 데이터 컨테이너를 똑같은 방법으로 다룰 수 있게 됩니다.
이터레이터 역할을 하는 포인터
가장 단순한 형태의 이터레이터는 바로 '포인터'입니다. 메모리에 데이터가 일렬로 쭉 저장되어 있을 때 포인터를 사용하면 아주 잘 작동하죠. 포인터를 사용해 간단한 배열을 훑어보는 코드를 다시 살펴볼까요?
#include <array>
#include <iostream>
int main()
{
std::array arr{ 0, 1, 2, 3, 4, 5, 6 };
auto begin{ &arr[0] };
// 주의: 이것은 마지막 원소의 바로 '다음' 빈 공간을 가리킵니다.
auto end{ begin + std::size(arr) };
// 포인터를 사용하는 for 문
for (auto ptr{ begin }; ptr != end; ++ptr) // ++를 사용해 다음 요소로 이동
{
std::cout << *ptr << ' '; // 역참조(*)를 통해 현재 요소의 실제 값을 가져옴
}
std::cout << '\n';
return 0;
}
출력 결과:
0 1 2 3 4 5 6
위 코드에서 우리는 두 개의 변수를 만들었습니다. 하나는 데이터의 출발점을 가리키는 begin이고, 다른 하나는 끝나는 지점을 표시하는 end입니다. 배열에서 이 끝 지점(end marker)은 보통 '마지막 데이터가 있는 자리'가 아니라, '마지막 데이터 바로 다음 빈칸'을 의미합니다. 만약 데이터가 하나 더 있었다면 들어갈 바로 그 자리 말이죠.
포인터는 이 begin부터 출발해 end에 닿기 전까지 이동하며, 포인터에 역참조 기호(*)를 붙여서 현재 위치의 데이터를 읽어옵니다.
주의 사항
끝 지점을 계산할 때 아래처럼 배열 문법을 사용해 주소를 가져오고 싶으실 수도 있습니다.
int* end{ &arr[std::size(arr)] };
하지만 이렇게 하면 '정의되지 않은 동작(Undefined behavior, 프로그램이 뻗거나 예측 불가능하게 행동함)'이 발생합니다. 왜냐하면 저 코드는 배열의 진짜 범위를 벗어난 곳의 값을 은연중에 읽어오려고 시도하기 때문입니다.
대신 아래처럼 안전한 방식을 사용하세요:
int* end{ arr.data() + std::size(arr) }; // data()는 첫 번째 요소를 가리키는 포인터를 줍니다.
표준 라이브러리 이터레이터
데이터를 순서대로 살펴보는 건 프로그래밍에서 숨 쉬는 것만큼 자연스럽고 흔한 일입니다. 그래서 C++의 모든 표준 라이브러리 컨테이너(데이터 저장소들)는 이터레이터 기능을 기본적으로 내장하고 있습니다. 우리가 힘들게 출발점과 끝점을 계산할 필요 없이, 컨테이너에게 직접 begin()과 end()라는 함수를 불러서 "시작점과 끝점을 알려줘!"라고 물어보기만 하면 됩니다.
#include <array>
#include <iostream>
int main()
{
std::array array{ 1, 2, 3 };
// 배열에게 시작점과 끝점을 물어봅니다 (begin 및 end 멤버 함수 사용).
auto begin{ array.begin() };
auto end{ array.end() };
for (auto p{ begin }; p != end; ++p) // ++를 사용해 다음 요소로 이동.
{
std::cout << *p << ' '; // 역참조를 통해 현재 요소의 값을 가져옴.
}
std::cout << '\n';
return 0;
}
출력 결과:
1 2 3
<iterator>라는 헤더 파일 안에는 범용적으로 쓸 수 있는 std::begin과 std::end라는 함수도 들어 있습니다.
팁
구형 C스타일 배열을 위한std::begin과std::end는<iterator>헤더에 정의되어 있습니다.
이터레이터를 지원하는 최신 컨테이너들을 위한std::begin과std::end는 해당 컨테이너의 헤더 파일(예:<array>,<vector>)에 같이 들어 있습니다.
#include <array> // <iterator>를 포함합니다
#include <iostream>
int main()
{
std::array array{ 1, 2, 3 };
// std::begin과 std::end를 사용해 시작점과 끝점을 가져옵니다.
auto begin{ std::begin(array) };
auto end{ std::end(array) };
for (auto p{ begin }; p != end; ++p) // ++를 사용해 다음 요소로 이동
{
std::cout << *p << ' '; // 역참조를 통해 현재 요소의 값을 가져옴
}
std::cout << '\n';
return 0;
}
이것도 똑같이 출력됩니다:
1 2 3
지금 당장 이터레이터의 '타입(자료형)'이 정확히 뭔지 몰라도 괜찮습니다. 나중에 다른 챕터에서 자세히 다룰 거거든요. 여기서 가장 중요한 핵심은 '컨테이너 안을 돌아다니는 복잡한 과정은 이터레이터가 다 알아서 해준다'는 점입니다. 우리가 필요한 건 딱 네 가지뿐입니다. 시작점(begin), 끝점(end), 다음으로 넘어가게 해주는 버튼(operator++), 그리고 값을 꺼내오는 버튼(operator*)입니다.
이터레이터에서의 operator< 와 operator!= 비교
이전 레슨 8.10(For 문)에서, 우리는 숫자를 비교해 반복문을 돌릴 때는 !=보다 < 기호를 쓰는 것이 더 좋다고 배웠습니다.
for (index = 0; index < length; ++index)
하지만 이터레이터를 쓸 때는 != (같지 않다) 기호를 사용해 이터레이터가 끝 지점(end)에 도달했는지 확인하는 것이 표준 관행입니다.
for (auto p{ begin }; p != end; ++p)
왜 그럴까요? 어떤 이터레이터들은 구조상 크기를 비교하는 것(<, >)이 아예 불가능하기 때문입니다. 하지만 != 기호는 어떤 종류의 이터레이터든 상관없이 항상 무사히 작동합니다.
다시 보는 범위 기반 for 문 (Range-based for loops)
begin()과 end() 함수를 가지고 있거나, std::begin() 및 std::end() 함수와 함께 쓸 수 있는 모든 데이터 타입은 아주 편리한 '범위 기반 for 문'에 쓸 수 있습니다.
#include <array>
#include <iostream>
int main()
{
std::array array{ 1, 2, 3 };
// 이 코드는 우리가 앞에서 썼던 반복문과 완전히 똑같이 동작합니다.
for (int i : array)
{
std::cout << i << ' ';
}
std::cout << '\n';
return 0;
}
보이지 않는 곳에서, 범위 기반 for 문은 훑어볼 대상의 begin()과 end()를 몰래 호출해서 사용하고 있습니다. std::array는 자체적으로 이 함수들을 가지고 있기 때문에 범위 기반 반복문에 넣고 돌릴 수 있는 거죠. 구형 C스타일의 고정 크기 배열도 std::begin과 std::end 함수와 호환되기 때문에 역시 사용할 수 있습니다.
하지만 구형 C스타일의 '동적 배열(크기가 변하는 배열)'이나 포인터로 깎여버린(decayed) 배열은 쓸 수 없습니다. 이런 배열들은 길이 정보를 잃어버려서 std::end 함수를 찾을 수 없기 때문입니다.
여러분이 직접 만든 타입에도 이 함수들을 추가해서 범위 기반 for 문을 쓸 수 있게 만드는 방법은 나중에 배우게 될 겁니다.
그리고 이터레이터는 범위 기반 for 문에서만 쓰이는 게 아닙니다. 표준 라이브러리의 std::sort(데이터 정렬하기) 같은 수많은 유용한 알고리즘에서도 널리 쓰입니다. 이제 이터레이터가 뭔지 아셨으니, 앞으로 표준 라이브러리를 쓰면서 이 녀석이 얼마나 자주 등장하는지 보게 되실 겁니다.
이터레이터 무효화 (허공을 맴도는 이터레이터)
포인터나 참조자(Reference)와 마찬가지로, 이터레이터도 가리키고 있던 데이터의 메모리 주소가 바뀌거나 데이터가 파괴되어 버리면 길을 잃고 "허공을 가리키게(dangling)" 될 수 있습니다. 이런 상황을 이터레이터가 무효화(Invalidated)되었다고 부릅니다. 무효화된 이터레이터에 억지로 접근하려고 하면 아까 말했던 끔찍한 '정의되지 않은 동작(Undefined behavior)'이 발생합니다.
데이터 저장소를 수정하는 몇몇 작업들(예를 들어 std::vector라는 바구니에 새로운 데이터를 쑤셔 넣는 일)은, 그 안에 들어있던 기존 데이터들의 메모리 주소를 통째로 이사시켜 버리는 부작용을 낳기도 합니다. 데이터들이 이사를 가버리면, 원래 위치를 가리키고 있던 옛날 이터레이터들은 전부 쓸모가 없어집니다(무효화됩니다).
좋은 C++ 공식 문서들은 어떤 행동을 했을 때 이터레이터가 무효화될 수 있는지 항상 친절하게 경고해 둡니다. (cppreference 사이트의 std::vector 문서 중 "Iterator invalidation(이터레이터 무효화)" 항목을 참고해 보세요.)
우리가 자주 쓰는 범위 기반 for 문 역시 뒤에서는 이터레이터를 쓰고 있습니다. 그러니 반복문이 쌩쌩 돌아가고 있는 중간에 이터레이터를 무효화시키는 짓을 하지 않도록 각별히 조심해야 합니다.
#include <vector>
int main()
{
std::vector v { 0, 1, 2, 3 };
for (auto num : v) // 뒤에서 몰래 v의 이터레이터를 돌리며 요소를 봅니다
{
if (num % 2 == 0)
v.push_back(num + 1); // 데이터를 밀어 넣다가 v의 이터레이터가 무효화되면, 프로그램이 어떻게 뻗을지 모릅니다 (정의되지 않은 동작)
}
return 0;
}
이터레이터가 무효화되는 또 다른 예시를 볼까요?
#include <iostream>
#include <vector>
int main()
{
std::vector v{ 1, 2, 3, 4, 5, 6, 7 };
auto it{ v.begin() };
++it; // 두 번째 요소로 이동합니다
std::cout << *it << '\n'; // 정상 작동: 2가 출력됩니다
v.erase(it); // 지금 이터레이터가 가리키고 있는 요소를 지워버립니다!
// erase() 함수는 지워진 요소(및 그 뒤에 있는 요소들)를 가리키던 이터레이터들을 모두 무효화시킵니다.
// 그러므로 이제 이터레이터 "it"은 쓸모없는 쓰레기가 되었습니다.
++it; // 정의되지 않은 동작 (에러 위험!)
std::cout << *it << '\n'; // 정의되지 않은 동작 (에러 위험!)
return 0;
}
이렇게 무효화되어 길을 잃은 이터레이터는, 올바른 위치를 가리키는 새 이터레이터를 덮어씌워 주면(예: begin(), end(), 혹은 이터레이터를 반환하는 다른 함수의 결괏값을 다시 넣어줌) 다시 정상적으로 쓸 수 있습니다.
참고로 erase() 함수는 요소를 하나 지우고 나면, 친절하게도 '지워진 녀석의 바로 다음 요소'를 가리키는 새로운 이터레이터를 반환해 줍니다. (만약 마지막 요소를 지웠다면 end()를 줍니다).
따라서 위에서 에러가 나던 코드는 아래처럼 아주 쉽게 고칠 수 있습니다!
#include <iostream>
#include <vector>
int main()
{
std::vector v{ 1, 2, 3, 4, 5, 6, 7 };
auto it{ v.begin() };
++it; // 두 번째 요소로 이동
std::cout << *it << '\n';
it = v.erase(it); // 현재 요소를 지운 다음, `it`이 다음 요소를 가리키도록 새 이터레이터 값을 받아옵니다.
std::cout << *it << '\n'; // 이제 안전합니다! 3이 출력됩니다.
return 0;
}
18.3 — 표준 라이브러리 알고리즘 소개
프로그래밍을 갓 배우기 시작한 분들은 정렬하기, 개수 세기, 배열 검색하기 같은 꽤 간단한 작업을 하기 위해 직접 반복문(loop)을 짜는 데 많은 시간을 보냅니다. 그런데 이 반복문이라는 게 은근히 골칫거리입니다. 오타나 실수를 내기도 쉽고, 나중에 코드를 다시 읽을 때 "이게 뭐 하는 코드였지?" 하고 한눈에 파악하기가 어려워서 유지보수하기도 까다롭거든요.
검색, 개수 세기, 정렬은 프로그래밍에서 정말 숨 쉬듯이 자주 하는 작업입니다. 그래서 C++ 표준 라이브러리(Standard Library)는 이런 귀찮은 작업들을 단 몇 줄의 코드만으로 끝낼 수 있도록 미리 만들어진 유용한 함수들의 묶음을 제공합니다. 게다가 이 함수들은 전문가들이 이미 꼼꼼하게 테스트해 두어서 안전하고, 속도도 엄청 빠르며, 여러 종류의 데이터 상자(컨테이너)에서 모두 사용할 수 있습니다. 심지어 일꾼(CPU 스레드) 여러 명을 동시에 투입해서 작업을 더 빨리 끝내는 '병렬 처리'를 지원하는 함수도 많답니다!
이런 '알고리즘 라이브러리'가 제공하는 기능은 크게 세 가지로 나눌 수 있어요.
- 검사기 (Inspectors): 데이터 상자 안을 들여다보기만 할 때 씁니다 (데이터를 수정하진 않아요). 검색이나 개수 세기가 여기 속합니다.
- 변경기 (Mutators): 데이터 상자 안의 데이터를 지지고 볶고 수정할 때 씁니다. 정렬하거나 순서를 마구 섞는 작업이 있죠.
- 도우미 (Facilitators): 데이터 값들을 바탕으로 새로운 결과를 만들어 낼 때 씁니다. 값들을 곱해주는 기능이나, 요소들을 어떤 순서로 정렬할지 심판을 봐주는 기능 등이 있어요.
이런 꿀 기능들은 <algorithm>이라는 라이브러리 안에 살고 있습니다. 이번 레슨에서는 가장 자주 쓰이는 친구들 몇 명을 만나볼 거예요. 하지만 이 외에도 정말 무궁무진한 기능이 있으니, 나중에 공식 문서를 한번 쭉 읽어보시면서 어떤 마법 같은 기능들이 더 있는지 구경해 보시길 추천합니다!
(참고: 이 함수들은 모두 '반복자(iterator)'라는 것을 사용해서 작동합니다. 반복자가 아직 어색하시다면, 이전 레슨인 '18.2 -- 반복자 소개'를 먼저 가볍게 복습하고 오시면 훨씬 이해가 쉬울 거예요!)
std::find를 사용해서 값으로 요소 찾기
std::find는 상자(컨테이너) 안에서 우리가 찾는 값이 처음으로 나타나는 위치를 콕 집어 찾아줍니다. 이 함수를 부르려면 세 가지 준비물이 필요해요.
1) 검색을 시작할 위치, 2) 검색을 끝낼 위치, 그리고 3) 내가 찾고 싶은 값입니다.
만약 값을 찾으면 그 값이 있는 위치를 가리키는 '반복자'를 돌려주고, 끝까지 다 뒤져도 못 찾으면 상자의 맨 끝(end)을 가리키는 반복자를 돌려줍니다.
예를 들어볼까요?
#include <algorithm>
#include <array>
#include <iostream>
int main()
{
std::array arr{ 13, 90, 99, 5, 40, 80 };
std::cout << "Enter a value to search for and replace with: ";
int search{};
int replace{};
std::cin >> search >> replace;
// 입력값 검증은 생략했습니다
// std::find는 찾은 요소(또는 컨테이너의 끝)를 가리키는 반복자를 반환합니다.
// (이 반복자의 정확한 타입은 굳이 신경 쓰지 않아도 되므로)
// auto를 사용해서 변수에 편하게 저장할게요.
auto found{ std::find(arr.begin(), arr.end(), search) };
// 알고리즘이 찾으려는 값을 찾지 못하면 '끝(end) 반복자'를 반환합니다.
// end() 멤버 함수를 호출해서 이것과 똑같은지 비교해 볼 수 있어요.
if (found == arr.end())
{
std::cout << "Could not find " << search << '\n';
}
else
{
// 찾은 요소의 값을 새 값으로 덮어씁니다.
*found = replace;
}
for (int i : arr)
{
std::cout << i << ' ';
}
std::cout << '\n';
return 0;
}
값을 무사히 찾았을 때의 실행 결과:
Enter a value to search for and replace with: 5 234
13 90 99 234 40 80
값을 찾지 못했을 때의 실행 결과:
Enter a value to search for and replace with: 0 234
Could not find 0
13 90 99 5 40 80
std::find_if를 사용해서 조건에 맞는 요소 찾기
가끔은 정확히 똑같은 값이 아니라, "이 글자가 포함된 단어가 있나?"처럼 특정 조건을 만족하는 값이 있는지 찾고 싶을 때가 있습니다. 이럴 때는 std::find_if가 아주 딱 맞습니다.
std::find_if는 std::find와 일하는 방식은 비슷한데, 찾고 싶은 '값'을 넘겨주는 대신 '함수'를 넘겨준다는 게 다릅니다. 배열의 요소들을 하나하나 훑어보면서 이 함수에 값을 던져주는데요, 함수가 "어? 이거 조건에 맞네!" 하고 true(참)를 외치면 찾은 것으로 간주하고, 아니면 false(거짓)를 외치고 다음 요소로 넘어가는 식입니다. (나중에 배울 '람다'라는 걸 쓸 수도 있어요.)
아래 예제는 문자열 안에 "nut"이라는 글자가 들어있는 요소가 있는지 std::find_if로 찾아보는 코드입니다.
#include <algorithm>
#include <array>
#include <iostream>
#include <string_view>
// 요소가 조건에 맞으면 true를 반환하는 함수입니다.
bool containsNut(std::string_view str)
{
// std::string_view::find는 부분 문자열을 찾지 못하면 std::string_view::npos를 반환합니다.
// 찾았다면 str 안에서 해당 부분 문자열이 시작하는 위치(인덱스)를 반환하죠.
return str.find("nut") != std::string_view::npos;
}
int main()
{
std::array<std::string_view, 4> arr{ "apple", "banana", "walnut", "lemon" };
// 배열을 쭉 훑어보면서 "nut"이라는 부분 문자열이 포함된 요소가 있는지 확인합니다.
auto found{ std::find_if(arr.begin(), arr.end(), containsNut) };
if (found == arr.end())
{
std::cout << "No nuts\n";
}
else
{
std::cout << "Found " << *found << '\n';
}
return 0;
}
출력 결과:
Found walnut
만약 이 작업을 라이브러리 없이 직접 짜야 했다면, 배열을 훑는 반복문 하나에, 문자열을 비교하는 반복문 두 개까지... 최소 3개의 반복문을 겹겹이 써야 했을 겁니다. 표준 라이브러리를 쓰면 이렇게 단 몇 줄로 깔끔하게 해결됩니다!
std::count와 std::count_if를 사용해서 개수 세기
이름만 봐도 딱 아시겠죠? std::count와 std::count_if는 특정 값이나 특정 조건에 맞는 요소가 총 몇 개 있는지를 세어주는 착한 함수들입니다.
다음 예제에서는 "nut"이라는 글자가 포함된 요소가 모두 몇 개인지 세어볼게요.
#include <algorithm>
#include <array>
#include <iostream>
#include <string_view>
bool containsNut(std::string_view str)
{
return str.find("nut") != std::string_view::npos;
}
int main()
{
std::array<std::string_view, 5> arr{ "apple", "banana", "walnut", "lemon", "peanut" };
auto nuts{ std::count_if(arr.begin(), arr.end(), containsNut) };
std::cout << "Counted " << nuts << " nut(s)\n";
return 0;
}
출력 결과:
Counted 2 nut(s)
std::sort를 사용해서 내 맘대로 정렬하기
예전 레슨에서 배열을 작은 수부터 큰 수로(오름차순) 예쁘게 줄 세울 때 std::sort를 써보셨을 거예요. 그런데 std::sort는 그것보다 훨씬 똑똑합니다. std::sort의 세 번째 준비물로 우리가 직접 만든 '함수'를 끼워 넣어 주면, 우리가 원하는 어떤 방식으로든 맘대로 줄을 세울 수 있거든요.
이 함수는 두 개의 값을 비교해서, 첫 번째 값이 두 번째 값보다 더 앞에 서야 한다면 true를 반환하도록 규칙을 정해주면 됩니다. (기본적으로 std::sort는 아무것도 안 알려주면 알아서 오름차순으로 줄을 세웁니다.)
그럼 이번에는 반대로, 큰 수부터 작은 수로(내림차순) 정렬해 볼까요? greater라는 우리만의 비교 규칙 함수를 만들어서 써보겠습니다.
#include <algorithm>
#include <array>
#include <iostream>
bool greater(int a, int b)
{
// a가 b보다 크면 a를 b보다 앞에 배치합니다 (내림차순 정렬).
return (a > b);
}
int main()
{
std::array arr{ 13, 90, 99, 5, 40, 80 };
// 우리가 만든 greater 함수를 std::sort에 넘겨줍니다.
std::sort(arr.begin(), arr.end(), greater);
for (int i : arr)
{
std::cout << i << ' ';
}
std::cout << '\n';
return 0;
}
출력 결과:
99 90 80 40 13 5
이것도 마찬가지로 머리 아프게 정렬 반복문을 직접 만들 필요 없이, 단 몇 줄만으로 내 맘대로 정렬을 끝냈습니다!
그런데 여기서 조금 헷갈리실 수 있는 부분! 우리가 만든 greater 함수는 2개의 재료(인수)가 필요한데, 코드에서는 괄호 ()도 없이 이름만 달랑 적어줬죠? 값은 대체 어디서 가져온 걸까요?
함수 이름 뒤에 괄호를 빼고 적으면, 이건 함수를 당장 실행하라는 게 아니라 "이 함수가 여깄어~" 하고 위치만 가리키는 함수 포인터가 됩니다. 예전에 함수를 괄호 없이 출력하려고 했을 때 화면에 이상하게 "1"이라고 찍혔던 거 기억하시나요? std::sort는 이 포인터를 가지고 있다가, 자기가 알아서 배열 안의 두 요소를 쏙쏙 뽑아 greater 함수에 넣고 실행해 보는 겁니다. std::sort가 속에서 어떤 정렬 방식을 쓰는지 우리는 모르기 때문에, 어떤 두 요소가 비교될지는 그때그때 다릅니다. (이 '함수 포인터'에 대해서는 나중 챕터에서 더 자세히 다룰 거니까 너무 걱정하지 마세요!)
std::for_each를 사용해서 모든 요소에 작업 수행하기
std::for_each는 리스트를 넘겨받아서, 그 안에 있는 모든 요소 하나하나에 똑같은 함수를 실행시켜 줍니다. 리스트에 있는 모든 숫자를 두 배로 뻥튀기하고 싶거나 할 때 아주 유용하죠.
배열의 모든 숫자를 두 배로 만드는 예제를 볼까요?
#include <algorithm>
#include <array>
#include <iostream>
void doubleNumber(int& i)
{
i *= 2;
}
int main()
{
std::array arr{ 1, 2, 3, 4 };
std::for_each(arr.begin(), arr.end(), doubleNumber);
for (int i : arr)
{
std::cout << i << ' ';
}
std::cout << '\n';
return 0;
}
출력 결과:
2 4 6 8
처음 프로그래밍을 배우시는 분들은 여기서 "어? 그냥 범위 기반 for문(range-based for-loop) 쓰면 코드도 더 짧고 편한데 굳이 이 복잡해 보이는 걸 왜 쓰지?" 하고 의아해하실 수 있습니다. 하지만 std::for_each만의 숨겨진 강력한 장점들이 있습니다. 두 방식을 비교해 볼게요.
std::ranges::for_each(arr, doubleNumber); // C++20부터는 begin()과 end()를 쓰지 않아도 됩니다.
// std::for_each(arr.begin(), arr.end(), doubleNumber); // C++20 이전 방식
for (auto& i : arr)
{
doubleNumber(i);
}
std::for_each를 쓰면, 코드를 읽는 사람에게 "나는 arr의 모든 요소에 doubleNumber 작업을 할 거야!"라는 내 의도를 아주 또렷하게 보여줄 수 있습니다. 반면 for문은 i라는 변수를 하나 더 끼워 넣어야 하죠. 이게 별거 아닌 것 같아 보여도, 사람이 피곤하거나 깜빡 정신을 놓으면 자잘한 실수들을 만들기 딱 좋습니다.
예를 들어 auto를 안 써서 나도 모르게 타입이 변환되어 버리거나, 참조 기호(&)를 깜빡해서 정작 배열 원본 값은 안 변하고 헛수고를 하거나, doubleNumber에 i가 아닌 다른 엉뚱한 변수를 넣는 실수를 할 수 있죠. std::for_each를 쓰면 구조상 이런 억울한 실수가 아예 일어날 수 없습니다!
게다가 std::for_each는 처음이나 끝부분을 마음대로 건너뛰고 실행할 수도 있습니다. 예를 들어 첫 번째 요소는 빼고 두 배로 만들고 싶다면, std::next를 써서 시작 위치를 한 칸 밀어버리면 됩니다.
std::for_each(std::next(arr.begin()), arr.end(), doubleNumber);
// 이제 배열은 [1, 4, 6, 8]이 됩니다. 첫 번째 요소인 1은 두 배가 되지 않았어요.
보통의 범위 기반 for문으로는 이렇게 부분만 쏙 골라서 실행하기가 꽤 번거롭습니다.
가장 중요한 차이점은 속도입니다. std::for_each는 다른 알고리즘들처럼 여러 작업을 동시에 해치우는 병렬 처리가 가능하기 때문에, 다뤄야 할 데이터가 엄청나게 많거나 대규모 프로젝트를 할 때는 단순 for문보다 훨씬 처리 속도가 빠릅니다.
성능과 실행 순서
알고리즘 라이브러리에 있는 기능들은 대체로 "나는 최소한 이 정도 속도는 낼 거야!" 라거나 "나는 꼭 이 순서대로 실행할 거야!" 하는 약속(보장)을 가지고 있습니다. 예를 들어 std::for_each는 각 요소에 딱 한 번씩만 들르고, 무조건 맨 앞에서부터 순서대로 차근차근 실행하겠다고 굳게 약속합니다.
대부분의 알고리즘이 속도 보장은 해주지만, 실행 순서까지 확고하게 보장해 주는 알고리즘은 생각보다 많지 않습니다. 그래서 '당연히 차례대로 실행되겠지?' 하고 우리 마음대로 넘겨짚고 코드를 짜면 위험합니다.
예를 들어 첫 번째 값에는 1을 곱하고, 두 번째에는 2를 곱하고, 세 번째는 3을 곱하는 식으로 순서가 절대적으로 중요한 작업을 해야 한다면, 반드시 '순차적 실행'을 보장하는 알고리즘만 골라서 써야 합니다!
순서대로 얌전히 실행될 것을 보장하는 알고리즘 삼총사는 std::for_each, std::copy, std::copy_backward, std::move, std::move_backward가 있습니다. (물론 '순방향 반복자'라는 걸 쓰는 다른 많은 알고리즘들도 구조상 자연스럽게 순서대로 실행되긴 합니다.)
권장 사항
특정 알고리즘을 사용하기 전에, 내가 지금 하려는 작업이 속도나 실행 순서가 중요한지, 그리고 이 알고리즘이 그걸 만족시켜 주는지 꼭 한번 체크하는 습관을 들이세요!
C++20의 범위 (Ranges)
알고리즘을 쓸 때마다 arr.begin()이랑 arr.end()를 꼬박꼬박 타자 치기, 솔직히 너무 귀찮고 손가락 아프지 않으셨나요? 걱정하지 마세요! C++20부터는 범위(ranges)라는 멋진 기능이 추가되어서, 그냥 arr 하나만 툭 던져줘도 똑같이 작동합니다. 덕분에 코드가 훨씬 짧아지고 읽기도 편해졌답니다.
결론
알고리즘 라이브러리는 우리 코드를 훨씬 단순하고, 실수 없이 튼튼하게 만들어주는 마법 같은 도구 상자입니다. 이번 레슨에서는 그중 아주 일부분만 살짝 맛보았지만, 이 함수들은 일하는 방식이 다들 비슷비슷하기 때문에 원리 몇 가지만 익혀두시면 다른 기능들도 금방 가져다 쓰실 수 있을 거예요.
참고로...
이 비디오에서 라이브러리에 있는 다양한 알고리즘들을 아주 깔끔하게 정리해서 설명해 주니, 시간이 나실 때 꼭 한번 시청해 보세요.
권장 사항
직접 반복문을 짜면서 고생하기보다는, 내가 하려는 작업과 똑같은 기능을 하는 함수가 알고리즘 라이브러리에 있는지 먼저 찾아보고 적극적으로 활용해 보세요!
18.4 — 코드 실행 시간 측정하기
코드를 짜다 보면, "이 방법이랑 저 방법 중에 어느 쪽이 더 빠를까?" 하고 궁금해질 때가 있죠. 그걸 어떻게 알 수 있을까요?
가장 쉬운 방법은 코드가 실행되는 데 걸리는 시간을 직접 재보는 것입니다.
C++11 버전부터는 chrono라는 라이브러리 안에 시간을 잴 수 있는 도구들이 들어있어요. 하지만 이 chrono 라이브러리를 있는 그대로 쓰기엔 조금 복잡하고 어렵게 느껴질 수 있습니다.
다행히도 좋은 소식이 하나 있어요! 우리가 필요한 시간 측정 기능들만 쏙쏙 뽑아서, 앞으로 우리 프로그램에서 쉽게 꺼내 쓸 수 있도록 하나의 '클래스(class)'로 깔끔하게 포장해 둘 수 있답니다.
바로 이 클래스입니다.
#include <chrono> // std::chrono 함수들을 사용하기 위해 포함
class Timer
{
private:
// 복잡한 타입 이름을 쉽게 쓰기 위해 별칭(alias) 만들기
using Clock = std::chrono::steady_clock;
using Second = std::chrono::duration<double, std::ratio<1> >;
std::chrono::time_point<Clock> m_beg { Clock::now() };
public:
void reset()
{
m_beg = Clock::now();
}
double elapsed() const
{
return std::chrono::duration_cast<Second>(Clock::now() - m_beg).count();
}
};
이게 전부입니다! 사용 방법도 정말 간단해요. main 함수 맨 위(혹은 시간 측정을 시작하고 싶은 곳)에 Timer 객체를 하나 만들어 주기만 하면 됩니다. 그러고 나서 프로그램이 거기까지 실행되는 데 얼마나 걸렸는지 알고 싶을 때마다 elapsed()라는 함수를 불러주면 된답니다.
#include <iostream>
int main()
{
Timer t;
// 시간을 측정할 코드를 여기에 넣으세요
std::cout << "걸린 시간: " << t.elapsed() << " 초\n";
return 0;
}
자, 이제 숫자 10,000개가 들어있는 배열을 정렬하는 실제 예제에 이 타이머를 사용해 볼까요? 먼저, 우리가 이전 장에서 직접 만들었던 '선택 정렬(selection sort)' 방식을 써보겠습니다.
#include <array>
#include <chrono> // std::chrono 함수들을 사용하기 위해 포함
#include <cstddef> // std::size_t를 사용하기 위해 포함
#include <iostream>
#include <numeric> // std::iota를 사용하기 위해 포함
const int g_arrayElements { 10000 };
class Timer
{
private:
// 복잡한 타입 이름을 쉽게 쓰기 위해 별칭(alias) 만들기
using Clock = std::chrono::steady_clock;
using Second = std::chrono::duration<double, std::ratio<1> >;
std::chrono::time_point<Clock> m_beg{ Clock::now() };
public:
void reset()
{
m_beg = Clock::now();
}
double elapsed() const
{
return std::chrono::duration_cast<Second>(Clock::now() - m_beg).count();
}
};
void sortArray(std::array<int, g_arrayElements>& array)
{
// 배열의 각 요소를 하나씩 확인합니다
// (마지막 요소는 이미 정렬되어 있을 테니 제외합니다)
for (std::size_t startIndex{ 0 }; startIndex < (g_arrayElements - 1); ++startIndex)
{
// smallestIndex는 이번 반복에서 찾은 가장 작은 값의 위치(인덱스)입니다.
// 일단 현재 시작 위치의 값이 가장 작다고 가정하고 시작합니다.
std::size_t smallestIndex{ startIndex };
// 그런 다음 배열의 나머지 부분에서 더 작은 값이 있는지 찾아봅니다.
for (std::size_t currentIndex{ startIndex + 1 }; currentIndex < g_arrayElements; ++currentIndex)
{
// 만약 지금까지 찾은 가장 작은 값보다 더 작은 값을 발견했다면
if (array[currentIndex] < array[smallestIndex])
{
// 그 위치를 기억해 둡니다.
smallestIndex = currentIndex;
}
}
// 이제 smallestIndex는 남은 배열 중 가장 작은 값을 가리킵니다.
// 시작 위치의 값과 가장 작은 값을 서로 바꿉니다 (이렇게 해서 알맞은 자리에 정렬합니다).
std::swap(array[startIndex], array[smallestIndex]);
}
}
int main()
{
std::array<int, g_arrayElements> array;
std::iota(array.rbegin(), array.rend(), 1); // 배열을 10000부터 1까지의 역순 숫자로 채웁니다
Timer t;
sortArray(array);
std::cout << "걸린 시간: " << t.elapsed() << " 초\n";
return 0;
}
원작자의 컴퓨터에서 3번 실행해 본 결과, 0.0507초, 0.0506초, 0.0498초가 나왔다고 합니다. 대략 0.05초 정도 걸렸다고 볼 수 있겠네요.
그럼 이번에는 C++ 기본 라이브러리에서 제공하는 강력한 도구인 std::sort를 사용해서 똑같이 테스트해 볼까요?
#include <algorithm> // std::sort를 사용하기 위해 포함
#include <array>
#include <chrono> // std::chrono 함수들을 사용하기 위해 포함
#include <cstddef> // std::size_t를 사용하기 위해 포함
#include <iostream>
#include <numeric> // std::iota를 사용하기 위해 포함
const int g_arrayElements { 10000 };
class Timer
{
private:
// 복잡한 타입 이름을 쉽게 쓰기 위해 별칭(alias) 만들기
using Clock = std::chrono::steady_clock;
using Second = std::chrono::duration<double, std::ratio<1> >;
std::chrono::time_point<Clock> m_beg{ Clock::now() };
public:
void reset()
{
m_beg = Clock::now();
}
double elapsed() const
{
return std::chrono::duration_cast<Second>(Clock::now() - m_beg).count();
}
};
int main()
{
std::array<int, g_arrayElements> array;
std::iota(array.rbegin(), array.rend(), 1); // 배열을 10000부터 1까지의 역순 숫자로 채웁니다
Timer t;
std::ranges::sort(array); // C++20 버전 이상부터 사용 가능
// 만약 컴파일러가 C++20을 지원하지 않는다면 아래 코드를 사용하세요:
// std::sort(array.begin(), array.end());
std::cout << "걸린 시간: " << t.elapsed() << " 초\n";
return 0;
}
원작자의 컴퓨터에서는 이 코드가 0.000693초, 0.000692초, 0.000699초를 기록했습니다. 평균적으로 대략 0.0007초가 걸렸네요.
다시 말해 이 경우, 표준 라이브러리의 std::sort가 우리가 직접 만든 선택 정렬보다 무려 100배나 더 빠르다는 뜻입니다!
프로그램 성능(속도)에 영향을 미치는 요소들
프로그램 실행 시간을 재는 것 자체는 아주 쉽지만, 그 결과는 꽤 여러 가지 이유로 휙휙 바뀔 수 있어요. 그래서 제대로 측정하는 법과 무엇이 시간에 영향을 주는지 알아두는 게 무척 중요합니다.
- 디버그(Debug) 모드가 아닌 릴리즈(Release) 모드로 측정하세요. 디버그 모드는 오류를 찾기 쉽게 하려고 코드를 빠르게 만들어주는 '최적화' 기능을 꺼둡니다. 이 때문에 속도 차이가 엄청나게 나요. 원작자 컴퓨터에서 디버그 모드로
std::sort를 실행했더니 무려 33배나 느린 0.0235초가 걸렸다고 합니다! - 컴퓨터가 뒤에서 몰래 하고 있는 다른 작업들을 조심하세요. 측정할 때 컴퓨터가 CPU나 메모리, 하드디스크를 무리하게 쓰고 있으면 안 됩니다 (예: 게임 중이거나, 바이러스 검사 중이거나, 몰래 윈도우 업데이트가 깔리는 중일 때). 심지어 그냥 켜둔 인터넷 브라우저가 새 광고를 띄우느라 잠깐 CPU를 100% 써버리는 일도 생겨요. 측정하기 전에 켜져 있는 프로그램을 최대한 다 끄면, 결과가 매번 들쭉날쭉하는 걸 막을 수 있습니다.
- 랜덤 숫자(난수)를 쓴다면 결과가 달라질 수 있어요. 매번 랜덤 숫자가 다르게 나오면 코드가 일하는 양도 달라집니다. 여러 번 잴 때 항상 비슷한 결과를 얻고 싶다면, 랜덤 숫자를 만드는 공식에 '고정된 시작 값(시드)'을 넣어주세요. 그러면 매번 똑같은 순서로 난수가 나오니까 측정이 편해져요. (다만, 프로그램의 성능 자체가 이 랜덤 숫자에 너무 의존적이라면 이 방법이 오히려 가짜 결과를 보여줄 수도 있으니 주의해야 합니다.)
- 사용자 입력을 기다리는 시간은 빼고 재야 합니다. 사용자 이름이나 비밀번호를 입력하라고 기다리는 시간은 프로그램 성능과 아무 상관이 없겠죠? 입력이 필요하다면 측정 중에는 사람이 타이핑하지 않게, 코드가 자동으로 입력값을 가져오도록 살짝 바꿔서 재는 것이 좋습니다.
성능 측정하는 방법
내 프로그램의 진짜 성능을 알아보려면 최소한 3번 이상 측정해 보세요. 3번 다 결과가 비슷하게 나온다면, 그게 현재 컴퓨터에서 내 프로그램이 내는 진짜 속도라고 볼 수 있습니다. 만약 결과가 중구난방이라면, 비슷한 숫자들이 모일 때까지 여러 번 더 재보셔야 해요 (그리고 유독 튀는 숫자가 나왔다면 왜 그런지 이유를 파악해야 합니다). 보통 컴퓨터가 뒤에서 다른 짓을 하느라 한두 번씩 엄청 늦게 끝나는 '튀는 값(outlier)'이 나오는 건 흔한 일입니다.
계속 재봤는데도 결과가 들쭉날쭉하다면, 컴퓨터의 다른 프로그램들이 크게 방해하고 있거나 내 프로그램 안의 무작위적인 요소(랜덤) 때문일 확률이 큽니다.
프로그램 속도는 컴퓨터 사양, 운영체제, 켜져 있는 다른 앱 등 정말 많은 것들에 영향을 받아요. 그래서 "내 프로그램은 10초 만에 끝난다!" 같은 '절대적인 시간'은 남의 컴퓨터에서는 별 의미가 없습니다. 남의 컴퓨터에선 1초가 될 수도, 1분이 될 수도 있거든요. 직접 테스트해 보기 전엔 모르는 일이죠.
하지만 내 컴퓨터 하나에서 하는 '상대적인 비교'는 아주 쓸모가 많습니다. 어떤 코드를 A 방법으로 짰을 때는 10초 걸리고, B 방법으로 짰을 때는 8초 걸렸다면, 다른 컴퓨터에서도 시간 수치 자체는 다르겠지만 결국 B 방법이 더 빠를 거라는 사실은 변함이 없으니까요.
가장 확실하게 비교하는 꿀팁을 하나 드릴게요. B 방법을 다 재보고 난 뒤에, 다시 처음의 A 방법을 한번 더 재보는 겁니다. 만약 다시 잰 A 방법이 맨 처음 잰 10초와 똑같이 나온다면, 컴퓨터 상태가 일정했다는 뜻이니 안심하고 'B가 더 빠르다'라고 결론 내릴 수 있습니다.
하지만 만약 A 방법의 시간이 갑자기 달라졌다면? 방금 내 컴퓨터에 무슨 일이 생겨서 성능에 영향을 줬다는 뜻이에요. 이럴 때는 그동안 측정한 결과를 다 버리고 처음부터 다시 꼼꼼하게 측정하는 것이 좋습니다.
