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

"리스트에서 3을 찾아 주세요"라는 부탁을 받았다고 해 봅시다. 바로 코드를 쓰고 싶지만, 막상 쓰려고 하면 정해지지 않은 것이 많습니다. 3이 두 번 나오면 어느 위치를 알려 줘야 할까요? 3이 아예 없으면 무엇을 돌려줘야 할까요? 위치를 원하는지, 있는지 없는지만 원하는지도 분명하지 않습니다. 이 글에서는 코드를 쓰기 전에 문제를 정확한 말로 적는 연습을 합니다. 그리고 그렇게 정한 절차를 여러 가지 표현으로 옮겨 보며, 표현이 달라져도 절차는 같다는 것을 확인합니다.

"찾는다"는 말에 숨어 있는 질문들

같은 "찾기"라도 원하는 답에 따라 전혀 다른 문제가 됩니다. 처음 나오는 위치를 원할 수도 있고, 나오는 모든 위치나 나오는 횟수를 원할 수도 있습니다. 목록이 정렬되어 있다고 가정해도 되는지에 따라 쓸 수 있는 방법도 달라집니다. 이 질문들에 답하지 않고 코드를 쓰기 시작하면, 빈 목록이 들어왔을 때 오류를 낼지 "없음"을 돌려줄지 같은 결정을 구현하는 도중에 그때그때 내리게 됩니다. 그렇게 내린 결정은 코드 어딘가에 묻혀서 다른 사람은 물론 나중의 자신도 알기 어렵습니다.

그래서 먼저 문제 명세(problem specification)를 적습니다. 명세는 입력이 무엇이고, 어떤 출력이 정답인지 정한 약속입니다. 이 글에서 다룰 탐색 문제의 명세는 다음과 같습니다.

• 입력: 숫자 리스트 values와 찾을 값 target. 리스트는 정렬되어 있지 않아도 됩니다.
• 출력: target이 처음 나타나는 위치의 인덱스(0부터 셈). 없으면 -1.
• 제약: 원본 리스트의 순서와 내용은 바꾸지 않습니다.

명세를 적었다면 작은 예로 정답을 미리 정해 둡니다. 특히 값이 겹치는 경우와 비어 있는 경우를 빼놓지 않습니다.

이렇게 표를 먼저 만들어 두면 빈 리스트가 오류인지 정상적인 "없음"인지를 구현하기 전에 정할 수 있습니다. 이 명세에서는 정상적인 "없음"이며, 답은 -1입니다. -1은 이 함수가 "찾지 못했다"는 뜻으로 정한 표시라는 점도 기억해 두세요. Python에서 values[-1]은 마지막 원소를 가리키므로, 이 함수의 결과를 확인 없이 인덱스로 쓰면 엉뚱한 원소를 읽게 됩니다.

입력의 제약은 풀이의 일부다

다른 문제들도 마찬가지입니다. 최소 개수의 동전으로 금액을 만드는 문제라면 금액과 사용할 수 있는 동전 단위를 정해야 하고, 단위가 모두 양수라는 조건이 필요합니다. 미로를 빠져나오는 문제라면 통로가 어떻게 연결되는지와 시작점, 목표점을 정해야 합니다. 모든 길을 한 번씩만 지나는 한붓그리기라면 점과 선의 연결 관계, 그리고 출발점으로 돌아와야 하는지를 정해야 합니다.

이때 제약은 단순한 조건이 아니라 풀이 방법을 결정합니다. 가짜 동전 찾기 문제를 예로 들어 보겠습니다. 동전 여러 개 가운데 하나만 가짜이고, 가짜는 진짜보다 가볍습니다. 후보의 수는 2의 거듭제곱이고, 두 묶음의 무게를 정확히 비교하는 저울이 있습니다. 이 조건이 모두 갖춰지면, 후보를 반씩 나눠 저울에 올리고 가벼운 쪽만 남기는 방법으로 가짜를 찾을 수 있습니다. 가짜가 더 가볍다는 조건이 없다면 어느 쪽을 남길지 정할 수 없고, 후보 수가 홀수라면 반으로 나누는 설명부터 고쳐야 합니다.

더 깊이: 저울의 결과는 세 가지다

반씩 나누는 방법으로 후보 16개를 1개로 줄이려면 16, 8, 4, 2, 1 순서로 네 번 달아야 합니다. 하지만 이것이 가장 적은 횟수는 아닙니다. 저울은 왼쪽이 가볍다, 오른쪽이 가볍다, 균형이 맞는다의 세 가지 결과를 알려 주기 때문입니다. 후보를 세 묶음으로 나눠 두 묶음만 저울에 올리면, 기울어진 쪽이 가벼운 쪽이고, 균형이 맞으면 내려놓은 묶음에 가짜가 있습니다. 한 번 달 때마다 후보가 약 3분의 1로 줄어드므로, 16개라면 16, 6, 2, 1처럼 세 번 만에 찾을 수 있습니다. 같은 문제도 도구가 주는 정보를 얼마나 쓰는지에 따라 필요한 횟수가 달라지는 것입니다. 이 생각은 2장의 마지막 글에서 "구별해야 할 경우의 수"라는 관점으로 다시 다룹니다.

같은 절차를 세 가지로 적기

명세가 정해졌다면 그것을 만족하는 절차를 설계합니다. 여기서는 가장 단순한 방법인 순차 탐색(linear search)을 씁니다. 왼쪽부터 하나씩 비교하다가 처음 같은 값을 만나면 그 위치를 돌려주는 방법입니다. 절차는 Python 코드가 아니어도 설명할 수 있습니다. 같은 절차를 자연어, 의사코드, 흐름표로 차례로 적어 보겠습니다.

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

1. 현재 위치 i를 0으로 둡니다.
2. i가 목록의 길이 이상이면, 목표가 없다는 뜻이므로 -1을 돌려주고 끝냅니다.
3. i번째 값이 목표와 같으면 i를 돌려주고 끝냅니다.
4. 같지 않으면 i를 1 늘리고 2단계로 돌아갑니다.

의사코드(pseudocode)는 특정 언어의 문법에 얽매이지 않고 절차의 뼈대만 드러내는 표기입니다. 아래에서 ←는 대입이고, 길이(목록)은 원소의 개수입니다. 이 코드는 사람이 읽기 위한 것이라 그대로 Python 파일에 넣어 실행할 수는 없습니다.

i ← 0
i < 길이(목록)인 동안 반복:
    목록[i] = 목표이면 i를 돌려주고 끝냄
    i ← i + 1
-1을 돌려주고 끝냄

흐름표는 각 단계에서 무엇을 하고, 조건이 참이거나 거짓일 때 어디로 가는지를 칸마다 적은 것입니다. 순서도(flowchart) 그림을 표로 옮긴 것이라고 생각하면 됩니다.

흐름표를 따라 [8, 3, 3, 9]에서 3을 찾아봅니다. S0에서 i는 0이고, S1의 조건은 참입니다. S2에서 목록[0]인 8은 3과 다르므로 S3으로 가서 i가 1이 됩니다. 다시 S1을 지나 S2에 오면 목록[1]이 3이므로 E발견으로 가서 1을 돌려줍니다. 뒤에 있는 두 번째 3은 읽지도 않았다는 점이 중요합니다. 처음 만나자마자 멈추기 때문에 "처음 나타나는 위치"라는 명세를 지키는 것입니다.

빈 목록이라면 S0에서 i가 0이 된 뒤, S1의 조건 0 < 0이 거짓이므로 곧바로 E없음으로 갑니다. S2에 한 번도 가지 않으니 존재하지 않는 목록[0]을 읽을 일도 없습니다. 길이를 먼저 확인하는 순서가 빈 입력에서의 오류를 막아 주는 셈입니다.

Python으로 옮기기

이제 같은 절차를 Python으로 옮깁니다. Python에서는 위치를 직접 늘리는 대신 enumerate를 쓰면 편합니다. enumerate(values)는 리스트의 원소를 하나씩 꺼내면서 그 인덱스도 함께 주고, for index, value in ...은 그 두 값을 각각 index와 value라는 이름으로 받습니다.

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

출력이 앞에서 미리 정한 정답 표와 그대로 일치합니다. 흐름표의 S1(아직 남은 원소가 있는가)과 S3(다음 위치로)은 for 반복이 대신 처리하고, S2의 비교와 E발견의 반환은 if와 return index가 맡습니다. 반복이 끝까지 돌았다면 같은 값이 없었다는 뜻이므로, 반복 뒤의 return -1이 E없음에 해당합니다. 표현은 네 번 바뀌었지만 "왼쪽부터 비교하고, 처음 같으면 멈추고, 끝까지 없으면 -1"이라는 약속은 그대로입니다.

이 함수가 명세를 지키는 이유

함수가 어떤 위치 i를 돌려줬다면, 그 앞의 위치 0부터 i-1까지는 이미 비교했고 모두 목표와 달랐습니다. 그렇지 않았다면 그보다 앞에서 멈췄을 것이기 때문입니다. 따라서 돌려준 위치는 목표가 처음 나타나는 위치입니다. 반대로 -1을 돌려줬다면 반복이 모든 원소를 비교하고도 같은 값을 찾지 못한 것이므로 목표는 목록에 없습니다. 함수는 목록에 원소를 더하거나 빼지 않고 정해진 길이만큼만 반복하므로 반드시 끝나며, 원본 리스트도 바꾸지 않습니다.

비용은 무엇의 개수로 셀까

목표가 맨 뒤에 있거나 아예 없으면, 이 함수는 원소 n개를 모두 비교합니다. 그래서 가장 오래 걸리는 경우의 비교 횟수가 n에 비례하며, 이를 O(n)이라고 씁니다. 반면 새 리스트를 만들지 않고 index와 value 같은 변수 몇 개만 쓰므로, 추가로 필요한 메모리는 n과 상관없이 일정하고 이를 O(1)이라고 씁니다. 이 표기의 정확한 뜻은 2장의 마지막 글에서 다룹니다.

여기서 n이 무엇인지 분명히 해야 합니다. n은 찾는 값의 크기가 아니라 입력 리스트의 길이입니다. 3을 찾든 3,000을 찾든 비교 횟수는 리스트 길이에 따라 정해집니다. 또 리스트를 파일이나 네트워크에서 읽어 오는 데 드는 시간은 탐색 자체의 비용과 따로 생각합니다. 무엇을 셌는지 밝히지 않은 비용은 비교할 수 없기 때문입니다.

정리

• 코드를 쓰기 전에 입력, 출력, 제약을 명세로 적고, 값이 겹치는 경우와 빈 입력을 포함한 작은 예로 정답을 미리 정합니다.
• 입력의 제약은 풀이 방법을 결정합니다. 조건이 하나 바뀌면 같은 설명이 더 이상 성립하지 않을 수 있습니다.
• 같은 절차를 자연어, 의사코드, 흐름표, Python으로 옮겨도 비교하는 순서와 멈추는 조건은 같습니다.
• 순차 탐색은 왼쪽부터 비교하다가 처음 같은 값에서 멈추므로 첫 위치를 돌려주고, 끝까지 없으면 -1을 돌려줍니다.
• 비용을 말할 때는 n이 무엇의 개수인지 먼저 밝힙니다. 순차 탐색에서 n은 리스트의 길이입니다.

연습 문제

1. 위치 대신 개수를 묻는다면

입력 [5, 5, 2]에서 목표 5의 위치가 아니라 나오는 횟수를 구하는 문제로 바꾸려고 합니다. 출력에 대한 약속과 반복을 멈추는 조건을 어떻게 바꿔야 할까요?

def count_target(values, target):
    count = 0
    for value in values:
        if value == target:
            count += 1
    return count


print(count_target([5, 5, 2], 5))
print(count_target([5, 5, 2], 7))
print(count_target([], 5))

2
0
0

2. 반씩 나누는 저울 문제

가짜 동전 문제의 조건(가짜 하나가 더 가볍고, 정확한 저울로 두 묶음을 비교함)을 그대로 두고, 후보 16개를 매번 두 묶음으로 반씩 나눠 단다면 후보를 하나로 줄이기까지 몇 번 달아야 할까요?

3. 흐름표를 끝까지 따라가기

흐름표에서 [8, 3, 3, 9]의 목표를 9로 바꾸면 S3은 몇 번 실행되고 무엇을 돌려줄까요? 빈 목록에서 목표 3을 찾을 때는 S2에 도달할까요?

다음 글 불변조건·종료와 반례 찾기에서는 "이 함수가 명세를 지킨다"는 설명을 불변조건과 종료 조건으로 더 엄밀하게 다룹니다. 미로 문제는 그래프 탐색에서, 한붓그리기는 그래프 표현에서 다시 만납니다.