탐색 방법 — 같은 답, 다른 일의 양
🎬 번호순으로 놓인 카드 100장에서 73번을 찾습니다. 하나씩 넘기면 73장, 반씩 줄이면 6장 — 같은 답인데 일의 양이 다른 까닭을 2분 10초 애니메이션으로 따라가 봅니다.
🃏한눈에 보는 뒤집은 카드 수
카드 100장에서 73번 찾기 — 하나씩
73장 뒤집음
같은 문제 — 반씩 줄이기
6장 뒤집음
카드 100장, 가장 운이 나쁠 때
100장 vs 7장
카드를 두 배로 늘리면
두 배 vs 한 장만 늘어남
카드 100만 장
100만 장 vs 20장
반씩 줄이려면 반드시 필요한 것
카드가 순서대로 놓여 있어야 함
🃏 핵심: 두 방법 모두 같은 답을 찾아냅니다. 다른 것은 뒤집어야 하는 카드 수입니다. 카드가 많아질수록 그 차이가 벌어져서, 100만 장에서는 100만 번과 20번이 됩니다. 더 빠른 컴퓨터를 쓴다고 뒤집을 카드 수가 줄어들지는 않습니다 — 일의 양은 방법이 정합니다.
🔎한 걸음 더
영상 마지막에
이 기호를 제대로 다루는 것은 중학교에서 배우는 내용입니다. 지금은 기호를 외우지 않아도 괜찮습니다. "같은 답이라도 방법에 따라 뒤집는 카드 수가 크게 다르다"만 남으면 충분합니다.
O(n), O(log n)이라는 기호가 나옵니다.
카드가 늘어날 때 일의 양이 어떻게 늘어나는지를 짧게 적는 약속입니다.
O(n)은 카드가 두 배가 되면 일도 두 배가 된다는 뜻이고,
O(log n)은 카드가 두 배가 되어도 일은 한 번만 늘어난다는 뜻이에요.이 기호를 제대로 다루는 것은 중학교에서 배우는 내용입니다. 지금은 기호를 외우지 않아도 괜찮습니다. "같은 답이라도 방법에 따라 뒤집는 카드 수가 크게 다르다"만 남으면 충분합니다.
반씩 줄이는 방법에는 조건이 하나 있습니다.
카드가 번호순으로 놓여 있어야 합니다. 섞여 있으면 "가운데보다 크다·작다"를 판단할 수 없어서,
찾는 카드가 분명히 있는데도 없다고 답해 버립니다. 영상 03에서 그 장면을 직접 보여 줍니다.
섞여 있을 때는 하나씩 넘기는 방법이 느리지만 확실합니다.