알고리즘의 기본 개념
알고리즘
교재: 쉽게 배우는 알고리즘: 관계 중심의 사고법 저자: 문병로
출판사: 한빛미디어, 2013년 발행
수업 목표
알고리즘의 개념 이해
알고리즘의 요건
알고리즘 기술 언어
알고리즘의 분석
용어 정의
알고리즘 이란?
문제 해결 절차를 체계적으로 기술한 것
문제의 요구조건
입력과 출력으로 명시할 수 있다.
알고리즘은 입력으로부터 출력을 만드는 과정 을 기술입출력의 예
문제
100명의 학생의 시험점수의 최대값을 찾으라 입력
100명의 학생들의 시험점수 출력
위 100개의 시험점수들 중 최대값프로그램 작성을 위한 접근 방법 (1/2)
컴퓨터를 사용하여 문제를 풀려면 최종적으
로는 그 문제를 해결하는 프로그램을 작성
해야 한다.
프로그램 작성을 위한 접근 방법 (2/2)
방법 1 문제의 파악
프로그램 작성 프로그램
방법 2 문제의 파악
프로그램 작성 프로그램 문제 해결 단계
해결방안 구상 (알고리즘)
알고리즘 공부의 목적
특정한 문제를 위한 알고리즘의 습득
체계적으로 생각하는 훈련
지적 추상화의 레벨 상승
Intellectual abstraction
연구나 개발에 있어 정신적 여유를 유지하기 위 해 매우 중요한 요소알고리즘의 요건
① 외부에서 0개 이상의 입력을 받아들여, 하나 이상의 출력을 생성한다.
② 각 단계가 단순하고 모호하지 않아야 한 다.
③ 한정된 수의 작업 후에는 반드시 끝나야 한다.
④ 모든 명령이 수행 가능해야 한다.
⑤ 효율적이어야 한다.
바람직한 알고리즘
명확해야 한다
이해하기 쉽고 가능하면 간명하도록
지나친 기호적 표현은 오히려 명확성을 떨어뜨 림
명확성을 해치지 않으면 일반언어의 사용도 무 방 효율적이어야 한다
같은 문제를 해결하는 알고리즘들의 수행시간 이 수백만배 이상 차이 날 수 있다
컴퓨터가 수행할 수 있게 하기 위해서는 알고리즘에 포함 될 수 있는 연산들에 약간의 제한들이 존재
각 연산(operation)은 명확하고 확실
예)
X에 6을 더해야 할지 7을 더해야 할지 확실하지 않고 문장의 수 행 결과도 분명하지 않음ADD 6 OR 7 TO X.
알고리즘 기술 언어
의사 코드 (pseudo code)
프로그래머가 기억하기 쉬운 연상 언어(mnemonic language)로 작 성한 컴퓨터 명령어
특정한 프로그래밍 언어의 문법과는 상관없이 영어나 국어와 같이 읽을 수 있도록 프로그램 논리를 명시하기 위해 작성한 것
특정 프로그래밍 모듈의 목적을 어느 정도 일반적인 용어로 단순 히 표현하는 데 사용의사 코드 예
1부터 10까지 더하여 결과를 얻는 문제에 대한 해결 방법① 시작한다.
② 데이터 값의 변수 I와 합의 변수 S를 모두 0으로 둔다.
③ 데이터 변수 I의 값을 1 증가시킨다.
④ 합 S와 I를 더하여 그 값을 합으로 한다.
⑤ 만약 I의 값이 10보다 작으면 ③으로 가서 계속한다.
⑥ I와 S의 값을 출력한다.
⑦ 실행을 마친다.
의사 프로그램(pseudo program)
의사코드를 사용
특정한 컴퓨터나 프로그래밍 언어에 구애받지 않고,
프로그래 머가 표현하기 쉽도록 처리 절차를 의사코드를 사용하여 작성 하는 것
의사 언어(pseudo language)
독특한 일을 수행할 수 있도록 특별히 인위적으로 만든 언어
선택된 표현에 부합되는 특별한 의미를 나타낼 수 있도록 고안된 규칙의 집합C 언어에 기반을 둔 의사 언어
sample(A[ ], n) {
sum ← 0 ;
for i ← 1 to
nsum← sum+ A[i] ;
return
sum ;}
