🎮 이 단원이 게임에서 쓰이는 곳
게임에서 인벤토리 100개일 때 "3번 슬롯 보기"는 한 번에 끝나고, "이름이 '검'인 슬롯 찾기"는 끝까지 볼 수도 있어요. 이런 걸 성능(시간 복잡도)으로 나누어 생각해요.
성능이란? — "몇 번 만에 끝나나"
성능이란, 일을 할 때 얼마나 빨리 끝내는지, 또는 몇 번의 단계로 끝내는지를 말해요. 초등학생도 생각해 볼 수 있어요.
예: 반에서 이름표 30개 중에 "철수" 이름표를 찾는다고 해요.
- 방법 1 — 하나씩 처음부터 보기: 운이 나쁘면 30번까지 봐야 해요.
- 방법 2 — 이름이 가나다 순으로 줄 세워 두었으면, "철수는 'ㅊ'이니까 뒤쪽이겠다" 하고 반씩 나눠서 찾기: 훨씬 적은 번만에 찾을 수 있어요.
같은 "찾기"인데, 어떤 방법을 쓰느냐에 따라 "몇 번 만에 끝나나"가 달라져요. 이걸 나중에 빅오로 대략적으로 나타내요.
실생활 예제로 느끼기
예 1: 책장에서 책 찾기
책장에 책 100권이 번호 순으로 1번, 2번, …, 100번 들어 있어요.
- "47번 책 주세요" → 47번째 칸에 가면 끝. 한 번에 찾아요.
- "제목이 '파이썬'인 책 주세요" → 어디 있는지 모르니까 처음부터 끝까지 볼 수도 있어요. 운이 나쁘면 100번까지 봐야 해요.
그래서 "몇 번째 칸이야?"라고 위치를 알고 있으면 한 번에 끝나고, "이름으로 찾기"는 개수만큼 볼 수 있다고 생각하면 돼요.
예 2: 반 친구끼리 악수
반에 30명이 있어요. 한 명이 나머지 모두와 악수를 한다고 하면, 그 한 명은 29번 악수해요. 이걸 30명 모두가 하면, 대략 30×29 ≈ 900번 정도 돼요. (같은 악수를 두 번 세지 않아도, "번 수"는 n×n에 비례해요.)
즉, 사람 수가 많아질수록 악수 횟수는 "n×n"처럼 빨리 늘어나요. 이런 걸 나중에 O(n²)라고 써요.
빅오 표기법 — "대략 몇 번에 비례하나"
컴퓨터도 "데이터가 n개일 때, 최악이라면 대략 몇 번 일을 하게 되나?"를 수학적으로 간단히 나타내요. 그게 빅오( Big O )예요. 정확한 초 단위가 아니라, 개수가 늘어나면 단계 수가 얼마나 늘어나는지를 보는 거예요.
아래는 시험에 나올 수 있는 표기예요. "실생활로 치면 이런 느낌"만 잡으면 돼요.
- O(1) — 한 번에 끝. 예: "n번째 칸에 있는 값 보기". 책 100권이 있어도 "47번 책"은 47번째 가면 끝.
- O(n) — 개수 n만큼, 최대 n번. 예: 이름표 30개 중 "철수"를 처음부터 하나씩 찾기. 100권 중 제목으로 찾기.
- O(n²) — 대략 n×n에 비례. 예: 반 30명이 서로 악수. 버블 정렬처럼 "모두와 비교"를 n번 반복하는 경우.
정리하면, 성능(시간 복잡도) = "데이터가 많아질 때, 단계 수가 얼마나 늘어나는가"를 빅오로 나타낸 거예요.
"O(n²) 알고리즘에 데이터 10만 개 넣으면?" → 프로그래머가 커피 마시러 갑니다. (단계가 100억 번 가까이 되니까요.) "O(1)이면?" → 넣든 1개 넣든 100만 개 넣든 한 번에 끝나니까 "효율 있다"고 말해요. 그래서 시험에서 "시간 복잡도가 O(n²)인 정렬"이 나오면 "데이터가 많을수록 단계가 n×n으로 늘어난다 = 많으면 느리다"라고 판단하면 돼요.
또 "무한 루프에 걸렸어요" "그거 O(∞) 아니에요?" 같은 말도 있어요. 빅오는 "대략 몇 번에 비례하나"를 쓰는 거라, 끝나지 않으면 복잡도만으로는 안 세요. 그래도 "효율이 있나 없나"는 "n이 커질 때 단계가 얼마나 불어나나"로 대략 보면 됩니다.
효율 있나 없나 — 대략 판단 근거
시험이나 실무에서 "이거 효율 있나?"를 대략 보려면 아래만 기억해도 돼요.
- O(1) — 데이터가 10개든 10만 개든 단계 수가 거의 그대로면 → 효율 좋음. "몇 번째 칸 보기"처럼 위치만 알면 한 번에 끝나는 연산.
- O(n) — 데이터 n개면 단계가 n번 정도 비례하면 → 보통 괜찮음. "처음부터 끝까지 한 번 훑기"가 이에 해당해요. n이 100만이면 대략 100만 번이니까, 컴퓨터가면 허용되는 경우가 많아요.
- O(n²) — n개면 대략 n×n번 비례하면 → 데이터가 많으면 느려짐. n=1만이면 1억 번, n=10만이면 100억 번 가까이 되니까 "효율 없다"고 보는 기준이에요. 버블 정렬처럼 "모두와 비교"를 반복하면 보통 O(n²)이에요.
판단 요약 "위치를 알고 한 번에 접근" → O(1) → 효율 있음. "한 번 쭉 훑기" → O(n) → 보통 허용. "모두와 비교·반복"가 두 겹이면 O(n²) 의심 → 데이터 많을 때 효율 없음. 이 정도만 있어도 "효율 있나 없나"를 대략 말할 수 있어요.
게임에서의 예
게임 인벤토리에 슬롯 10개가 있어요.
- "3번 슬롯에 뭐 있어?" → 3번째 칸만 보면 되니까 O(1).
- "이름이 '검'인 슬롯이 어디야?" → 처음부터 끝까지 볼 수 있으니까 최대 10번 → O(n).
그래서 "몇 번째인지 아는 칸 보기"는 O(1), "이름으로 찾기"는 O(n)이라고 외우면 돼요.
한 줄 요약
성능 측정 = "몇 번 만에 끝나나"를 생각하는 것. 빅오는 그걸 "대략 n번? n×n번?"처럼 간단히 쓴 거예요. O(1) = 한 번에, O(n) = n개면 최대 n번, O(n²) = n×n에 비례. 실생활의 "책장에서 번호로 찾기 / 이름으로 찾기 / 악수"처럼 생각하면 쉬워요.