[Algorithm] 0. Introduction

소프트웨어 개발

- 프로그램: 소프트웨어를 만드는 것

- 요구사항 분석 (What, 논리적 사고력, 추상화) → Design (How, 알고리즘) → Implement (Do it!, 프로그래밍 언어) → Test (Check) → Maintenance (Getting Better)

 

알고리즘이란?

- 전산학의 핵심 기술

- 컴퓨터를 사용하여 문제 해결하는 절차를 체계적으로 제시

- 특정한 일을 수행하는 명령어들의 유한 집합 (절차적 처리, 효율적 실행, 전략적 접근, 정확한 결과)

- 입력으로부터 출력을 생성해내는 과정

 

- A plan of solution for a problem (strategy)

- Find algorithms that are fast for very large inputs

- An algorithm is a sequence of unambiguous instructions

- i.e., for obtaining a required output for any specified input in a finite amount of time

Algorithmic Solution

 

알고리즘 학습 이유

- 학문적으로 매우 중요 (Theoretical importance): The core of computer science

- 실용적으로 매우 중요 (Practical importance): 특정한 문제를 위한 알고리즘의 습득, 체계적으로 생각하는 훈련, 지적 추상화의 레벨 상승, Expert in problem solving, Expert in programming

 

알고리즘 관련 기본 Issues

- How to design algorithms

- How to express algorithms

- Proving correctness

- Efficiency

- Optimality

 

좋은 알고리즘이란?

- Correctness

- Time efficiency

- Space efficiency

- 도전: Better algorithm에 대한 끊임없는 생각

 

알고리즘의 조건

- 입력 (Input): 외부에서 제공되는 데이터가 0개 이상

- 출력 (Output): 적어도 한 가지의 결과를 생성

- 명확성 (Definiteness): 각 명령들은 명확해야 하며 모호성 배제

- 유한성 (Finiteness): 알고리즘의 명령대로 수행하면 어떤 경우에도 유한개의 단계 뒤에는 반드시 종료

- 효율성 (Effectiveness): 간단하고 기본적인 절차로 구성

 

알고리즘 분석 기준

- 정확성 (Correctness)

- 수행량 (Amount of work done)
- 기억장소 사용량 (Amount of space used)
- 단순성/명확성 (Simplicity, Clarity)

- 최적성 (Optimality)

알고리즘 표현 방법

- 자연어: 한글/영어, 알고리즘 기술의 용이성, 자연어의 모호성에 의해 명확성 유지의 어려움

- 순서도: 좋은 알고리즘의 표현 방법, 규모가 큰 문제에 대해 코딩의 어려움

- Pseudo Code: 프로그래밍 언어에 가까우며 특정 언어의 구조에 제약 X, 실행을 위해선 새로이 코딩해야 함

 

문제 해결

- Problem Solving

   - Accomplish purpose; Need Strategies

   - Analysis

   - Methodology

   - Environments

   - Prediction of Consequences

   - Optimization

   - Adoptable Result

 

문제 해결을 위한 전략

- Brute force

- Divided and conquer

- Decrease and conquer

- Transform and conquer

- Greedy Method

- Dynamic Programming

- Backtracking

- Branch & Bound