컴퓨터 개론 - 알고리즘의 개요

1. 문제 해결과 알고리즘의 개념

• 문제를 해결하는 논리적인 절차가 알고리즘

1) 문제해결(Problem Solving)이란?

• 문제들을 해결하기 위한 방법과 절차 또는 행동
• 중요한 기술이나 순서의 제어를 요하는 인지과정

(1) 컴퓨터 과학

• 알고리즘에 관한 공부(“Computer Science is the study of algorithm”)를 하는 학문

(2) 컴퓨터적인 사고(computatinal thinking)

• 컴퓨터를 활용하여 어떻게 세상 문제를 해결할지 주어진 문제와 상황을 창의성을 가지고 사고하고, 알고리즘과
  연관 지어 해결하는 것
• 문제를 푸는 과정이 알고리즘

2) 알고리즘의 정의

• 알고리즘은 모호하지 않은 일련의 절차와 명령의 집합
• 모든 절차는 컴퓨터에 의하여 수행가능 해야 함

(1) 알고리즘은 반드시 종결하는 절차

• 예외적인 경우를 제외하고 위의 세가지 조건을 만족
• 알고리즘은 모호하지 않는 일련의 절차나 명령의 집합
• 알고리즘의 모든 절차는 컴퓨터에 의하여 수행가능 해야함
• 알고리즘은 반드시 종결해야함
• 운영체제는 알고리즘이 아니다.

(2) 소프트웨어와 알고리즘의 관계

1. 알고리즘은 ‘잘 정의된 기본 절차’들을 이용하여 실현
2. 잘 정의된 기본절차는 어떤 시스템을 만드는 빌딩 블록의 역할
3. 프로그램의 개발에도 ‘잘 정의된 기본절차’를 이용하여 알고리즘을 실현. 때로는 의사코드를 이용
4. 프로그램 언어는 알고리즘을 표현하기 위한 수단

2. 알고리즘의 중요성과 데이터

• 프로그램은 처리할 데이터를 기억하기 위한 데이터구조와 처리절차를 나타내는 알고리즘

1) 알고리즘의 중요성

(1) 문제해결 방법론

• 숫자, 문자, 사운드, 이미지, 그래픽, 동영상 등 동일한 2진 데이터를 다르게 해석

(2) 알고리즘 분석의 필요성

• 어떤 문제를 해결하기 위한 알고리즘이 여러 개 존재하는 경우, 각각의 알고리즘을 여러가지 방법으로 분석하여
  좋은 알고리즘을 선택, 활용 하는것이 중요함

(3) 좋은 알고리즘 이란?

• 어떤 문제를 해결하기 위해서 여러 알고리즘이 존재하고, 그 중 가장 시간이 적게 소요되는 알고리즘이 좋은 알고리즘
• 영어사전을 이용해서 단어 검색하는 방법(=좋은 알고리즘)

(4) 알고리즘 수행시간 비교

• 알고리즘의 수행시간은 최상의경우, 최악의 경우, 평균적인 경우로 구분됨
• 알고리즘의 수행시간 복잡도(Time Complexity)는 자료의 종류, 자료의 상태에 따라서 달라짐
• 알고리즘의 수행시간 복잡도는 최악의경우와 평균적인 경우를 구하여 효율적인 알고리즘을 선택함

(5) 효율적인 알고리즘

(5-1) 일반적 알고리즘 분석

• 수행시간 복잡도는 최악의 경우와 평균적인 경우를 기준으로 이루어지며, 자료의 상황에 따라서 성능이 달라짐
• 과거는 공간복잡도도 평가하였으나 오늘날은 의미가 없음

• 예상 소요 시간인 경우 : 항공기
• 비용인 경우 (탑승자의 수 고려)
• 비용 + 소요 시간인 경우

3) 알고리즘과 데이터구조

(1) 알고리즘과 데이터구조의 관계

• 알고리즘을 효율적으로 실행하기 위하여 효율적인 데이터구조가 필수적
• 데이터구조 + 알고리즘 + 프로그래밍 언어 = 프로그램

• 공통으로 많이 사용되는 데이터구조 연산 : 순회, 탐색, 삽입, 삭제, 정렬, 병합 등
• COBOL, PL/I등의 프로그램 구조는 “선언문 + 프로시저”로 구성

(2) 데이터 추상화 (Data Abstraction)

• 데이터 구조가 어떻게 구성되어 있는지 또는 데이터구조에 적용되는 연산이 어떤 절차로 수행되는지를 알지 못해도
  이용할 수 있는 개념
• 프로그램의 독립성이 강해짐
• 추상 데이터 형 (ADT : Data Abstraction Type) = 클래스의 개념

(2-1) 외부 인터페이스를 통해 접근하는 ADT 개념