알고리즘 조건 / 알고리즘 설계 / 효율적인 알고리즘 (고등학교 정보 교과서 정리)

    알고리즘

 

 

 

 

➊ 알고리즘

𐩐알고리즘 : 문제 해결 절차(과정)를 논리적 순서로 설명하거나 표현(기술하여 표현)하는 문제 해결 절차나 방법

 

➝알고리즘 조건 ➀입력 ➁출력 ➂명확성 ④유한성 ⑤수행 가능성

 

알고리즘의 5조건	입력	외부에서 제공되는 0개 이상의 입력이 필요하다.
	출력	적어도 하나 이상의 출력(결과)이 있어야 한다.
	명확성	각 명령이나 연산자들은 모호하지 않고 명확해야 한다.
	유한성	해당 알고리즘의 명령대로 수행하면 한정된 단계를 처리하고 반드시 종료되어야 함
	수행 가능성	모든 명령은 명백하게 실행이 가능해야 함
󰄤 숫자 게임 알고리즘에서 알고리즘 조건 찾기  게임을 시작한다.(점수=0점)  30초의 제한 시간이 주어진다.  0부터 9까지의 숫자를 순서대로 찾는다.  숫자를 순서대로 찾을 때마다 점수가 1점씩 오른다.  만약 제한 시간이 남으면, 번으로 돌아간다.  게임이 끝난다.

 

입력	출력	명확성	유한성	수행 가능성
숫자를 순서대로 찾는다	점수를 보여준다	언제 점수가 오르는지 명확	게임 제한 시간 있음	숫자 게임 알고리즘을 수행하면 숫자 게임 할 수 있다

 

 

 

󰄤 하노이의 탑 (규칙) 𐩐 큰 원반은 작은 원반 위에 올라갈 수 없다. 𐩐 한 번에 하나의 원반만 옮길 수 있다 𐩐 최소한의 움직임으로 원반 옮겨야 함

 

입력	출력	명확성	유한성	수행 가능성
기둥 A에 크기가 다른 3개 원반 있다	기둥 A에서 기둥 C로 3개 원반이 이동되었다	한 번에 하나의 원반만 이동. 단, 큰 원반은 작은 원반 위에 올라갈 수 없다	최소한의 움직임으로 원반을 이동	규칙에 따라 원반 이동시키면 기둥 A에 있는 3개 원반을 기둥 C로 이동할 수 있다

 

 

 

 

② 알고리즘 설계

알고리즘 설계	의사 코드	사람들이 사용하는 언어로 프로그램 코드를 흉내내어 알고리즘을 표현하는 방법
	순서도	정해진 기호 이용해 알고리즘 표현하는 방법

 

 

 

<순서도 기호>

	시작과 끝		자료의 입력과 출력
	문제의 조건		실행 흐름
	처리 : 계산 등 자료 처리

 

 

 

<알고리즘 제어 구조>

순차 구조	선택 구조	반복 구조
시작부터 종료까지 순서대로 명령을 실행	주어진 조건에 따라 실행하는 명령이나 순서가 달라짐	주어진 조건에 따라 특정 명령을 반복적으로 실행
	무인 발권기 생겼을 때	여러 장 (다른 영화) 티켓 추가

 

 

 

 

③ 효율적인 알고리즘

 

𐩐효율적인 알고리즘 조건

➀ 기억 장소의 사용량이 적을수록 효율적인 알고리즘	➝ 즉, 적은 기억 장소, 적은 작업량,     수행 시간이 짧은 알고리즘
➁ 작업량 적고 수행 시간이 짧을수록 효율적인 알고리즘
➂ 조건 ➀ ➁를 동시에 만족하는 알고리즘이 가장 효율적이지만, 두 조건 모두 만족하기 어렵다면 수행 시간이 짧은 것이 좋다.

 

예>  1부터 10까지 합을 구하는 문제
<방법 1> 1+2+3+ 𐩐𐩐𐩐 +10 =55 𐩐1부터 10까지 숫자를 차례대로 더하는 방법 ➝더하는 구간이 커지면 연산 수가 비례 증가해 문제 해결 시간도 증가한다.	<방법 2> 1 2 𐩐𐩐𐩐 9 10 10 9 𐩐𐩐𐩐 2 1 11 11 𐩐𐩐𐩐 11 11 11 x 10 ÷2 = 55 𐩐문제의 규칙만 이해하면 작업량으로 숫자의 범위와 상관없이 일정한 수행 시간을 갖게 된다. ➝구간 크기와 상관 없이 일정한 연산하므로 문제 해결 시간이 일ㄹ정하다.

 

󰄤 강 건너기 알고리즘

<문제 상황> 덧셈, 곱셈 중 원하는 연산자를 선택하면 두 정수의 값을 계산해 출력한다. ➝ 선택 구조
<알고리즘 단계> ➀ 두 정수값을 입력받는다 ➁ 연산자를 선택한다 ➂ 만약 덧셈 연산자를 선택하면 두 정수값을 더해 결과를 출력한다. 그렇지 않으면 (곱셈 연산자를 선택하면) 두 정숫값을 곱해 결과를 출력한다.

 

<문제 상황> 버스 전용 차로 다닐 수 없는 차 구분하기
<조건> 버스 전용 차로는 9인승 이상 차만 다닐 수 있다. 그러나 구급차와 소방차는 버스 전용 차로 자유롭게 이용 가능	<알고리즘 작성> 구급차나 소방차 또는 9인승 이상 차인가? 버스 전용 차로를 이용할 수 있다. 그렇지 않으면 버스 전용 차로를 이용할 수 없다.