알고리즘 미니 프로젝트

dreamya (70)in #krsuccess • 5 days ago

정렬·탐색 감 잡는 미니 프로젝트: “전화번호부 검색기” 만들기

이번 편은 진짜로 손에 땀 나는 파트!
4-4에서 정렬과 탐색을 맛봤다면, 이번 4-5. 알고리즘 미니 프로젝트에서는 내가 직접 문제를 쪼개서 설계하고, 구현하고, 테스트까지 해보는 시간을 가져볼게요. 솔직히 말하면… 저도 예전에 이거 만들다가 “어? 내가 원하는 대로 안 찾아오네?” 하면서 한참 삽질했거든요. 그 실패담도 같이 풀어볼게요. 😄

오늘 만들 것: 전화번호부 검색기

기본 아이디어는 이거예요.

사람 이름과 전화번호가 들어있는 “전화번호부”가 있다
사용자가 이름을 입력하면
정렬된 구조를 기준으로 빠르게 찾아준다
못 찾으면 “없어요”라고 친절하게 말한다

여기서 중요한 건 “무작정 다 훑는 방식(선형 탐색)” 말고,
우리가 이전에 배운 이진 탐색을 쓰는 느낌이에요.

프로젝트 목표(딱 3개만)

전화번호부 데이터를 준비한다
이름 기준으로 정렬한다
정렬된 데이터에 대해 이진 탐색으로 검색한다

그리고 보너스로:

입력이 없거나 공백이면 처리
대소문자 차이(“kim” vs “Kim”)도 대충 대응
이 정도만 해줘도 꽤 “프로그램 같다” 느낌 나요.

전체 흐름(입력 → 처리 → 출력)

프로그램 흐름은 이렇게 생각하면 편해요.

(시작) 데이터 준비
(전처리) 이름으로 정렬
(반복) 사용자 입력 받기
(탐색) 이진 탐색으로 찾기
(출력) 찾으면 전화번호 출력, 아니면 “없음” 출력
(종료) 사용자가 끝내기 입력하면 종료

단계 1) 데이터 만들기

일단 예시 데이터를 만들어둘게요.
실제 전화번호부처럼 “이름-번호” 쌍이 여러 개 있는 형태요.

contacts = [
    ("Kim", "010-1234-5678"),
    ("Lee", "010-2222-3333"),
    ("Park", "010-7777-8888"),
    ("Choi", "010-9999-0000"),
    ("Jung", "010-4444-5555"),
]

음… 여기서 한 가지!
이진 탐색은 “정렬이 되어 있어야” 정상 동작해요.

그래서 다음 단계가 핵심!

단계 2) 정렬하기 (이름 기준)

이름으로 정렬합니다. (대소문자 때문에 검색이 꼬이면, 미리 통일해두는 게 좋아요)

contacts_sorted = sorted(contacts, key=lambda x: x[0].lower())

나름(?) 팁 하나:
탐색할 때도 입력을 같은 방식으로 lower()로 맞춰줘야 매칭이 깔끔해져요.
저는 예전에 “왜 없다고 하지?” 하고 한참 봤는데, 입력은 원래 대소문자였고 정렬 기준은 lower였더라구요… 아! 그때 진짜 어이가 없었어요. 😅

단계 3) 이진 탐색 구현하기

이제 “이진 탐색 함수”를 만들어요.
목표: 입력한 이름을 기준으로 전화번호부에서 찾아오기.

def binary_search_contacts(contacts, target_name):
    target = target_name.lower()
    left, right = 0, len(contacts) - 1

    while left <= right:
        mid = (left + right) // 2
        mid_name = contacts[mid][0].lower()

        if mid_name == target:
            return contacts[mid][1]  # 전화번호 반환
        elif mid_name < target:
            left = mid + 1
        else:
            right = mid - 1

    return None

여기서 내가 중요하다고 느낀 포인트는 딱 하나예요.

contacts는 반드시 정렬된 상태
비교는 lower()로 통일해서 대소문자 이슈를 제거

솔직히 말하면, 이 부분에서 조건 방향 하나만 뒤집혀도 “항상 못 찾는” 일이 생겨요.
저도 한번… “<”랑 “>”를 바꿔놓고 몇 분 동안 멍 때렸습니다. 그럴 때 진짜 웃기죠. 나만 그런 거 아니지? 어? 😄

단계 4) 사용자 입력 받고 실행하기

이제 “검색기”처럼 동작하게 만들 차례!

def run_search_app():
    contacts_sorted = sorted(contacts, key=lambda x: x[0].lower())

    print("전화번호부 검색기 시작! (이름을 입력하세요)")
    print("종료하려면 'exit'를 입력하면 돼요.")
    print("-" * 40)

    while True:
        name = input("찾을 이름: ").strip()

        if name.lower() == "exit":
            print("종료합니다. 안녕!")
            break

        if not name:
            print("이름이 비어 있어요. 다시 입력해볼까요? 아, 그냥 공백이면 안 돼요! 😅")
            continue

        result = binary_search_contacts(contacts_sorted, name)

        if result:
            print(f"{name}의 전화번호는 {result} 입니다.")
        else:
            print(f"아! {name}은(는) 전화번호부에 없어요.")
        
        print("-" * 40)

그리고 실행!