(a+b)/2 과 a+(b-a)/2 의 차이 (feat. Integer Overflow, Leetcode 374)

(a+b)/2 과 a+(b-a)/2의 결과값은 같다.
하지만 전자는 일시적으로 데이터 타입의 허용범위를 넘길 수 있다.

 

 

겪은 문제

코딩테스트 중 입력받은 int n 값이 int의 최대허용범위 근처의 큰 수일때만 통과하지 못 했다.

 

 

• int 타입의 start, end 변수 두 개가 있다.
• 경우에 따라 start의 값을 mid+1로 변경하는 분기가 존재한다.

 

첫번째 시행

• n의 값이 int 타입의 최대 허용범위에 근접해있고, 약 2억이라 표현해본다.
• start=1, end=2억 인 셈이다. 이 때의 mid 값을 구하기 위한 start+end값은 약 2억으로 허용범위를 초과하지 않는다.
• start=1억 정도의 값으로 변경되며 시행 마무리

두번째 시행

• int mid 값을 연산하기 위해 end+start의 값을 구할때, 2억+1억은 int의 최대허용범위를 벗어나기에 음수로 표현된다. 이는 오버플로우 현상.

mid 값을 출력. (2의 31제곱 수를 벗어나 음수로 표현된다)

 

 

---

 

결론

 

int mid = start + (end-start)/2; 로 수정

 

(start + end) / 2와 계산값은 같지만 알고리즘을 고려하였을 때 최대허용범위를 넘지않는 방향으로 계산이 가능한 연산식이다.

 

---

 

깨달은 점

컴퓨터 프로그래밍적으로 생각을 해야한다.
단순히 수식을 세우는 것이 아닌, 연산이 이루어지면서 할당된 메모리에서 어떠한 변화가 일어나는지를 고려하자.