[C++] INF의 값은 어떤 것으로 해주는 것이 좋을까?

다익스트라 알고리즘이나 여러 최단 거리 알고리즘에서, 초기 거리를 매우 큰 값(INF)으로 초기화해야 할 때가 왕왕 있다.

 

근데, 어떤 특정 값을 넣어야 할 지에 대해서는 아직 정해진 것이 없다. 사용자 취향에 따라 다음과 같이 정할 수 있다.

 

const int INF = 0x3f;
const int INF = int(1e9);
const int INF = 987654321;
const int INF = INT_MAX;
// 취향껏 사용할 수 있다.

 

그럼, 어떤 것을 사용해야 가장 부작용이 적을까? 한번 알아보도록 하자.

INF는 어떤 값으로 하는 것이 좋을까?

---

1. INF = INT_MAX

간혹 매우 큰 값으로 int형이 가질 수 있는 가장 큰 값인 $2^{32}-1$을 사용하는 경우가 있다.

 

이 수를 사용할 때 C / C++의 헤더 <limits.h> 혹은 <climits>에 매크로로 정의되어 있는 INT_MAX를 활용하면 아주 쉽게 정의할 수 있다. (INT_MAX의 실제 값은 컴파일러 종류에 따라 다르지만, int형이 가질 수 있는 가장 큰 값이라는 점에서는 동일하다.)

 

만약 INF의 값에 추가적인 연산을 사용하지 않는다면 사용할 수 있다. 다만, INT_MAX를 사용할 경우 덧셈에서 오버플로우가 발생한다.

 

실제 INT_MAX + INT_MAX를 하면 오버플로우가 발생하여, 엉뚱한 음수를 출력할 것이다.

 

이 경우, 플로이드-워샬 알고리즘과 같이 거리를 더하는 알고리즘에서 문제가 발생한다.

 

대부분의 경우, INF의 초깃값은 INT_MAX로 설정하는 것을 추천하지 않는다.

---

2. INF = 987654321

많은 사람들이 INF의 값을 987654321에 놓는 경우를 보았다.

 

충분히 가능하다. 9억이라는 큰 값이기도 하고, 한눈에 알아보기 쉬운 형태라서 디버깅하기도 쉽고, 자릿수로 인한 실수를 미연에 방지할 수 있다.

 

또한, 32비트 기준 987654321을 987654321에 더하였을 때 19억 7천보다 조금 큰 수라 int형의 범위를 넘지 않는다.

 

그러나, 한 번 더하였을 때 최댓값이 19억 7천이므로, 이를 저격하는 데이터(ex. 10억 + 10억)가 입력되면 틀릴 수 있으므로 주의해야 한다. 이런 잘못된 초기화로 틀리면 억울하지 않겠는가?

---

3. INF = int(1e9)

INF의 값으로 int(1e9) = $10^9 = $10억을 사용하는 경우도 보았다.

 

이 수도 충분히 큰 수이고, 한 번 자기 자신을 더하였을 때 int형의 범위를 넘지 않는다. 사용할만한 최댓값이다.

 

그러나, 이 수도 작정하고 저격 데이터를 만들면 충분히 저격당할 수 있는 수이다. 그러나, 출제자가 싸이코가 아닌 이상 이 초기화가 저격당할 일은 없을 것이다.

---

4. INF = 0x3f3f3f3f

INF의 값으로 16진법으로 "3f3f3f3f"으로 사용하는 경우도 보았다.

 

0x3f3f3f3f를 10진법으로 나타내면 '106,119,567', 즉 10억이 조금 넘는 수이다.

 

이 수도 충분히 큰 수이고, 한 번 자기 자신을 더하였을 때 int형의 범위를 넘지 않으므로, 위의 int(1e9)과 같은 맥락으로 사용할 수 있다.

 

또한, 이 수의 장점은 memset을 사용해 배열을 초기화할 수 있다는 점이다. 

 

또한, 0x3f3f3f3f으로 memset하는 대신 0x3f를 사용하여 초기화할 수 있다. 무슨 말인지 모르겠으면 다음 포스팅을 보고 오자.

memset(arr, 0x3f, sizeof arr) = memset(arr, 0x3f3f3f3f, sizeof arr)
// 같은 역할을 한다.

 

([C++] 초기화 함수 fill 과 memset은 무엇이 다를까?)

[C++] 초기화 함수 fill 과 memset은 무엇이 다를까?

---

5. INF = (~0U >> 2)

대다수의 사람들이 잘 안 쓰지만, 한 번만 더할 때 가장 촘촘하게 할 수 있는, 저격 데이터를 걱정하지 않아도 되는 수이다.

 

비트 연산에 익숙하지 않으면 무슨 말인지 이해하기 힘들 수 있다. 이를 하나씩 해석하여 보자.

 

0U는 Unsigned를 의미하고 "0" 뒤에 붙어있기에 unsigned int 0이란 의미를 가진다.

 

비트 연산자 "~"는 NOT의 의미를 지니고, 비트를 뒤집는 역할을 한다 (0 -> 1, 1 -> 0)

 

unsigned int 0은 실제로 "0"이 32개이므로, 이를 뒤집으면 "1"이 32개가 된다.

 

비트 연산자 ">> 2"는 비트를 오른쪽으로 2번 shift하란 뜻이 되고, 앞의 비트는 자동으로 0으로 채워진다.

 

최종적인 결과는 앞의 두 비트는 "0"이고, 나머지 30개의 비트는 "1"인 수가 된다.

 

결국 (~0U >> 2) = "1,073,741,823", 10억 7천이 조금 넘는 자연수가 된다.

 

이 수의 장점은 위의 수들의 장점을 모두 포함한다. 또한, 이 자기 자신은 한 번 더하면 INT_MAX과 같은 값을 지니므로, 저격 데이터를 피할 수 있다.

---

이외의 경우는 이야기할 필요가 없거나, 위의 경우와 비슷한 맥락이 대다수이다.

6. 3줄 요약

지금까지의 이야기를 정리하면 다음과 같이 쓸 수 있다.

 

1. INF = INT_MAX는 최대한 피하자.
2. 987654321, int(1e9), 0x3f 등 여러 수를 써도 된다. 다만 완전히 안전하지 않다.
3. 가장 안전한 것은 INF = (~0U >> 2)이다.

도움이 되었다면 지나가는 길에 하트 하나 눌러주세요, 양질의 글을 쓰는데 하나의 동기부여가 됩니다😍

지적이나 오타 수정 댓글 환영합니다!!