문제·입력·출력·제약과 알고리즘

빠른 답보다 먼저 맞는 문제를 정한다

“가장 가까운 배송센터를 찾는다”는 부탁을 받았다고 하자. 가까움이 도로상 이동거리인지 직선거리인지, 닫힌 센터도 고를 수 있는지, 같은 거리의 센터가 둘이면 어느 쪽인지 먼저 정해야 한다. 가장 가까운 곳과 배송비가 가장 싼 곳도 같다고 보장할 수 없다. 목적을 바꾸고도 같은 정답이라고 할 수는 없다.

입력은 판단에 주어진 자료이고, 출력은 그 자료로 만들어 돌려줄 결과다. 고객 위치와 센터 목록을 입력으로 받아 센터의 이름표에 해당하는 식별자를 돌려줄 수 있다. 그러나 거리만 돌려주면 어떤 센터를 선택했는지 알 수 없으므로 출력 형식도 약속해야 한다.

먼저 무엇을 정답으로 인정할지 적고, 그다음 그 답을 찾는 순서를 만든다. 이 절에서는 싼 상품을 고르는 작은 문제부터 따라간 뒤 같은 후보 갱신 방법을 배송센터 선택에 적용한다. 정확한 해법이 여러 개라면 그때 시간·메모리·구현 부담을 비교한다.

먼저 되짚기: 입력과 출력 사이에 처리 규칙이 있다

입력–처리–출력 모델은 시스템 행동을 가장 작게 펼치는 틀이었다. 계산문제에서는 입력 집합, 원하는 출력, 둘 사이의 올바른 관계와 제약을 먼저 적는다. 알고리즘은 그 관계를 실제 유한 단계로 구현한다.

입력·출력에서 문제 명세로 좁힌다

그림의 왼쪽에서는 어떤 자료까지 받아들일지, 오른쪽에서는 어떤 결과가 맞는지 묻는다. 가운데의 처리 방법부터 고르면 ‘입력이 비었을 때 무엇을 돌려줄까’ 같은 약속을 놓치기 쉽다. 앞에서 배운 입력·처리·출력은 이처럼 계산문제의 허용 입력·기대 출력·제약·성공조건으로 구체화된다.

문제 명세

문제 명세는 입력·출력·제약·성공조건으로 계산문제를 정확히 표현한 것이다. 입력은 가능한 값과 크기, 출력은 만들어야 할 결과와 형식, 제약은 시간·메모리·허용값·업무 규칙, 성공조건은 모든 허용 입력에 대해 결과가 옳다는 판정 기준을 담는다.

‘최저가 상품을 고른다’를 예로 들면 가격 목록이 입력, 상품 식별자가 출력이다. ‘음수 가격은 받지 않는다’는 허용 입력의 경계이고, ‘같은 가격이면 먼저 나온 상품을 고른다’는 결과를 하나로 정하는 규칙이다. 가장 싼 상품을 골랐더라도 동률 규칙을 어겼다면 이 명세에서는 틀린 답이다.

빈 목록을 허용한다면 그때의 답도 정해야 한다. 자료가 하나도 없다는 것은 가격이 0인 상품이 있다는 뜻이 아니므로, 여기서는 상품 식별자 대신 없음을 반환한다. 허용하지 않은 자료를 받은 입력 오류와도 구분한다.

알고리즘 전에 문제 계약을 다시 고정한다

문제 명세는 입력·출력·제약·성공조건을 정한다. 알고리즘은 이 계약을 만족해야 하므로 해법보다 먼저 무엇이 정답인지 고정한다.

해법은 명세가 정한 동률과 빈 입력까지 따라야 한다

최솟값만 찾는 절차라도 동률에서 먼저 나온 항목을 고르는지, 빈 입력에서 무엇을 반환하는지 명세가 다르면 다른 알고리즘 계약이 된다. 예를 들어 가격이 같은 B와 C 중 먼저 나온 B를 고르라는 약속에서는, 나중에 본 C로 바꾸는 동작을 해서는 안 된다. 이 차이가 아래 코드에서 ‘더 작다’와 ‘작거나 같다’의 선택으로 나타난다.

알고리즘

알고리즘(algorithm)은 유한한 단계로 입력을 원하는 출력으로 바꾸는 명확한 절차다. 각 단계는 수행할 수 있을 만큼 분명하고, 허용된 입력에서 종료하며, 종료 결과가 문제 명세의 성공조건을 만족해야 한다. 같은 문제를 푸는 여러 알고리즘은 정확성은 같아도 입력이 커질 때 드는 시간과 공간이 다를 수 있다.

‘적당히 싼 상품을 찾는다’에는 얼마를 비교하고 언제 멈출지가 없다. 반면 ‘첫 상품을 후보로 두고, 나머지를 하나씩 보며 더 싼 상품을 만나면 후보를 바꾼다’는 실행할 동작이 정해져 있다. 마지막 항목까지 한 번씩 본 뒤 끝낸다는 종료 기준도 있다.

가장 싼 상품을 찾는 작은 예

다음은 실제 상점의 정책이 아니라 설명을 위한 문제다.

• 입력: 식별자와 0 이상 정수 가격을 가진 상품 목록. 빈 목록도 허용한다.
• 출력: 가장 낮은 가격의 상품 식별자. 빈 목록이면 없음.
• 제약: 같은 최저가격이면 입력에서 먼저 나온 상품을 고른다. 허용하지 않은 가격·누락된 식별자가 있으면 입력 오류이며 일부 결과를 정답으로 내보내지 않는다.
• 성공조건: 반환한 상품보다 더 싼 상품이 목록에 없고 동률 규칙을 지킨다.

아래는 특정 언어의 문법 대신 실행 순서를 읽기 쉽게 적은 의사코드다. 후보 = 현재 상품은 후보로 기억할 항목을 바꾸라는 뜻이고, <는 왼쪽 가격이 오른쪽보다 작은지 묻는다. 반환하면 그 호출의 처리를 끝내고 결과를 돌려준다.

목록의 모든 항목이 허용 형식인지 검사한다
잘못된 항목이 있으면 입력 오류 반환
목록이 비었으면 없음 반환
후보 = 첫 상품
두 번째 상품부터 차례로 반복:
    현재 상품 가격 < 후보 가격이면 후보 = 현재 상품
후보 식별자 반환

후보를 0원짜리 가상 상품으로 시작하면 안 된다. 모든 실제 상품이 0원보다 비싸면 가상 상품이 끝까지 남기 때문이다. 실제 첫 상품으로 시작하면 후보가 언제나 입력 안의 상품이라는 조건을 지킬 수 있다.

각 반복을 마칠 때마다 유지되어야 하는 설명을 반복 불변조건이라고 부른다. 여기서는 ‘후보는 지금까지 본 상품 중 가장 싸며, 그 가격에서는 가장 먼저 나온 상품’이다. 처음에는 한 상품만 보았으므로 성립한다. 새 가격이 더 작으면 바꾸고, 같거나 크면 유지하면 이 설명은 다음 단계에서도 성립한다. 모든 상품을 본 뒤에는 ‘지금까지 본 상품’이 전체 목록이 되므로 명세가 요구한 답을 얻는다.

이는 후보의 값이 절대 바뀌지 않는다는 뜻이 아니다. 후보는 A에서 B로 바뀔 수 있지만 후보가 지켜야 하는 관계가 계속 유지된다는 뜻이다. 결과가 맞는 이유와 반복이 끝나는 이유도 구별해야 한다. 종료는 아직 보지 않은 상품 수가 매번 하나씩 줄어 결국 0이 된다는 점으로 설명한다.

PA-1: 최저가 선택을 입력·불변조건·경계값으로 검증한다

상품이 A=12000원, B=9000원, C=9000원 순서로 들어온다고 하자. 명세는 최저가격 상품을 반환하고 동률이면 먼저 나온 상품을 고른다고 정한다.

결과는 B다. 반복 불변조건은 “후보는 지금까지 본 상품 중 명세의 동률규칙을 적용한 최저가 상품”이다.

세 번째 줄에서 9000 < 9000은 거짓이다. 따라서 후보를 바꾸지 않는다. 조건을 <= 즉 ‘작거나 같다’로 바꾸면 C로 교체되어 이 명세에는 틀리지만, 동률에서 마지막 상품을 고르는 다른 명세에는 맞는다. 코드를 짧게 바꿔도 약속한 의미까지 바뀔 수 있다.

빈 목록이면 없음, 한 상품 A만 있으면 A, 마지막에 음수 가격이 있으면 입력 오류다. 오류가 있는데 먼저 찾은 B를 정상 결과로 내보내지 않는다. 세 상품의 가격을 서로 비교하는 횟수는 2회이지만 형식 검사는 3개 모두에 필요하다. 무엇을 세는지 정하지 않은 ‘두 번이면 끝’이라는 말은 전체 작업량이 아니다.

PA-2: 같은 방법으로 배송센터를 고른다

이번에는 목적을 직선도로에서 고객과의 거리가 가장 짧은 열린 센터 선택으로 고정한다. 배송요금·교통량·도로망은 이 교육용 모형에 넣지 않는다. 고객과 센터의 위치는 같은 도로 시작점에서 잰 0~1,000,000의 정수 미터값이고, 목록 길이는 0~10,000이다. 각 항목에는 비어 있지 않은 식별자·위치·열림 여부가 있어야 한다.

거리는 두 위치 중 큰 값에서 작은 값을 빼서 얻는다. 고객이 500m, 센터가 600m라면 600-500=100m이고, 센터가 400m여도 500-400=100m다. 여기서 음수 위치를 오류로 정한 것은 이 모형의 허용 구간 때문이지 실제 좌표가 언제나 양수여야 해서가 아니다.

입력 순서는 A·B·C·D이고, 동률이면 먼저 나온 열린 센터를 고른다.

배송센터 예의 정답은 A다. B는 더 가깝지만 닫혀 있어 선택 대상이 아니고 C는 동률에서 뒤에 나온다. 표의 B 거리 20m는 설명용 계산이다. 실제 절차는 닫힌 센터의 형식을 확인한 뒤 거리 계산을 생략해도 된다.

고객 위치·목록 길이가 허용 범위 밖이면 입력 오류 반환
후보 = 없음
각 센터를 입력순서로 한 번씩 확인:
    식별자·위치·열림 여부의 형식이 틀리면 입력 오류 반환
    닫힌 센터이면 다음 항목으로 이동
    거리 = 두 위치 중 큰 값 - 작은 값
    후보가 없으면 이 센터와 거리를 후보로 저장
    그렇지 않고 거리가 후보 거리보다 작으면 후보 교체
후보가 없으면 없음, 있으면 후보 식별자 반환

후보가 없는 첫 단계와 거리 비교 단계를 분리했다. 비교할 기존 거리가 아직 없는데 숫자 0과 비교하면 모든 센터를 잘못 탈락시킬 수 있다. 또 정상 결과는 마지막 항목까지 확인한 뒤에만 반환하므로, 뒤쪽의 잘못된 항목을 보고도 앞 후보를 정상 결과로 내보내지 않는다.

이제 후보는 ‘지금까지 확인한 열린 센터 중 동률 규칙까지 지킨 최근접 센터’다. 닫힌 센터를 건너뛰어도 이 설명은 유지된다. 형식 검사를 통과한 유한 목록의 다음 항목으로 계속 이동하므로 끝난다. 오류가 있으면 별도의 오류 반환으로 종료한다.

센터 수를 n, 열린 센터 수를 k라고 적자. 두 글자는 각각 개수를 대신 쓰는 이름이다. 정상 목록에서는 n개 항목을 검사하고 k개 센터의 거리를 계산한다. k가 1 이상이면 후보 거리 비교는 k-1회이며 k가 0이면 비교 없이 없음이다. 위 예는 n=4, k=3이므로 거리 계산 3회와 후보 거리 비교 2회다. 전체 센터를 복사하지 않고 현재 후보와 거리만 추가로 기억한다.

한 번 고르는 문제에서는 정렬부터 할 필요가 없다. 순서를 모두 정할 필요 없이 가장 좋은 하나만 남기면 되기 때문이다. 고객별 요청이 반복된다면 이 목록 확인이 요청마다 반복된다는 비용은 따로 세어야 한다.

정확성과 효율을 순서대로 판단한다

틀린 답을 빨리 내는 알고리즘은 쓸 수 없다. 최근접 센터를 묻는데 가장 싼 배송요금만 비교했다면, 프로그램이 정확히 실행되어도 다른 문제를 푼 것이다. 거리 계산과 동률 규칙까지 맞춘 뒤에야 비용을 비교할 수 있다.

예제 시험과 일반적인 정확성 설명도 다르다. A가 나온다는 시험 하나는 그 자료에 대한 결과만 확인한다. 불변조건과 종료 설명은 왜 같은 규칙이 다른 허용 목록에서도 성립하는지 보여준다. 실제 프로그램의 자료형·입출력·동시 변경까지 옳다는 증명은 아니므로 구현 검증은 따로 필요하다.

단순한 선택에서는 입력이 두 배면 항목 검사 수도 두 배가 된다. 이 증가 모양을 표현하는 전문 기호는 시간·공간 복잡도에서 배운다. 아직 기호를 외우지 않아도 현재 절의 횟수와 추가 저장량은 직접 설명할 수 있어야 한다.

실패조건과 방어

빈 입력과 동률 누락은 정상 예제만 통과하고 경계에서 결과를 정하지 못하게 한다. 상품이 하나·없음·같은 가격인 경우의 답부터 써 보고 코드와 대조한다. 없음을 0원 상품이나 입력 오류와 섞지 않는다.

종료 없는 절차는 ‘답을 찾을 때까지’라고 쓰지만 답이 없는 입력을 처리하지 못한다. 다음 항목으로 이동하는지, 남은 항목 수가 줄어드는지 확인한다. 최근접 센터가 없다는 결론도 모든 항목을 본 뒤 얻는 올바른 결과다.

특정 예제에만 맞추면 A·B·C의 답을 외워도 다른 순서에서는 실패할 수 있다. 가격과 입력순서를 바꾸어 보고, 후보 관계가 유지되는 이유를 함께 설명한다.

숨은 제약은 정렬되어 있거나 모든 자료가 메모리에 있다고 말하지 않은 채 기대하는 것이다. 여기서는 유한 목록과 정수 위치, 처리 중 변하지 않는 운영 상태를 가정했다. 실제 거리·상태가 변하면 새 자료를 얻고 다시 선택할 규칙이 필요하다.

효율 지표 혼동은 개발시간·실행시간·응답시간을 한 단어로 부르는 경우다. 이 예의 항목 검사 횟수는 실행시간의 초 단위 측정값이 아니다. 네트워크로 위치를 가져오는 비용과 입력 자체의 저장공간도 후보 변수 몇 개와 구분한다.

자체 10점 문제

문제 명세와 알고리즘의 관계 및 평가기준을 설명하시오.

요구어는 설명이다. 입력·출력·제약·성공조건을 적은 뒤, 그 약속을 지키는 절차와 정확성·종료·비용을 연결한다. 정의 두 개만 나열하지 말고 PA-1의 ‘동률이면 후보 유지’ 한 동작이 왜 필요한지 짧게 근거로 사용한다.

자체 25점 문제

배송센터 선택 문제를 명세하고, 정확성과 효율을 검증하는 알고리즘 설계를 제시하시오.

요구어는 명세, 설계, 검증이다. 문제에 생략된 거리의 뜻과 동률 기준은 가정으로 먼저 적는다. PA-2의 직선도로·정수 위치·운영 상태를 사용할 수 있다. ‘가장 가까운 곳’이라는 목적을 중간에 ‘가장 싼 곳’으로 바꾸지 않는다.

명세에는 정상 결과와 없음/입력 오류를, 설계에는 실제 후보 갱신 절차를, 검증에는 표의 기대값·불변조건·종료·검사 횟수를 넣는다. 아래 답안은 PA-2에서 이미 배운 판단을 시험 표현으로 묶은 자체 예시다.

출처와 적용 경계

상품 가격·직선도로 위치·운영 상태·입력 상한은 원리 설명을 위한 자체 교육 예다. 실제 배송 서비스의 거리함수·배송요금·응답시간 약속을 재현하지 않는다. 이 절의 횟수 계산과 불변조건 설명은 명시한 모형의 검토이며 제품 성능이나 모든 구현의 정확성 인증이 아니다.

문제는 자체 제작이며 공식 기출 원문·공식 채점표가 아니다. 이 기초를 전문 알고리즘 학습에 연결하지만, 여기의 사례만으로 공식 출제범위 전체를 검수했다고 주장하지 않는다.

30초 정리

1. 문제 명세는 입력·출력·제약·성공조건을 고정하고 빈 값·동률·입력 오류의 의미까지 정한다.
2. 알고리즘은 명확한 유한 단계로 허용 입력을 처리하며, 불변조건은 결과가 맞는 이유를, 진행량은 끝나는 이유를 설명한다.
3. 정확성과 종료를 확인한 뒤 무엇을 세는지 정해 시간·공간·구현 비용을 비교한다.

자기교정과 조건 변경

동률이면 마지막 상품을 고르도록 바꾸면? 비교를 <에서 <=로 바꾸면 A·B·C 예의 정답은 C다. 기대값뿐 아니라 불변조건도 ‘동률에서 마지막 상품’으로 고친다. 절차만 바꾸고 B를 정답으로 남기면 문제와 답안이 어긋난다.

고객이 500m에서 450m로 이동하면? 열린 A·C·D의 거리는 150m·50m·450m이므로 정답은 C다. B는 30m여도 닫혀 있어 제외한다. 같은 입력순서라도 비교값이 달라지면 후보가 달라진다.

첫 센터가 닫혀 있으면? 첫 목록 항목을 무조건 후보로 두지 않는다. 없음에서 시작해 첫 열린 센터를 만날 때 저장한다. 전부 닫혀 있으면 끝까지 없음이다.

음수 가격을 할인표시로 허용한다면? 음수가 총가격인지 할인액인지부터 명세한다. 할인액이라면 최솟값이 실제 결제금액과 같지 않을 수 있으므로 비교할 값·성공조건·검증 예를 함께 바꾼다.

가격순 정렬이 이미 보장된다면? 정상 자료에서 최저가는 첫 항목이다. 다만 자료 형식 검사와 정렬 보장 확인까지 생략할 수 있다는 뜻은 아니다. 정렬을 만들고 유지하는 비용을 어디서 부담하는지도 구별한다.