문제·입출력·자료의 제약 정하기

자료를 찾으라는 말만으로는 프로그램을 만들 수 없습니다. 중복값이 있으면 어느 위치를 반환하는지, 없으면 무엇을 반환하는지 정해야 합니다. 목표는 구현 전에 입력·출력·제약·작은 예를 적는 것입니다. 함수와 리스트를 사용할 줄 알면 시작할 수 있습니다.

개념과 약속

문제 명세는 입력이 무엇이고 어떤 출력이 정답인지 정한 약속입니다. 아래 탐색 문제의 입력은 숫자 리스트와 목표값, 출력은 처음 나타나는 위치의 인덱스(0부터 셈)이며 없으면 -1입니다. 원본 순서는 바꾸지 않습니다. 정렬을 요구하지 않습니다.

동전 개수를 최소화하기, 미로에서 도착하기, 한 번에 한 간선을 지나는 길을 찾기도 각각 다른 문제입니다. 동전은 금액과 양의 동전 단위를, 미로는 통로와 시작·목표를, 한붓그리기는 정점·간선과 닫힌 길인지 여부를 먼저 정해야 합니다. 입력의 제약은 해결 방법의 일부입니다. '가짜 동전 하나가 더 가볍고, 후보 수가 2의 거듭제곱이며 정확한 저울로 두 그룹의 무게를 비교한다'는 조건이 있어야 단순한 반 나누기 설명을 사용할 수 있습니다.

같은 절차를 세 표현으로 읽기

알고리즘의 입력·결과가 정해졌다면 절차는 Python 코드 외의 방법으로도 설명할 수 있습니다. 여기서는 같은 첫 위치 탐색을 자연어, 의사코드, 분기 흐름표로 읽습니다. 표현이 달라도 왼쪽부터 비교하고 처음 일치하면 끝내는 약속은 같습니다.

자연어로 쓰면 다음과 같습니다.

1. 현재 위치 i를 0으로 둡니다.
2. i가 목록 길이 이상이면 목표가 없으므로 -1을 반환하고 끝냅니다.
3. 현재 값이 목표와 같으면 i를 반환하고 끝냅니다.
4. 같지 않으면 i를 하나 늘리고 2단계로 돌아갑니다.

의사코드는 특정 언어의 문법보다 절차를 드러내는 표기입니다. 아래 ←는 대입이고 길이(목록)은 원소 개수입니다. 그대로 Python 파일에 복사해 실행하는 코드가 아닙니다.

i ← 0
i < 길이(목록)인 동안 반복:
    목록[i] = 목표이면 i를 반환하고 종료
    i ← i + 1
-1을 반환하고 종료

분기 흐름표는 조건이 참·거짓일 때 갈 위치를 명시합니다. 순서도 그림의 모든 기호를 설계하는 과정은 선택 학습으로 남기고, 이 표에서는 제어 흐름을 정확히 읽는 데 집중합니다.

[8,3,3,9]에서 목표 3이면 S0→S1→S2→S3을 거쳐 i=1이 되고, S1→S2→E발견으로 끝납니다. 뒤의 3까지 더 읽지 않아 첫 위치를 반환합니다. 빈 목록은 S0→S1→E없음이므로 목록[0]에 접근하지 않습니다. 아래 Python의 enumerate는 위치 증가를 반복문에 맡기지만 같은 조건·반환 순서를 구현합니다.

손으로 상태 추적하기

명세를 먼저 적으면 입력이 비어 있을 때 '오류인가, 정상적인 실패인가'를 구현 중에 임의로 정하지 않습니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

enumerate(values)는 각 원소의 인덱스와 값을 함께 줍니다. for index, value in ...는 그 두 값을 각각의 이름으로 받습니다. -1은 이 함수가 정한 없음 표시이며 마지막 원소 인덱스로 사용하면 안 됩니다.

def linear_search(values, target):
    for index, value in enumerate(values):
        if value == target:
            return index
    return -1


print(linear_search([8, 3, 3, 9], 3))
print(linear_search([8, 3, 3, 9], 4))
print(linear_search([], 3))

실행 결과:

1
-1
-1

왜 맞고 언제 끝나는가

왼쪽부터 하나씩 비교하므로 반환한 인덱스 앞에는 목표가 없습니다. 일치하자마자 반환해 첫 위치라는 약속을 지킵니다. 모두 다르면 마지막 반환 -1이 정확합니다. 원소를 추가하거나 삭제하지 않고 유한한 순회를 하므로 종료합니다.

비용과 적용 범위

최악에는 n개를 모두 비교해 O(n) 시간이며 새 목록을 만들지 않아 추가 공간은 O(1)입니다. n은 목표값의 크기가 아니라 입력 목록의 길이입니다. 파일·네트워크에서 입력을 읽는 비용과 탐색 함수 자체의 비용은 따로 설명해야 합니다.

스스로 풀어 보기

1. 입력 [5, 5, 2]에서 목표 5의 '개수'를 구하는 문제라면 출력 약속과 종료 조건을 어떻게 바꿔야 하나요?
2. 가짜 동전 후보 16개를 매번 두 그룹으로 반 나누면 후보를 하나로 줄이는 비교는 몇 번인가요? 위 조건을 그대로 사용하세요.
3. 위 분기 흐름표에서 [8,3,3,9]의 목표를 9로 바꾸면 S3은 몇 번 실행되고 무엇을 반환하나요? 빈 목록에서는 S2에 도달하나요?

힌트

1. 처음 발견하자마자 반환하면 나머지 중복을 세지 못합니다.
2. 16 → 8 → 4 → 2 → 1을 적어 보세요.
3. i=0,1,2에서는 불일치하고 i=3에서 일치합니다. 빈 목록의 첫 길이 검사를 확인하세요.

해설

1. 반환값은 위치가 아니라 2이고 전체 목록을 순회하며 일치 횟수를 더합니다. 목표가 없을 때는 0입니다.
2. 네 번입니다. 이는 해당 이분 전략과 주어진 조건의 계산입니다. 임의 개수·무거움까지 미정인 동전 문제의 최적 비교 횟수라는 뜻은 아닙니다.
3. S3은 세 번 실행해 i를 0→1→2→3으로 바꾸고 3을 반환합니다. 빈 목록에서는 S1이 즉시 거짓이므로 S2에 가지 않고 -1을 반환합니다. 따라서 빈 입력에서도 인덱스 오류 없이 명세를 지킵니다.

흔한 오해

문제 이름만 같다고 입력 조건과 정답도 같은 것은 아닙니다. 문자열의 첫 위치와 모든 위치, 최단 간선 수와 최소 비용은 다른 명세입니다.

복습과 다음 연결

다음 정확성과 종료에서 명세를 지킨다는 설명을 코드의 반복과 연결합니다. 미로는 그래프 탐색, 한붓그리기는 그래프 표현에서 다시 만납니다.