‘우리글’이라는 검색어를 … 18글자의 대상 문자열에서 검색한다고 가정해 보자. 가장 간단히 떠올릴 수 있는 방법은 ‘우리글’이 3글자이므로 대상 문자열을 3글자씩 잘라 1글자씩 비교하는 것이다. … 하나의 비교 대상을 확인하기 위해서는 3글자를 각각 비교해야 하므로 총 16×3번 비교를 하게 될 것이다.
검색어와 비교 대상을 … 3글자씩 한 번에 비교할 수 있다면 그만큼 비교 횟수가 줄어들게 되어 검색 시간이 줄어들 것이다. 이를 위해 각각의 문자열에 특정 값을 생성하는 함수를 설정할 수 있다. 이런 함수를 해시 함수라고 하고, 어떤 문자열에 대해 해시 함수가 생성한 값을 해시값이라고 한다. 만일 해시 함수가 입력 가능한 문자열에 대해 모두 다른 해시값을 생성한다면 검색어의 해시값과 비교 대상의 해시값을 비교하여 두 문자열이 일치함을 단번에 판단할 수 있다. … 각 비교 대상에서 문자열 비교는 1번의 해시값 비교로 줄어들기 때문에 전체 비교 횟수는 감소하게 된다. 물론 해시값을 생성하는 해시 함수의 연산이 추가되지만 추가되는 연산 시간이 각 글자 단위의 비교에 필요한 연산 시간보다 짧다면 전체적인 검색 시간은 단축될 수 있다.
11. [A]를 이해한 내용으로 적절한 것은?
① 검색어의 길이가 짧아진다면 비교 대상의 개수가 줄어들어 해시값 비교 횟수가 증가할 수 있겠군. ② 대상 문자열에 반복되는 글자가 많다면 해시값이 작아져서 해시 함수의 연산 시간이 단축될 수 있겠군. ③ 검색어보다 긴 대상 문자열의 개수가 늘어난다면 비교 대상이 늘어나 해시값 비교 횟수가 증가할 수 있겠군. ④ 대상 문자열이 1개일 경우 검색어의 길이가 짧아진다면 비교 대상의 길이가 줄어들어 해시값 비교 횟수가 감소할 수 있겠군. ⑤ 대상 문자열이 2개일 경우 검색어의 길이가 길어진다면 비교 대상의 개수가 늘어나 해시 함수의 연산 시간이 증가할 수 있겠군.
- 2022학년도 3월 교육청 전국연합학력평가-
각각의 문자열에 특정 값을 생성하는 함수를 설정할 … 함수가 생성한 값
옛날이야기에 나오는 ‘요술항아리’는 물건을 넣으면 하나 더 만들어낸다. 투입(입력)하면 어떤 작용으로 산출(출력)이 생기니 그 항아리는 함수다. 수학에서는 항아리 속 작용을 함수식이라 한다. 결국 요술항아리는 ‘입력(값)×2=출력(값)’이라는 함수식으로 나타낼 수 있다. 지문의 ‘해시 함수’는 ‘문자열에 특정 값을 생성하는 함수’, 즉 문자열을 입력하면 ‘해시값’을 출력하므로 요술항아리와 같다.
이런 함수가 왜 필요할까? ‘문제(과제) 발생의 원인-문제 상황(과제)-해결법-해결 결과’로 글을 나눠 읽으면 좋을 때가 있다고 했다. 지문에 의하면 ‘비교 횟수’라는 과제가 있다. 이것의 발생 원인은 ‘검색어의 글자 수’와 ‘비교 대상의 수’다. 그 해결법은 ‘해시값의 비교’다. 그 결과는 ‘검색 시간의 감소’다. ‘a=b×c’의 경우 a는 b와 c에 비례함을 보여준다. 그런데 비교 횟수는 검색어의 글자 수와 비교 대상의 수에 비례하므로, 이 둘을 줄이면 비교 횟수도 줄게 된다. 검색어 글자와 비교 대상 글자를 각각 그룹으로 묶어 하나의 값으로 만들면 그 수를 줄일 수 있다. 지문에서는 이를 해시 함수라 하고 있다. 이는 학생들의 번호를 일일이 불러 모으는 것이 아니라, 몇몇을 묶어 1, 2, 3,…n모둠 등으로 부르면 부르는 횟수가 줄어드는 것과 같은 방식이다.
① … 짧아진다면 … 줄어들어 … 증가할 … ② … 많다면 … 작아져서 … 단축될… ③ … 늘어난다면 … 늘어나 … 증가할 … ④ … 짧아진다면 … 줄어들어 … 감소할 … ⑤ … 길어진다면 … 늘어나 … 증가할
국어에서의 함수 문제는 구체적 계산 결과를 알아내는 것이 아니고, 어떤 것이 독립 변수이고 어떤 것이 종속 변수인지를 알고 그것들 사이에 비례 또는 반비례 관계만 파악하면 된다. 이 문제의 선택지들은 ‘A면 B’라는 문장 구조로 되어 있는데, 이는 독립변수 A와 종속변수 B의 관계가 비례 또는 반비례임을 나타내는 것이다.
①은 ‘검색어의 길이’는 ‘비교 대상의 개수’와 비례 관계고, ‘해시값 비교 횟수’와는 반비례 관계임을 말한다. 지문에 따르면 검색어의 글자 수로 대상 문자열을 잘라 비교 대상을 만들므로, 검색어의 길이와 비교 대상의 개수는 ①과 달리 반비례 관계다.
②는 ‘반복되는 글자’의 수는 ‘해시값’, ‘해시 함수의 연산 시간’과 반비례임을 말한다. 지문에는 해시 함수가 있다고만 했지 그 내용이 무엇인지는 설명하고 있지 않아 반복되는 글자의 수와 해시값이 어떤 관계인지 알 수 없다.
③은 ‘대상 문자열의 개수’가 ‘비교 대상’의 개수, ‘해시값 비교 횟수’와 비례 관계임을 말한다. 이는 지문 내용과 일치한다.
④는 ‘검색어의 길이’가 ‘비교 대상의 길이’, ‘해시값 비교 횟수’와 비례 관계임을 말하고 있다. 지문에 의하면 검색어의 길이와 비교 대상의 길이는 비례 관계지만, 해시값 비교 횟수는 반비례 관계다.
⑤는 ‘검색어의 길이’가 ‘비교 대상의 개수’와 ‘해시 함수의 연산 시간’과 비례 관계임을 말한다. 지문에 의하면 검색어의 길이와 비교 대상의 개수는 반비례 관계다. 그리고 해시 함수의 연산 시간은 지문에서 알 수가 없다. ‘해시값을 생성하는 해시 함수의 연산’이 있다는 것만 언급됐고, 그 방법은 설명되지 않았기 때문이다.
④ 대상 문자열이 1개일 경우 … ⑤ 대상 문자열이 2개일 경우
‘… 경우’는 흔히 판단 조건에 해당한다. 예컨대 ‘교사의 경우’와 ‘여교사의 경우’는 판단할 때 조건에 차이가 있다. 철수샘은 ‘교사의 경우’에 포함되지만 ‘여교사의 경우’에는 포함되지 않기 때문에 판단에 포함할 경우와 포함하지 않을 경우가 생긴다.
그런데 이 문제의 경우 조건이 판단에 전혀 영향을 미치지 않는다. 쉽게 말해 ‘대상 문자열이 1개일 경우’와 ‘대상 문자열이 2개일 경우’가 없다고 생각하고 문제를 풀어도 결과는 같다. 선택지가 학생에게 조금씩 다르게 보여야 한다. 그래서 ‘대상 문자열이 1개일 경우’와 ‘대상 문자열이 2개일 경우’ 같은 조건을 주지 않았나 생각된다.
