고등학교 정보 · 알고리즘과 프로그래밍 · 2022 개정 교육과정
[12정03-03] 성취기준 해설과 수업·평가 예시
성취기준 원문
[12정03-03] 데이터를 탐색하는 다양한 알고리즘의 특징과 효율을 비교·분석한다.
성취기준 해설
[12정03-02], [12정03-03] 여러 가지 정렬, 탐색 알고리즘을 적용하여 실생활의 간단한 데이터의 정렬, 탐색 문제를 해결할 수 있어야 한다. 정렬, 탐색 알고리즘의 수행 과정을 분석해보고 문제에 따라 알고리즘의 효율성이 다를 수 있음을 설명할 수 있어야 한다.
쉽게 풀어 보면
순차 탐색과 이진 탐색처럼 원하는 데이터를 찾는 여러 방법의 수행 과정을 분석하고 비교 횟수로 효율을 따져 보는 성취기준이에요. 이진 탐색은 빠르지만 데이터가 정렬되어 있어야 한다는 조건이 있어서 문제 상황에 따라 선택이 달라진다는 점을 이해해요.
학습지 문항 예시 예시
어떻게 찾아야 빠를까
- 정렬된 목록 2, 5, 9, 13, 17, 21, 30에서 이진 탐색으로 21을 찾을 때 확인하는 값을 순서대로 쓰세요.
- 정렬된 데이터 1000개에서 이진 탐색으로 찾을 때 최대 비교 횟수가 약 10번인 까닭을 2의 거듭제곱으로 설명하세요.
- 정렬되지 않은 데이터에 이진 탐색을 적용하면 어떤 문제가 생기는지 예를 들어 설명해 보세요.
- 한 번만 검색할 데이터와 수천 번 반복 검색할 데이터에서 정렬 후 이진 탐색과 순차 탐색 중 무엇이 유리한지 비교해 보세요.
수업 흐름 예시 예시
- 도입: 1부터 100 사이의 숫자를 맞히는 업다운 게임으로 가장 적은 횟수에 맞히는 전략을 찾아요.
- 전개 1: 번호가 적힌 뒤집힌 카드에서 순차 탐색과 이진 탐색을 각각 수행하고 확인한 카드 수를 기록해요.
- 전개 2: 데이터 크기를 10, 100, 1000으로 늘릴 때 두 탐색의 최악 비교 횟수가 어떻게 변하는지 표와 그래프로 분석해요.
- 정리: 전화번호부, 쇼핑몰 상품 검색 같은 실생활 사례에 어떤 탐색 방법이 알맞은지 근거를 들어 정리해요.
서술형 평가 문항과 채점 기준 예시
학생 1024명의 학번 목록에서 특정 학생을 찾으려고 한다. 순차 탐색과 이진 탐색의 수행 과정을 비교하여 각 방법의 최악의 비교 횟수를 제시하고, 이진 탐색을 사용하기 위해 필요한 조건과 그 조건을 갖추는 데 드는 비용까지 고려하여 서술하시오.
| 수준 | 채점 기준 |
|---|---|
| 상 | 순차 탐색은 최악 1024번, 이진 탐색은 약 11번 이내임을 반씩 줄이는 과정과 함께 설명하고, 정렬이 필요하며 반복 검색이 많을 때 정렬 비용을 감수할 가치가 있음을 서술함 |
| 중 | 두 탐색의 효율 차이와 정렬 조건은 제시했으나 비교 횟수 계산이나 정렬 비용 고려가 부족함 |
| 하 | 이진 탐색이 빠르다고만 쓰고 수행 과정이나 정렬 조건을 설명하지 못함 |
세특 기재 예시 예시
탐색 알고리즘 분석 활동에서 업다운 게임 전략이 이진 탐색과 같은 원리임을 찾아내고, 탐색 범위가 매번 절반으로 줄어드는 과정을 표로 정리함. 데이터 수가 두 배가 될 때 이진 탐색의 비교 횟수는 한 번만 늘어남을 실험 결과로 확인함. 정렬되지 않은 데이터를 한 번만 찾을 때는 순차 탐색이 합리적일 수 있다는 판단 근거를 제시함.
이 예시는 185자, 나이스 기준 447Byte예요. 과목별 세특은 1,500Byte(500자)까지 써요. 내 문장은 나이스 글자수·바이트 계산기로 세어 볼 수 있어요.
세특에는 학생이 실제로 한 활동과 교사가 관찰한 내용만 써요. 대회명·기관명처럼 쓰면 안 되는 내용은 생기부 기재 금지 사전에서 확인할 수 있어요.
학생들이 자주 헷갈리는 점
이진 탐색이 언제나 순차 탐색보다 좋다고 생각하는 학생이 많아요. 정렬되지 않은 데이터를 한 번만 찾는다면 정렬하는 시간이 더 들기 때문에 순차 탐색이 나을 수 있다는 점을 전체 소요 시간으로 비교하게 해 주세요.
이 영역의 적용 시 고려 사항 (고시 원문)
- 제시된 문제 상황을 컴퓨팅 시스템으로 해결할 수 있도록 문제 분해, 모델링, 알고리즘 설계 등의 추상화 과정 및 프로그램 작성, 실행 결과 평가, 오류 수정 등의 자동화 과정이 유기적으로 연결되도록 나선형으로 교수·학습을 제시하고 과정 전반을 평가하도록 한다.
- 정렬, 탐색 알고리즘 학습 과정에서 정렬, 탐색의 효율적인 부분을 효과적으로 이해할 수 있도록 실제 대규모 데이터를 정렬하고 탐색하는 과정을 교수·학습 과정에 충분히 포함하도록 한다.
- 다차원 데이터 구조 학습 과정에서 프로그래밍 언어에 따라 2차원 혹은 그 이상의 배열이나 리스트를 활용하도록 하며, 다차원 데이터를 활용하는 이유를 이해하기 쉽도록 실제로 사용되는 데이터의 예시를 충분히 제공하도록 한다.
- 프로그래밍 학습 시 최소 성취수준을 보장하기 위하여 프로그래밍 관련 학습 개념을 우선 이해할 수 있도록 미리 제작된 코드를 제공하거나, 프로그래밍 언어에서 활용할 수 있는 여러 라이브러리를 활용하는 방안을 구상하도록 한다. 기본적인 프로그래밍 개념이 부족한 학생을 위해 수준에 맞게 스스로 학습을 진행할 수 있는 추가적인 교육 내용을 제공하는 것도 고려하도록 한다.
같은 영역의 다른 성취기준
왓퀴즈는 이런 AI예요
왓퀴즈는 한국 학교의 수업과 기록 업무에 맞춘 교사용 AI예요. 이 사전과 같은 2022 개정 교육과정 성취기준 데이터로 학습지, 수업 PPT, 평가계획서 초안을 만들고, 2026학년도 학교생활기록부 기재요령 원문을 바탕으로 세특 초안을 쓰고 기재 금지 표현을 검사해요.