📚알고리즘이란?

• 9세기경 수학자 알콰리즈미(Al Khwarizmi)의 이름에서 유래
• 문제의 복잡성에 따라 컴퓨터 프로그램을 통하여 문제를 해결할 수 있는 것
• 알고리즘 컴퓨터 프로그램을 작성하는 바탕이 되는 것
• 어떤 작업을 수행하기 위해 입력 받아 원하는 출력을 만들어내는 과정을 기술한 것
• 작업을 수행하는 방법을 정의하는 단계들의 집합
• 수학문제를 풀기 위해 정의나 정리들을 활용하는 것과 같이 컴퓨터에서는 알고리즘을 활용함
• 자료구조를 바탕으로 프로그램이 효율적으로 동작하는 방법을 알려줌
  → 프로그램 = 자료구조 + 알고리즘
• 실행시간이 짧고, 사용하는 메모리 공간이 적은 효율적인 알고리즘을 선택하여 사용
  ex) 내비게이션, 인터넷 검색, 제조 공정, 현금자동인출기(ATM) 등

알고리즘의 조건

	알고리즘의 조건
입력	0개 이상의 데이터 입력이 있어야 한다.
출력	적어도 하나 이상의 결과를 출력해야 한다.(결과물이 있어야한다.)
명확성	각 단계와 명령은 모호하지 않고 명확해야 한다.
유한성	유한한 단계를 거친 후에는 반드시 종료해야 한다.(너무 긴 시간이 걸린다면 알고리즘 사용이 소용없음)
유효성	각 명령어들은 실행 가능해야 한다.

효율적인 알고리즘 선택

• 프로그램의 성능에 많은 영향

  • 정확성 / 작업량 메모리 / 사용량 / 단순성 / 최적성

• 개개의 연산을 빠르게 하도록 하는 것보다는 빠른 알고리즘을 찾는 것이 우선

• 알고리즘 설계 후 자원(소요시간, 메모리, 통신대역 등)을 얼마나 소모하는지 분석이 필요

  • 전체 실행 시간이 짧으면서 메모리와 같은 컴퓨터 자원들을 적게 사용하는 알고리즘
  • 알고리즘의 실행 시간을 효율적인 알고리즘의 기준을 삼는다.

  👉 프로그램을 분석하는 목적

• 작성된 프로그램의 수행시간을 예측하고 확인

• 좀 더 빠른 시간에 수행할 수 있는 프로그램을 작성할 수 있도록 하기 위함

  👉 프로그램의 수행 시간 계산 - 알고리즘의 종류

• 최악의 경우 분석(Worst-case Analysis) → 가장 의미 있는 분석방법

  • ‘어떠한 입력이 주어지더라도 알고리즘의 수행시간이 얼마 이상은 넘지 않는다’
    → 상한(Upper Bound)의 의미
  • 수행 시간이 가장 늦은 경우

• 평균의 경우 분석(Average-case Analysis)

  • 균등 분포(Uniform Distribution)를 가정
  • 수행 시간이 평균적인 경우 분석

• 최선의 경우 분석(Best-case-Analysi)

  • 수행 시간이 가장 빠른 경우 분석
  • 최적(Optimal) 알고리즘을 찾는데 활용

알고리즘 설계 기법

• 분할 정복(divide and conquer)
  • 해결하려고 하는 문제를 작은 여러개의 부분 문제로 분할하여 문제를 해결
  • 작은 부분의 문제를 해결 한 뒤 그 해답들을 통합하여 본래의 문제를 해결
  • 분할(divide), 정복(conquer), 결합(combine)
• 동적 프로그래밍(dynamic progrmming)(D.P)
  • 문제를 여러 개의 하위 문제로 나누어 푼 다음 그것을 결합하여 최정적인 목적에 도달
  • 분할 정복과 유사하지만 동적 프로그래밍은 부분 문제들이 의존적인 관계를 가짐
• 그리디 알고리즘(greedy algorithm)
  • 선택해야할 방법이 여러 가지일 때 현재 상황에서 가장 최선인 것을 먼저 선택하는 기법
• 백트래킹(backtracking)
  • 우선 어떤 하나의 가능한 경우를 확인하고 가능하지 않다면 다시 되돌아가고 다시 다른 가능성이 있는 경우를 확인해감
  • 재귀 함수를 사용하여 구현