01 — 선형 탐색

돌핀쌤이 보물 상자 여러 개를 앞에 두고 두 친구에게 "상자를 하나씩 열어서 보물을 찾아봐요!"라고 말하는 도입 장면

🐬 돌핀쌤: "오늘은 상자를 여러 개 가져왔어요. 그중 딱 하나에만 보물이 들어 있대요. 어느 상자에 있을까요?"

🙋‍♂️ 제네릭: "열어보기 전엔 모르니까, 앞에서부터 하나씩 차례대로 열어보면 되겠네요!"

🎯 오늘 완성할 코드는?

오늘 우리가 만들 건 선형 탐색이에요. 리스트(값을 한 줄로 늘어놓은 것)를 처음부터 하나씩 차례대로 확인해서, 찾는 값이 몇 번째 칸(인덱스) 에 있는지 알아내는 코드예요.

먼저 완성된 모습부터 볼게요. 지금은 이해 안 돼도 괜찮아요. 아래에서 한 줄씩 천천히 뜯어볼 거예요.

boxes = [15, 7, 42, 3, 28]   # 숫자들이 담긴 리스트
target = 3                    # 찾는 값(보물)
for i in range(len(boxes)):   # 인덱스 0부터 끝까지
    if boxes[i] == target:    # i번 인덱스의 값이 찾는 값이면
        print(i, "번 인덱스에서 찾았어요!")
        break                 # 찾았으니 멈추기
else:
    print("리스트에 없어요.")

실행하면 이렇게 나와요.

3 번 인덱스에서 찾았어요!

리스트 [15, 7, 42, 3, 28] 에서 3 을 찾았더니 인덱스 3 이라고 알려줬어요.

🐬 돌핀쌤: "10줄도 안 되는 짧은 코드지만, 값을 찾는 핵심이 다 들어 있어요. 지금부터 이 코드가 어떻게 보물을 찾아내는지 하나씩 풀어볼게요. 다 보고 나면 위 코드가 술술 읽힐 거예요."

💡 어떻게 풀까? — 앞에서부터 한 칸씩 열어보기

겉으로는 다 똑같이 생긴 상자(리스트)예요. 어느 칸에 보물이 있는지는 열어 봐야 알 수 있죠.

여기서 한 가지 약속! 컴퓨터는 칸 번호를 0번부터 세요. 이 번호를 인덱스(index) 라고 해요.

리스트:  [15] [ 7] [42] [ 3] [28]
인덱스:    0    1    2    3    4

규칙은 딱 하나예요. "인덱스 0부터 한 칸씩 열어서, 찾는 값이면 멈추기"

리스트 [15, 7, 42, 3, 28] 에서 3 을 찾아볼게요.

인덱스 0 → 15 == 3? 아니요, 다음!
인덱스 1 →  7 == 3? 아니요, 다음!
인덱스 2 → 42 == 3? 아니요, 다음!
인덱스 3 →  3 == 3? 찾았어요! 여기서 멈춤

리스트 [15,7,42,3,28]에서 3을 인덱스 0부터 차례로 확인해 찾는 4단계 진행 도식

이렇게 리스트를 처음 인덱스부터 끝까지 한 칸씩 확인하는 방법을 선형 탐색(Linear Search) 이라고 해요. '선형'은 "직선처럼 쭉 이어진"이라는 뜻이에요.

🙋‍♀️ 람다: "인덱스 3에서 찾았으니, 인덱스 4는 열어볼 필요도 없네요!"

🔍 코드 한 줄씩 뜯어보기

이제 맨 위에서 본 완성 코드를 한 줄씩 볼게요.

① 리스트와 찾는 값을 준비해요

boxes = [15, 7, 42, 3, 28]   # 숫자들이 담긴 리스트
target = 3                    # 찾는 값(보물)

boxes 가 바로 리스트, target 은 우리가 찾는 보물 값이에요.

② 인덱스 0부터 끝까지 하나씩 돌아요

for i in range(len(boxes)):   # 인덱스 0부터 끝까지

len(boxes) 는 리스트의 칸 개수(여기선 5)예요. range(len(boxes)) 는 그만큼 0, 1, 2, 3, 4 를 순서대로 i 에 넣어 줘요. 그래서 boxes[i] 로 첫 칸부터 끝 칸까지 하나씩 확인하게 되죠.

③ 찾는 값이면 알려주고 멈춰요

    if boxes[i] == target:    # i번 인덱스의 값이 찾는 값이면
        print(i, "번 인덱스에서 찾았어요!")
        break                 # 찾았으니 멈추기

boxes[i] 가 target 과 같으면 보물을 찾은 거예요. 몇 번 인덱스인지 알려주고, break 로 바로 멈춰요.

💡 break 가 없으면 어떻게 될까요? 인덱스 3에서 보물을 찾고도 인덱스 4까지 계속 열어보게 돼요. 찾았으면 멈추는 게 중요해요!

④ 끝까지 없으면 알려줘요 (for-else)

else:
    print("리스트에 없어요.")

이 else 는 if 에 붙은 게 아니라 for 에 붙은 else 예요. 반복이 한 번도 break 하지 않고 끝까지 갔을 때 — 즉 리스트에 보물이 없을 때만 실행돼요.

🐬 돌핀쌤: "찾으면 break, 끝까지 없으면 else! 이 한 쌍이 선형 탐색의 핵심이에요."

⑤ 전체가 어떻게 굴러가는지 — `[15, 7, 42, 3, 28]` 에서 `3` 찾기

인덱스 0: boxes[0]=15 == 3? 아니요  → 다음
인덱스 1: boxes[1]= 7 == 3? 아니요  → 다음
인덱스 2: boxes[2]=42 == 3? 아니요  → 다음
인덱스 3: boxes[3]= 3 == 3? 예!     → 출력 후 break (멈춤)

총 4번 확인해서 인덱스 3에서 찾았어요. else 는 실행되지 않아요(중간에 break 했으니까요).

🙋‍♂️ 제네릭: "break 로 멈췄으니까 else 의 '리스트에 없어요'는 안 나오는 거군요!"

✍️ 직접 완성해보기

이제 빈칸을 채워 직접 완성해봐요. 위에서 본 그대로예요.

boxes = [15, 7, 42, 3, 28]
target = 3
for i in range(len(boxes)):
    if boxes[i] == ___:       # i번 칸이 찾는 값이면
        print(i, "번 인덱스에서 찾았어요!")
        ___                   # 찾았으니 멈추기 (break)
else:
    print("리스트에 없어요.")

🐬 돌핀쌤: "막히면 위 '코드 한 줄씩 뜯어보기'로 다시 올라가서 확인해요. 다 채웠으면 맨 위 🎯 완성 코드와 비교해보세요. 정답을 외우는 게 아니라 왜 그런지 떠올리는 게 진짜 공부예요."

📌 오늘 배운 것

개념	설명
리스트	값을 한 줄로 늘어놓은 것 (상자 한 줄)
인덱스	리스트에서 몇 번째 칸인지 가리키는 번호 (0부터 시작)
선형 탐색	리스트를 인덱스 0부터 끝까지 하나씩 차례대로 확인하기
`break`	찾으면 바로 멈추기 (없으면 끝까지 계속 확인)
`for`-`else`	`break` 없이 끝까지 갔을 때만 실행 → "리스트에 없어요"

🐬 돌핀쌤: "앞에서부터 한 칸씩, 찾으면 break, 끝까지 없으면 else! 이 세 박자면 어떤 리스트에서도 값을 찾을 수 있어요. 잘했어요! 👏"

▸ 더 해보기 — 여기서부터는 선택!

여기까지가 오늘의 필수 내용이에요. 아래는 여유 있을 때 도전하는 내용이고, 예제 문제로 직접 풀어볼 수 있어요. 외울 필요는 없어요.

리스트를 인덱스 0부터 하나씩 확인한다는 뼈대는 그대로 두고, 무엇을 확인하느냐만 바꾸면 다른 일도 할 수 있어요. 모두 같은 선형 탐색이에요.

같은 값이 몇 개인지 세기 — 이번엔 break 로 멈추지 않아요. 끝까지 보면서 같은 값을 만날 때마다 count 를 +1 하면 개수를 셀 수 있어요. → 예제로 연습
가장 큰 값과 그 인덱스 찾기 — '지금까지 본 것 중 가장 큰 값'의 인덱스를 기억하는 변수를 두고, 더 큰 걸 만나면 바꿔요. → 예제로 연습
'못 찾음'은 -1로 표시 — 인덱스로 절대 나올 수 없는 -1 을 '못 찾음' 표시로 써요. 0 으로 하면 인덱스 0과 헷갈리니까요.

주황머리 여자아이 람다가 리스트 칸들을 가리키며 밝게 "찾는 값이 어느 인덱스에 있느냐가 중요하겠네요!"라고 말하는 장면

참고 — 운이 좋을 때, 운이 나쁠 때 (시간복잡도)

찾는 값이 리스트의 어느 인덱스에 있느냐에 따라 빨리 찾기도, 오래 걸리기도 해요.

경우	값의 위치	확인한 횟수
운 좋을 때	맨 앞 인덱스	1번
보통	중간쯤	n/2번
운 나쁠 때	맨 끝 / 없음	n번

리스트 길이가 n이면 최악일 때 n번을 다 확인해야 해요. 리스트가 10배 길어지면 확인 횟수도 10배 늘어나요. 이걸 O(n) ('오 엔'이라고 읽어요)이라고 해요.

리스트 길이 n이 늘수록 확인 횟수가 비례해 늘어나는 O(n) 직선 그래프

리스트 길이 (n)	최악일 때 확인 횟수
10칸	10번
100칸	100번
1,000,000칸	1,000,000번

🐬 돌핀쌤: "선형 탐색은 순서가 정리 안 된 리스트에서도 쓸 수 있다는 큰 장점이 있어요. 다만 리스트가 길어지면 느려질 수 있죠. 다음 시간엔 더 빠르게 찾는 방법(이진 탐색)도 배울 거예요!"

01 — 선형 탐색

📃 해결할 문제

💻 예제 입력 1

🖨️ 예제 출력 1