[67] 알고리즘 01차시 알고리즘 개요

1. 알고리즘의 개념

가. 알고리즘이란?

어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것

어떤 일을 수행할 수 있는 일련의 명령어 또는 규칙의 집합

알고리즘을 설계하기 위해서는 해야 할 작업을 명확하게 명시해야 함

문제해결이나 처리 과정에서의 순서를 단계적으로 서술

나. 문제해결을 위한 알고리즘(예시)

1) 자동차 네비게이션

두 지점 간의 최단 경로나 최단 시간이 걸리는 경로

-> 최단 경로 알고리즘

2) 현금자동인출기(ATM)

여러 지역의 수많은 ATM의 잔고를 유지하며 자금을 운용하는 방법

-> 스케줄링 알고리즘 등

3) 인간 게놈 프로젝트

방대한 DNA 데이터 간의 관계 파악

-> 게놈 서열 간의 유사성을 파악하는 알고리즘 등

4) 인터넷 검색

수 조 페이지 이상의 데이터 중에서 원하는 결과를 검색

-> 최대한 빨리 정확한 검색 결과를 제공하는 알고리즘

5) 반도체 설계

하나의 반도체 칩에는 수천수만 개의 게이트 존재

-> 게이트의 배치와 논리적 연결 구조 설계 알고리즘

6) 제조업

제조 공정에서 작업의 선후 관계가 존재

-> 위상 정렬 알고리즘

다. 문제를 알고리즘으로 작성하는 과정

1) 문제 분석

주어진 문제에 대한 논리적 분석을 통하여 핵심 사항들을 분석

2) 데이터 수집과 표현

문제 해결과 관련된 정보들을 수집하며 데이터를 적절한 형태로 표현

3) 분해

복잡한 문제를 보다 쉽게 다룰 수 있도록 여러 개의 작은 부분들로 쪼개어 분해

4) 패턴인식

문제 내에서 공통적인 유사성이나 규칙을 찾아냄.

5) 추상화

문제에서 필요 없는 부분들을 걸러내고 복잡한 문제나 아이디어를 단순화

6) 알고리즘

문제에 대한 단계적인 해결책, 설명, 지시 사항들을 설계

7) 평가

알고리즘의 정확성, 해답의 적절성, 효율성 등을 최종 점검

평가 완료 후에는 알고리즘을 기반으로 코딩

2. 알고리즘의 특성

가. 알고리즘의 특성

1) 입력

문제를 풀기 위한 입력이 반드시 필요함.

2) 출력

문제를 해결했을 때 그 결과인 출력이 반드시 존재해야 함.

3) 유한성

알고리즘은 일정한 시간 내에 반드시 종료되어야 함.

알고리즘 수행이 끝나지 않거나 매우 오래 걸리면 해를 얻을 수 없음.

4) 정확성

주어진 문제에 대한 정확한 출력값을 만들어야 함.

5) 일반성

같은 유형의 문제에 모두 적용 가능

나. 알고리즘은 생각하는 방법을 훈련하는 것

문제 자체를 해결하는 알고리즘을 배움.

그 과정에 깃든 '생각하는 방법'을 배우는 것이 더 중요(체계적으로 생각하는 훈련)

미래에 다른 문제를 해결하는 생각의 빌딩블록을 제공

3. 알고리즘의 표현 방법

가. 알고리즘은 여러 가지 방법으로 표현 가능

1) 순서도(Flow Chart)

문제 해결 과정을 기호와 도형을 사용하여 표현하는 방식

https://ko.wikipedia.org/wiki/순서도

순서도 - 위키백과, 우리 모두의 백과사전

2) 의사코드(Pseudocode)

프로그램 명령문 형식을 취하고 각 명령을 사람이 이해하기 쉽게 적당한 뜻을 가진 단어로 나타냄.

https://ko.wikipedia.org/wiki/의사코드

의사코드 - 위키백과, 우리 모두의 백과사전

3) 일반적인 언어

사람이 사용하는 문장으로 설명

나. 알고리즘의 구현 과정

알고리즘은 문제를 해결하기 위한 체계적이고 순서적인 절차

논리적 표현으로 변환하면 순서도나 의사코드로 변환 가능

알고리즘을 프로그래밍 언어로 변환하면 컴퓨터 프로그램

최종적으로 컴퓨터 프로그램을 실행하여 결과를 얻음.