2 문제해결절차 학습목표 알고리즘의의미를이해하고, 문제해결절차를알고리즘으로표현할수있다. 알고리즘을의사코드나순서도로작성할수있다. 자료를정렬하고탐색하는다양한방법을설명할수있다. 공주님을구하라! 메인보드나라롬공주와이웃나라램왕자의결혼식에믿을수없는일이일어났다. 온국민의축복속에결혼식이진행되던중무시무시한용이나타나공주를납치해간것이다. 범인은왕국북쪽의디스크산에살고있는바이러스용이다. 정의롭고용맹스러운램왕자는공주를구하기위해떠나기로결심한다. 함께싸울용사가필요하다! 생각하기 롬공주를구하려면어떤용사를선택해야할까? 220 Ⅳ. 문제해결방법과절차 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 220 2012-07-19 오후 7:39:37
함께공주를구할용사고르기! 램왕자가칼솜씨가뛰어나다면힘세고용감한전사보다는치료마법을가진사제나, 많은정보를가지고있는동료가함께가는것이좋다. 램왕자가용에대한정보는가지고있으나싸움을잘하지못한다면, 강력한마법사또는파괴력이있는힘센전사와함께가는것이좋다. 램왕자는자신의능력을정확히파악한후자신의단점을보완하고함께협력하여용을물리칠수있는동료를선택해야한다. 이것은공주를구출하는문제를해결하기위해꼭필요한절차이다. Ⅳ-2 문제해결절차 221 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 221 2012-07-19 오후 7:39:39
2-1 알고리즘의이해 주요학습내용 알고리즘 / 알고리즘의특성 / 알고리즘의표현 학습활동 생활속알고리즘만들기 / 라면끓이기알고리즘만들기 / 등교시간알고리즘만들기 알고리즘의유래알고리즘이라는용어는아랍의수학자알콰리즈미 (Al - Khwarizmi) 의이름에서유래되었다. 알고리즘알고리즘은주어진문제를해결하기위해명확히정의된절차나방법들의모임이다. 컴퓨터프로그램을작성할때의알고리즘은실행명령어들의순서를의미한다. 그러나알고리즘의개념이컴퓨터를이용한정보처리에서만쓰이는것은아니다. 집을짓는방법도알고리즘이될수있고, 책을쓰는방법도알고리즘이될수있다. 간단한예를통해일상생활에서알고리즘이이용되는사례를알아보자. 생활속알고리즘이용사례 주말오후에친구와만나기로한약속장소에가기위해집을나섰다. 약속시간에맞춰약속장소에도착하기위한방법은? 약속시간에늦었다면택시를타는것이좋겠지만, 다른교통수단과비교하여비용이많이소요되므로현재금전적인여유가있어야한다. 시간을지키기에는지하철을이용하는것이가장좋지만, 주변에가까운지하철역이있어야한다. 버스를이용하는것도좋지만, 만약교통이혼잡한출퇴근시간이라면약속시간에맞춰도착하기어려울것이다. 위의예는우리가일상생활에서자주접할수있는상황이다. 그리고일반 꼭알아두기! 문제를해결하기위해명확히정의된절차나방법을 ( 이 ) 라고한다. 적으로이러한상황에접했을때비용이나시간, 교통여건등여러가지요인을고려하여가장최적이라고생각되는교통수단을선택하고행동으로옮기게된다. 이처럼우리는일상생활속에서크고작은문제의해결을위해알고리즘을이용하고있다. 222 Ⅳ. 문제해결방법과절차 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 222 2012-07-19 오후 7:39:40
알고리즘의특성우리가일상생활에서어떤문제를해결할때즉흥적으로처리하는경우가있는데, 이러한문제해결과정은알고리즘이라고할수없다. 알고리즘의절차와과정이확실하지않거나잘못된점이있다면, 문제를해결하지못하거나문제를해결하더라도많은시간과자원을낭비할수있다. 따라서문제를효과적으로해결하기위해서는알고리즘의특성을정확히이해하고활용해야한다. 성공적으로문제를해결하기위해갖추어야할알고리즘의일반적인특성은다음과같다. 명확성이만족되지못한문제 Q 사과, 배를 2개가져가기 A 사과 1개 + 배 1개? 사과 2개 + 배 2개? 유한성이만족되지못한문제 Q 만원을 3명이똑같이나누기 A 3,333.3333 원 수행가능성이만족되지못한문제 Q 5를 0으로나누어 X에저장하라. A 컴퓨터에서는실수를 0으로나누는연산은처리되지않는다. 알고리즘의일반적인특성 입력 : 알고리즘은문제해결을위해특정한형태의입력이필요하다. 출력 : 알고리즘은문제해결절차에따른하나이상의결과를출력해야한다. 명확성 : 알고리즘각단계의명령은모호하지않고명확해야한다. 유한성 : 해당알고리즘을명령대로수행하면정해진단계를거쳐서유한한시간안에종료되어야한다. 수행가능성 : 알고리즘은각단계가반드시실행가능한것이어야한다. 그림Ⅳ-6은문제에대한해결과정이다른경우와해결방법이다른경우를비교하여알고리즘선택의중요성을나타낸것이다. 같은재료를썼는데왜내가만든음식은맛이없을까? 요리과정이다르면맛도달라지지! 얼음판위에서는스케이트가제일이지! 수영장에서는엄청빨랐는데 같이가! 과정에대한알고리즘이다른경우 방법에대한알고리즘이다른경우 그림 Ⅳ 6 알고리즘선택의중요성 Ⅳ-2 문제해결절차 223 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 223 2012-07-19 오후 7:39:41
한 걸음 더 / 더 좋은 알고리즘이란? 어떠한 작업을 수행하는 데에는 여러 가지 방법이 있다. 같은 일이더라도 그 작업을 수행하는 사람에 따라서 문 제에 접근하는 방법이 다르고 처리하는 방법도 다르기 때문이다. 알고리즘도 마찬가지이다. 우리가 알고리즘을 공부하는 이유는 주어진 상황에서 보다 효율적이고 합리적인 방법 을 찾기 위해서이다. 더 좋은 알고리즘을 찾으려면 여러 가지 알고리즘 중에 어떠한 것이 더 나은지 증명할 수 있 어야 한다. 이러한 과정을 알고리즘 분석이라고 한다. 그림Ⅳ-7은 우리가 생활 속에서 더 좋은 알고리즘을 선택할 때 고려해야 하는 일반적인 기준을 나타낸 것이다. 1 알고리즘을 수행하는 데 시간이 얼마나 걸렸는가? 서울 서울 2 알고리즘이 복잡하지 않고 간결한가? 같은 물건들이라도 부산 잘 정리하면 낭비되는 부산 공간이 그만큼 줄지 3 알고리즘이 문제없이 예상한 대로 잘 동작하고, 그 결과가 정확한가? 딸기 딸기 4 5 알고리즘의 표현이 단순하고 이해하기가 쉬운가? 알고리즘을 수행하는 데 얼마나 적은 비용으로 해결하였는가? 그림Ⅳ 7 더 좋은 알고리즘을 선택하기 위한 일반적인 기준 224 Ⅳ. 문제 해결 방법과 절차 정보_4-2 문제 해결 절차(220-247)_수정본.indd 224 2012-07-19 오후 7:39:46
활동 08 생활속알고리즘만들기 다음은약속장소에시간에맞추어도착하기위한알고리즘이다. 알고리즘이갖추어야할요건을모두갖추고있는지알아보자. ➊ 집을나선다. ➋ 버스정류장까지걸어간다. ➌ 버스정류장에도착한후 10분이내에 35번버스가오면타고 ❺로간다. ❹ 버스정류장에도착한후 10분이지나면택시를탄다. ❺ 인천지하철 1호선부평역에내린다. ❻ 인천지하철 1호선국제업무지구역방향으로가는열차를탄다. ❼ 인천지하철 1호선문학경기장역에서내린다. ➑ 약속시간전이면 ➓으로간다. ➒ 약속장소까지뛰어간다. ➓ 약속장소까지걸어간다. 입력출력명확성유한성수행가능성 심장마비가발생했을때아무런조치를취하지않으면 4~5분이내에뇌손상이일어나기때문에초기 5분의대응이매우중요하다. 심장마비직후응급처치를실시하면생존율이 3배이상으로증가한다. 응급처치방법을조사하여그속에들어있는알고리즘을설명해보자. Ⅳ-2 문제해결절차 225 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 225 2012-07-19 오후 7:39:46
프로그래밍언어프로그램을작성하기위해사용되는명령어알고리즘표현의이점 문제해결에대한생각들을정리할수있음. 잘못된부분을찾기쉬움. 알고리즘을다른사람과공유하기에편리함. 알고리즘의표현알고리즘을표현하는방법은여러가지가있는데, 이러한방법들은알고리즘을보다명확하고이해하기쉽도록표현하는것이목적이다. 일반적으로많이사용되는알고리즘표현방법에는자연어, 의사코드, 순서도가있다. 자연어자연어는우리가일상생활에서일반적으로사용하는언어로, 별다른지식없이도사용할수있다. 또한, 형식에구애받지않고표현할수있기때문에누구나쉽게사용하고이해할수있다. 하지만내용이길어지면한눈에알아보기어렵고, 경우에따라서는하나의표현이여러가지의미로해석될수있는단점이있다. 따라서자연어를이용하여알고리즘을표현할경우에는의미가명확하게전달될수있도록표현해야한다. Q A 알고리즘표현방법은어떻게선택해야할까? 알고리즘의특성에따라적합한알고리즘표현방법을사용하여야한다. 의사코드의사코드는알고리즘의내용을자연어보다간단하면서도자세하게기술해놓은것으로, 슈도코드라고도한다. 의사코드는자연어와프로그래밍언어의중간단계의표현으로, 일정한형식이정해져있지는않다. 또한, 컴퓨터에서실행할수는없지만비교적자세하고읽기쉬워프로그램설계전에많이사용한다. 자연어 의사코드 A에 1을저장한다. A와 B를더한결과를 S에저장한다. A 1 S A + B A가 B보다크면 A에 1을저장한다. 그렇지않으면 B에 2를저장한다. A가 5보다작거나같을동안에는 S와 A 값을더하여 S에저장한다. if (A B) then A 1 else B 2 while (A 5) do S S + A A값을출력한다. 정보 라는문자를출력한다. print A printf 정보 그림 Ⅳ 8 자연어와의사코드표현의예 226 Ⅳ. 문제해결방법과절차 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 226 2012-07-19 오후 7:39:47
순서도순서도는미리약속된기호를이용하여알고리즘을표현한그림으로, 문제해결과정의단계와흐름을쉽고명확하게표현할수있어컴퓨터프로그램을설계할때많이사용한다. 순서도는내용이복잡하거나프로그램의크기가클경우에는모든내용을다표현하는데어려움이있다. 표Ⅳ 1 순서도에사용되는기호 순서도작성의기본원칙 표준기호를사용한다. 순서도의흐름을위쪽에서아래쪽으로한다. 흐름이서로교차하지않도록작성한다. 설명은기호안에간단하게삽입한다. 이름기호및그림설명 단말순서도의시작과끝을의미한다. 처리계산등다양한자료처리기능을표시한다. 입출력자료의입력과출력을나타낸다. 판단조건을나타내며, 조건에따라 예, 아니오 로이동한다. 자료의흐름각기호들을연결해주며, 순서도의흐름을나타낸다. 한걸음더 / 횡단보도건너기알고리즘의예 시작 신호등앞에선다 아니오 자연어 ➊ 신호등앞에선다. ➋ 녹색신호인지확인한다. ➌ 녹색신호가아니면기다린다. ➍ 녹색신호면건넌다. 순서도 색신호인가? 예 건 다 의사코드 신호등앞에선다. if( 신호 = 녹색 ) then( 건넌다 ) else 신호등앞에선다. 끝 Ⅳ-2 문제해결절차 227 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 227 2012-07-19 오후 7:39:48
활동 09 라면끓이기알고리즘만들기 다음그림은라면끓이는과정을나타낸것이다. 이그림과의사코드를보고순서도로표현해보자. 라면 1 개 마른새우 5 마리 마른오징어 고춧가루 1Ts 맛있는라면을끓여보자! 양파 ⅓ 개대파고추 1 개 1 재료를준비한다. 2 물을붓고양파, 마른오징어, 마른새우, 파등을넣고끓인다. 면을넣고끓인다. 3 4 라면스프는 ~ 정도만넣는다. 면발을물에서건졌다넣었다를 3번이상반복한다. 맛있는라면완성! 의사코드 순서도 ➊ 재료준비하기라면 1개, 마른오징어, 마른새우 5마리, 고춧가루 1Ts, 양파개, 대파, 고추 1개 ➋ 재료를냄비에넣기양파, 마른오징어, 마른새우, 파넣기냄비 ( 물 ) 시작 ➌ 면을넣고끓이기면, 라면스프 ~ 개 재료준비 ➍ 면발입수반복하기 if( 입수횟수 3) then 라면완성 228 Ⅳ. 문제해결방법과절차 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 228 2012-07-19 오후 7:39:49
활동 10 등교시간알고리즘만들기 다음그림은민규의아침등교시간을순서도로나타낸것이다. 자연어와의사코드로표현해보자. 시작 아침이되었습니다 일어난다 아니요 몸이아픕니까? 아니요 씻었습니까? 예심하게아픕니까? 아니요 예 예 부모님께말씀드린다 아니요 끝 반성한다 씻는다 아니요 배가고픕니까? 예 아침을먹는다 지각입니까? 예 예 지각입니까? 아니요 옷을갈아입었습니까? 예 학교에도착 아니요 옷을갈아입는다 자연어 의사코드 Ⅳ-2 문제해결절차 229 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 229 2012-07-19 오후 7:39:50
2-2 알고리즘설계와작성 주요학습내용 알고리즘의설계 / 알고리즘의기본구조 학습활동 알고리즘기본구조이해하기 / 알고리즘활용하기 알고리즘의설계알고리즘설계란, 구체적인문제해결방안을단계별로만들어가는것으로, 문제를해결하기위한알고리즘을생각하여논리적이고명확하게표현하는과정을말한다. 알고리즘의설계가잘못되면문제를해결하지못하거나문제를해결하더라도많은시간과자원을낭비할수있으므로, 알고리즘의설계는아주중요하다. 알고리즘의기본구조 알고리즘을설계할때에는전체적인흐름을쉽게파악할수있는순서도를많이사용한다. 알고리즘설계를위한기본구조로는순차구조, 선택구조, 반복구조가있다. 1 순차구조 : 시간적순서에따라차례대로수행되는구조이다. 2 선택구조 : 주어진조건에따라실행내용이다르게진행되는구조이다. 3 반복구조 : 주어진조건에따라특정부분을반복하여실행하는구조이다. 처리 1 예 조건 아니오 조건 아니오 처리 2 처리 1 처리 2 예 처리 2 꼭알아두기! 알고리즘의기본구조중주어진조건에따라실행내용이다르게진행되는구조를 구조라한다. 처리 1 처리 3 순차구조 선택구조 반복구조 그림Ⅳ 9 알고리즘설계를위한기본구조 230 Ⅳ. 문제해결방법과절차 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 230 2012-07-19 오후 7:39:50
알고리즘설계를위한기본구조들은실제설계과정에서는따로따로적용되기보다 3가지기본구조가문제상황에알맞게적절하게융합되어활용되고있다. 수학여행시작 Q A 알고리즘설계가중요한이유는무엇일까? 알고리즘설계방법을이해하는것은문제해결과정을이해하는것이므로, 문제해결능력을키우는데매우중요하다. 예 필요한준비물을가방에다 는가? 아니오 준비물을찾는다. 가방에 는다. 집을나선다. 예 약속시간에늦었는가? 아니오 선택구조 순차구조 택시를탄다. 버스를탄다. 역에도착한다. 약속장소로간다. 예 모두모였는가? 아니오 반복구조 인원을점검한다. 기차를타고간다. 끝 그림 Ⅳ 10 알고리즘의기본구조가융합된순서도의예 Ⅳ-2 문제해결절차 231 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 231 2012-07-19 오후 7:39:50
활동 11 알고리즘기본구조이해하기 다음악보의진행순서를적어보고, 순서도로나타내보자. 1. 2. 구분 진행순서 A B C D A B C D C D A B C A B D 순서도 232 Ⅳ. 문제해결방법과절차 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 232 2012-07-19 오후 7:39:50
활동 12 알고리즘활용하기 다음은키와몸무게를이용하여비만도를구하는일반적인방법이다. 필요한정보 : 키, 몸무게 비만도 한국인비만기준 몸무게 (kg) 신체질량지수 (BMI) = { 키 (m)} 2 분류 신체질량지수 비만관련질환의위험도 저체중 <18.5 낮음 정상체중 18.5~22.9 보통 과체중 23.0 높음 ( 자료 : 한국비만협회 ) 신체질량지수를이용해비만정보를계산하는알고리즘을설계하여순서도로나타내보자. Ⅳ-2 문제해결절차 233 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 233 2012-07-19 오후 7:39:50
2-3 정렬의이해 주요학습내용 정렬 / 정렬알고리즘의종류와특징 학습활동 내림차순정렬하기 / 오름차순정렬하기 그림 Ⅳ 11 생활속정렬의예 정렬정렬은흩어져있는자료들을일정한기준으로다시나열하는것을말한다. 일상생활속에서정렬되어있는것을쉽게찾아볼수있는데, 번호순으로정렬된출석부, 제목순으로정렬된도서관의책, 작성일자순으로정렬된컴퓨터의자료파일, 선착순으로정렬된버스정류장의대기줄등이그예이다. 이와같이특정기준에의해자료를순서대로나열하는것은모두정렬에속한다. 정렬에는값이작은것에서부터큰것으로정렬하는오름차순정렬과큰것에서부터작은것으로정렬하는내림차순정렬이있다. 오름차순정렬 내림차순정렬 그림 Ⅳ 12 키에따른오름차순정렬과내림차순정렬의예 234 Ⅳ. 문제해결방법과절차 정보 _4-2 문제해결절차 (220-247)_ 전시본.indd 234 2012-08-16 오전 10:18:13
정렬알고리즘의종류와특징 자료의양이나현재의정렬상태에따라다양한정렬방법이있다. 다음 5 개의숫자가적힌카드를오름차순으로정렬하는다양한방법을알아보자. 22 37 15 17 11 선택정렬 선택정렬은전체자료들중에서해당위치에맞는자료를선택하여자리 를바꾸는방식으로정렬한다. 정렬되지않은자료중에서가장작은수 22 37 15 17 11 정렬되지않은자료 정렬된자료 자리바꿈 11 37 15 17 22 11 15 37 17 22 11 15 17 37 22 선택정렬알고리즘 ( 오름차순 ) ➊ 모든자료중에서가장작은자료를정렬되지않은자료의첫번째자료와자리를바꾼다. ➋ 첫번째자료는정렬된자료이므로, 나머지중에서가장작은자료를두번째자료와자리를바꾼다. 두번째자리까지정렬된자료가된다. ➌ 이과정을자료가 1개남을때까지반복하면가장작은자료부터정렬이이루어지게된다. 11 15 17 22 37 11 15 17 22 37 선택정렬의특징 자료의양이적을때효과적인방법이다. 자료의분포에크게영향을받지않는다. 자료의수가커지면실행하는시간이많이걸린다. 그림 Ⅳ 13 선택정렬의예 Ⅳ-2 문제해결절차 235 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 235 2012-07-19 오후 7:39:53
버블정렬 버블정렬은인접한자료들의값을비교하여자리를바꾸는방식으로정 렬한다. 비교 22 37 15 17 11 ➊ 22 37 15 17 11 자리바꿈 22 15 37 17 11 ➋ 22 15 17 37 11 ➌ 버블정렬알고리즘 ( 오름차순 ) ➊ 첫번째자료와두번째자료를비교하여첫번째자료가큰경우자리를바꾼다. ➋ 두번째자료와세번째자료를비교하여두번째자료가큰경우자리를바꾼다. ➌ 마지막자료에가장큰값이올때까지앞의과정을반복한다. ➍ 마지막이전자료에두번째큰값이올때까지 ➊~➌의과정을반복한다. ➎ 모든자료가정렬될때까지위의과정을반복한다. 22 15 17 11 37 22 15 17 11 37 15 22 17 11 37 15 17 22 11 37 정렬된자료 ➍ 버블정렬의특징 정렬방법이단순하여이해하기쉽다. 자료가정렬되어있어도항상비교횟수는같다. 15 17 11 22 37 비교할원소가 1 장이될때까지반복 11 15 17 22 37 ➎ 236 Ⅳ. 문제해결방법과절차 그림 Ⅳ 14 버블정렬의예 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 236 2012-07-19 오후 7:39:54
삽입정렬 삽입정렬은정렬되지않은자료를이미정렬되어있는자료들과비교하 여맞는위치에삽입하는방식이다. 정렬된자료 22 37 15 17 11 정렬되지않은자료 ➊ 22<37 이므로 22 뒤에 37 배치 삽입 22 37 15 17 11 15<37 이므로다시앞자리원소 22와비교 15<22 이므로 22 앞에 15 삽입삽입 ➋ 15 22 37 17 11 17<37 이므로다시앞자리원소 22와비교 17<22 이므로다시앞자리원소 15와비교 17>15 이므로원소 15와 22 사이에 17 삽입삽입 15 17 22 37 11 ➌ 삽입정렬알고리즘 ( 오름차순 ) ➊ 두번째자료를첫번째자료와비교하여두번째자료가작은경우자리를바꾼다. ➋ 세번째자료를왼쪽의정렬된자료들과비교하여맞는위치에삽입한다. ➌ 네번째자료를왼쪽의정렬된자료들과비교하여맞는위치에삽입한다. ➍ 마지막자료가정렬될때까지이과정을반복한다. 11<37 이므로다시앞자리원소 22와비교 11<22 이므로다시앞자리원소 17과비교 11<17 이므로다시앞자리원소 15와비교 11<15 이므로원소 15 앞에 11 삽입 11 15 17 22 37 ➍ 삽입정렬의특징 자료들이이미정렬되어있는경우비교횟수가줄어실행속도가빠르다. 내림차순으로정렬된자료를다시오름차순으로정렬하는경우실행속도가가장느리다. 그림 Ⅳ 15 삽입정렬의예 Ⅳ-2 문제해결절차 237 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 237 2012-07-19 오후 7:39:54
활동 13 내림차순정렬하기 아래그림은우리반친구들의생일을나타낸것이다. 친구들의생일을선택정렬을이용하여내림차순 으로정렬해보자. 10 월 1 일 (10. 1) 4 월 6 일 (4. 6) 9 월 20 일 (9. 20) 12 월 24 일 (12. 24) 정렬되지않은자료 10. 1 4. 6 9. 20 12. 24 정렬된자료 12. 24 10. 1 9. 20 4. 6 238 Ⅳ. 문제해결방법과절차 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 238 2012-07-19 오후 7:39:57
활동 14 오름차순정렬하기 우리반에전학생이한명왔다. 친구들의생일을삽입정렬을이용하여오름차순으로정렬해보자. 10 월 1 일 (10. 1) 4 월 6 일 (4. 6) 9 월 20 일 (9. 20) 12 월 24 일 (12. 24) 9 월 30 일 (9. 30) 정렬되지않은자료 10. 1 4. 6 9. 20 12. 24 9. 30 정렬된자료 4. 6 9. 20 9. 30 10. 1 12. 24 Ⅳ-2 문제해결절차 239 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 239 2012-07-19 오후 7:40:00
2-4 탐색의이해 주요학습내용 탐색 / 탐색알고리즘의종류와특징 학습활동 순차탐색과이진탐색활용하기 / 순차탐색과이진탐색비교하기 탐색탐색은많은자료들중에서원하는특정자료를찾는일을말한다. 입을옷을고르는일, 편지를보내기위해우편번호를검색하는일, 책장에서읽고자하는책을찾는일등우리는일상생활에서다양한탐색활동을하고있다. 그림 Ⅳ 16 생활속탐색의예 특히, 오늘날과같은정보사회에서의탐색은더욱중요한의미를갖는다. 방대한양의정보들중에서필요한정보를찾아내고선택하는것은정보사회를살아가는데필수적으로갖추어야할능력이기때문이다. 탐색의과정은 무엇을탐색하느나? 에따라여러가지가있을수있으나, 일반적인탐색과정은그림Ⅳ-17과같다. 탐색기준정하기탐색대상비교하기자료찾기 무엇을기준으로탐색할것인지를결정하는과정으로, 사람과관련된자료를탐색할때에는이름, 생일, 소속등이될수있다. 탐색대상을기준에따라비교해보는과정으로, 이름을기준으로한다면대상의이름과탐색자료의이름이일치하는지를비교한다. 원하는자료를찾아내는과정으로, 탐색하는자료와일치하는이름을찾아냄으로써탐색이마무리된다. 그림 Ⅳ 17 탐색의기본과정 240 Ⅳ. 문제해결방법과절차 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 240 2012-07-19 오후 7:40:04
탐색알고리즘의종류와특징 순차탐색 섞여있는자료속에서하나씩순차적으로자료를비교해가며특정한자료를찾는방법으로, 자료가일정한기준에의해정렬되어있지않은경우에많이사용된다. 순차탐색으로자료를찾을경우, 최상의경우는가장먼저비교한자료와찾는자료가일치하는경우이며, 이때의비교횟수는 1이된다. 이와반대로최악의경우는찾는자료가가장마지막에있거나없는경우로, 이때의비교횟수는자료전체의개수와같다. 아무런전략없이탐색을하면원하는자료를찾기까지많은시간과노력을낭비할수있다. 따라서상황에맞는효율적인탐색방법을선택하는것이중요하다. 8 을찾는경우 ➊ 9 8 이므로탐색계속 9 5 8 3 7 ➋ 5 8 이므로탐색계속 순차탐색의특징 9 5 8 3 7 가장간단하고직접적인검색방법이라고할수있다. 검색해야하는자료의양에따라 ➌ 8 = 8 이므로탐색성공 효율의차이가크다. 자료를처음부터마지막까지순 9 5 8 3 7 서대로검색하므로선형검색이라고도한다. 그림 Ⅳ 18 순차탐색의예 한걸음더 / 컴퓨터의탐색작업 탐색은저장된자료중에서원하는항목을찾는것으로, 컴퓨터에서탐색은정렬과더불어기본적인작업이라고할수있다. 컴퓨터에저장된각각의자료는구별하여인식할수있는키를가지고있는데, 이를탐색키 (Search Key) 라고한다. 자료를탐색할때에는원하는탐색키를가진항목을찾는것이다. 탐색방법의효율성은어떠한구조의자료를사용하고있는지와자료의배열상태에따라영향을받으므로, 문제에맞는가장적절한탐색방법을선택하여야한다. 그림 Ⅳ 19 컴퓨터에서의파일과폴더검색 Ⅳ-2 문제해결절차 241 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 241 2012-07-19 오후 7:40:05
Q A 이진탐색은어느경우에활용하나요? 이름순으로정렬된전화번호부에서특정이름찾기 번호순으로정렬된영화관좌석에서내자리찾기 알파벳순으로정렬된영어사전에서단어찾기 이진탐색이진탐색은정렬된자료중에서처음과마지막자료의중간값자료와찾으려는자료를비교하여, 원하는자료가중간값보다작으면왼쪽부분, 크면오른쪽부분에서검색하는방법이다. 가운데있는값을기준으로왼쪽과오른쪽의두부분으로나누어서검색하므로이분검색이라고도한다. 자료를찾을때까지이진탐색을순환적으로반복수행함으로써검색범위를반으로줄여가면서빠르게검색한다. 이진탐색알고리즘은자료가많을수록효율적이지만, 자료가정렬되어있어야유용하게사용될수있으며, 자료의삽입이나삭제가자주일어나는경우에는비효율적이다. 5 를찾는경우 1 7 과비교 1 3 5 6 7 9 11 20 30 2 5<7 이므로앞부분만다시탐색 1 3 5 6 3 5 를 3 과비교 1 3 5 6 4 5>3 이므로뒷부분만다시탐색 5 5=5 이므로탐색성공 5 6 5 6 이진탐색의특징 자료의개수가많아져도검색시간이많이늘어나지않는다. 자료의평균비교횟수가적어탐색속도가빠르다. 자료가반드시정렬되어있어야한다. 그림 Ⅳ 20 이진탐색의예 242 Ⅳ. 문제해결방법과절차 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 242 2012-07-19 오후 7:40:16
정보플러스 인터넷검색노하우 특색있는단어를사용한다. 평상시쓰는문장을사용하지않는다. 비슷한단어나관련분야를생각한다. 필요없는키워드는버린다. 검색어의철자를조심한다. 범위를좁혀간다. 검색결과가단하나가나와도실망하지않는다. 분야별전문웹사이트를이용한다. 어디부터검색할지막막하면뉴스검색부터시작한다. 웹검색엔진에는 로봇 이라불리는특별한프로그램이사용되는데, 이로봇이웹사이트들을돌아다니면서각종정보를자동으로수집한다. 검색도움말을 꼭 읽는다. Ⅳ-2 문제해결절차 243 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 243 2012-07-19 오후 7:40:19
활동 15 순차탐색과이진탐색활용하기 다음은컴퓨터역사상큰업적을남긴위인들을나열한것이다. 파스칼라이프니츠폰노이만튜링배비지 순차탐색을활용하여문제를해결해보자. ⑴ 파스칼에서배비지까지각각의이름을찾기위한비교횟수를적어보자. 이름파스칼라이프니츠폰노이만튜링배비지 비교횟수 ⑵ 가장많은비교를하는경우의비교횟수를적어보자. 회 ⑶ 총비교횟수 : ⑷ 총자료수 : ⑸ 평균비교횟수 : 개 회 회 이진탐색을활용하여문제를해결해보자. ⑴ 명단을가나다순으로오름차순정렬을해보자. 이름 ⑵ ⑴ 에서정렬한명단을기준으로각각의이름을찾기위한비교횟수를적어보자. 이름 비교횟수 ⑶ 가장많은비교를하는경우의비교횟수를적어보자. 회 ⑷ 총비교횟수 : ⑸ 총자료수 : ⑹ 평균비교횟수 : 개 회 회 244 Ⅳ. 문제해결방법과절차 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 244 2012-07-19 오후 7:40:19
활동 16 순차탐색과이진탐색비교하기 다음과같이정렬된자료에서 56 을찾으려고한다. 순차탐색과이진탐색을활용하여각각탐색해보고, 비교횟수를적어보자. 45 46 47 48 49 50 51 52 53 54 55 56 57 구분순차탐색이진탐색 검색과정수 순차탐색과이진탐색중각각의상황에효율적인탐색방법을선택하여탐색하고, 선택이유를설명해보자. (1) 아래그림에는총몇쌍의같은그림이있는가? 효율적인탐색방법 선택이유 (2) 정보교과서 35 쪽을펼치려고한다. 가장효율적인탐색방법과그이유를설명해보자. 효율적인탐색방법 선택이유 Ⅳ-2 문제해결절차 245 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 245 2012-07-19 오후 7:40:20
체험활동 암호알고리즘만들기 예전에는암호를군사목적이나외교통신용으로만사용하였으나, 오늘날에는스포츠경기에서의사인, 컴퓨터의정보보안등우리생활에서다양한형태로쓰이고있다. 2명씩모둠을구성하여자기모둠만의암호를만들어보자. 1 문자로된메시지를전달할암호알고리즘을만들어보자. 암호알고리즘원문암호문 1. 알파벳을 1 자씩다음문자로바꾼다. 2. 띄어쓰는곳은앞의글자를반복해서사용한다. I like baseball Jjmjlffcbtfcbmm 암호알고리즘 2 만들어진암호알고리즘을이용하여상대방에게전달할 10 자내외의메시지를암호문으로만들어보자. 원문 암호문 3 각모둠별로만든암호문을서로교환하여해독해보자. 246 Ⅳ. 문제해결방법과절차 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 246 2012-07-19 오후 7:40:20
교과서밖정보세상 더욱은밀하게, 역사속의암호기법들 암호란, 원래의메시지를다른사람이의미를이해할수없는형태로변형하거나, 또는암호화된통신문을해독가능한형태로변환하기위한원리, 수단, 방법등을취급하는기술을의미한다. 현대에서는컴퓨터와인터넷같은정보기술의발달로정보의복제및유출이더욱심각해지고있어, 안전한암호화알고리즘에대한연구가활발하게진행되고있다. 카이사르의암호문 로마의율리우스카이사르는어느날 EH FDUHIXO IRU DVVDVVLQDWRU 라는문장을전달받는다. 이문장은영문알파벳의글자를 3개뒤로미루어서쓴간단한방식의암호문이었다. 해독하면원래의문장이 Be careful for assassinator( 암살자를조심하시오 ) 임을알수있었지만, 실제로암살자가누구인지알수없었던카이사르는결국최측근인브루투스에게암살되었다. 카이사르의암호문해독방법 에니그마와콜로서스 콜로서스 에니그마 다른예로, 제2 차세계대전당시독일군은군사정보의기밀성을유지하기위해 에니그마 라는암호기를만들어주요정보를주고받았다. 에니그마는타자기와같은모양을하고있으며, 원문의문자를두드리면암호문이만들어지고, 암호문을받은사람은다시에니그마를이용해서원문으로해독하는방식으로사용되었다. 영화 U보트 에서독일군의에니그마암호기를필사적으로탈취하려는모습이그려졌듯이, 이당시독일군의암호체계를알아내려는연합군의노력은필사적이었다. 그만큼군사작전에서정보의기밀성유지는중요한것이기때문이다. 하지만연합군의암호해독기 콜로서스 가개발된이후독일군의움직임이사전에파악됨으로써연합군은유리한위치를차지하여전쟁에승리하게되었다. Ⅳ-2 문제해결절차 247 정보 _4-2 문제해결절차 (220-247)_ 수정본.indd 247 2012-07-19 오후 7:40:22