[프로그래머스] 세균 증식

woo·2025년 11월 24일

문제 설명
어떤 세균은 1시간에 두배만큼 증식한다고 합니다. 처음 세균의 마리수 n과 경과한 시간 t가 매개변수로 주어질 때 t시간 후 세균의 수를 return하도록 solution 함수를 완성해주세요.

처음엔 단순히 n을 t만큼 제곱하면 되겠구나 생각했는데 그건 아니었고..(정신을 어디에 두는 건지..)

n을 t번만큼 2배씩 곱해주면 되는 문제였다..!
그래서 아래와 같이 for 문을 돌려서 해결!

class Solution {
    public int solution(int n, int t) {
        int answer = n;
        for(int i = 1; i <= t; i++) {
            answer = answer * 2;
        }
        return answer;
    }
}

그리고 다른 사람들 풀이를 봤는데 아래와 같은 기적의 코드를 발견..😲

class Solution {
    public int solution(int n, int t) {
        int answer = 0;

        answer = n << t;

        return answer;
    }
}

answer = n << t;

진짜 너무 깜짝 놀람..
알아보니 아래와 같다고 한다

🚀 코드 분석: 비트 시프트 연산 (`<<`)

1. 연산의 의미

answer = n << t;에서 사용된 << 연산자는 왼쪽 비트 시프트(Left Bit Shift) 연산자이다.

이 연산은 정수 $n$ 을 이진수로 표현했을 때, 모든 비트를 왼쪽으로 $t$ 만큼 이동시킨다.
가장 오른쪽(LSB)에 생긴 빈자리 $t$ 개는 모두 ** $0$ **으로 채워집니다.
이 연산은 수학적으로 ** $n \times 2^t$ **를 계산하는 것과 동일한 효과를 가지며, 일반적인 곱셈(*) 연산보다 CPU 차원에서 더 빠르게 처리될 수 있다.

2. 코드의 결과

따라서 이 코드는 다음과 같은 결과를 계산합니다.

$\text{answer} = n \times 2^t$

⚠️ `Math.pow()`와의 차이 및 주의사항

앞의 풀이 방식인 Math.pow(n, t)와 이 비트 시프트 방식은 몇 가지 중요한 차이가 있다.

구분	`n << t` (현재 코드)	`Math.pow(n, t)` (이전 질문)
계산하는 값	$n \times 2^t$	$n^t$ (n의 t승)
데이터 타입	`int` (정수)	`double` (실수)
적용 범위	$2^t$ 형태의 곱셈에만 적용 가능	일반적인 거듭제곱에 모두 적용 가능
성능	매우 빠름 (비트 연산)	비교적 느림 (부동 소수점 연산)

🛑 주의사항: 오버플로우 (Overflow)

int 타입은 $2^{31}-1$ 까지만 저장할 수 있다.

만약 $n \times 2^t$ 의 결과가 이 범위를 초과하면, answer 변수에는 음수를 포함한 **잘못된 값(오버플로우)**이 저장.
$n$ 이 양수일 때, $t$ 값이 31 이상이거나 최종 결과가 21억을 초과할 경우 오버플로우가 발생할 수 있으므로, 입력 값의 범위를 확인해야 한다.