컴퓨터 알고리즘의 이해

일점 돌파.

---

효율적인 프로그래밍이란?

하드웨어의 성능 향상은 한계가 있으며, 소프트웨어 성능 향상을 효율화하기 위해서 아래의 항목들에 대해서 차차 알아간다.

• 시간복잡도, 공간복잡도
• 정렬 알고리즘
• 효율적인 계산 방법
• 수행 시간 분석

위의 내용들에 대해서 효율적인가에 대한 부분들을 중점적으로 같이 보려고 함.

알고리즘

• 문제 해결 방법
  • 정량
  • 절차

주어진 문제를 어떻게 해결할 것인가 ? - Recipe와 같이 정량화, 수치화, 절차화가 되어 있는 상태

• 장점
  • 누구든지 방법만 배우면 사용할 수 있다.
  • 우리는 어떤 알고리즘이 어떤 문제를 풀고 상황에 적합한 알고리즘을 사용하면 된다.

컴퓨터 알고리즘의 의미

• 컴퓨터 언어
  • 컴퓨터와 대화하기 위해서 사용하는 언어
• 컴퓨터 알고리즘
  • 컴퓨터를 이용하여 주어진 문제를 풀기 위한 방법이나 절차
    • 정렬 알고리즘, 해시 알고리즘, 최단거리 알고리즘
• 컴퓨터 프로그램
  • 컴퓨터가 특정 작업을 수행하기 위해서 짜여진 명령의 순서

=> Computer Language + Computer Algorithm = Computer Program

우리가 어떤 목적지를 가능 방법

우리가 어떤 목적지를 가기 위해서는 다양한 방법들이 존재한다. 예를 들어

• 버스를 타고서
• 지하철을 타고서
• 택시를 타고서
• 자전거를 타고서
• 걸어서

갈 경우, 우리는 주로 지하철을 타고 간다. 왜 일까? 우리의 비용와 효율성을 생각하게 되는데, 택시를 탈 경우, 가장 빠르게 목적지로갈 수 있지만, 비용이 가장 많이 드는 방법이고, 걸어서 가는 경우에는 비용은 가장 적게 들지만 가장 느리게 목적지에 도작하게 된다. 그래서 우리는 주로 가장 빠르지는 않지만 적당히 빠르고 비용도 적당한 지하철을 타고 가게 된다. 결국 목적지를 가기 위해서 비용과 효율성의 가장 적합한 방법을 정하게 된다. 그 상황에 맞는 가장 효율적인 방법을 정의하는 것이 중요한데, 결국 컴퓨터 알고리즘이 가지는 의미와 동일하다.

컴퓨터 알고리즘을 설명하기 위한 4단계

• 문제 정의
  • 해결하고자 하는 문제는 무엇인가?
  • 입력과 출력의 형태로 정의될 수 있는가?
  • 컴퓨터가 수행할 수 있는 형태로 전환이 가능한가?
• 알고리즘 설명
  • 컴퓨터가 수행할 내용을 하나씩 차례대로 설명하는 과정
• 정확성 증명
  • 과정대로 수행하면 출력으로 항상 올바른 답을 내보내는 가?
  • 잘못된 답을 내보내는 경우는 없는가?
  • 올바른 출력을 내보내고 정상적으로 종료되는가?
• 성능 분석
  • 수행시간
  • 사용공간

수행시간을 분석하는 방법은?

• 수행 시간은 입력으로 크기가 커지면 커질수록 시간이 많이 걸린다.

  • 10개의 키를 정렬하는 시간이 100개의 키를 정렬하는 시간보다 길다.

• 따라서 수행 시간은 n에 대한 함수로 표현한다.

  • 예를 들면 T(n)
  • 또한 n에 대한 다항식에서 최고차 항만을 고려한다.

• 특정 기계에서 수행시간을 출정하는 것은 공정하지 않다. 따라서 조건이 동일한 특정 기계에서 모든 알고리즘의 수행시간을 측정해야 하는데 이 방법은 현실적으로 불가능하다. 따라서 수행 연산의 횟수를 비교하는 방식으로 성능을 분석한다.

• 수행 시간은 입력으로 크기가 커지면 커질수록 시간이 많이 걸린다. 따라서 수행 시간은 입력 크기 n에 대한 함수로 표현한다.

성능 분석의 비교 대상

• 산술연산 : Add, Multiply, Exponent, Modular …
• 데이터 입출력 : Copy, Move, Save, Load … - 메모리 관련 등등
• 제어 연산 : If, While, Register … - 무한루프 등등

그 알고리즘을 구성하는데 가장 메인이 되는 연산의 횟수를 이용하여 상대적인 비교 수행이 가능하다.

컴퓨터 알고리짐의 성능 분석

• 빅오 표기
• 오메가 표기
• 세타 표기

T(n) 으로 표현하고 최고차항으로 고려

재귀함수에 대한 성능 분석

• Substitution Method : 대체법

해답의 형태를 추측 -> 수학적 귀납법을 이용하여 추측한 해답이 맞음을 증명

• Recursion-tree Method

  재귀함수에 대한 성능 분석

• Master Method

https://www.youtube.com/watch?v=R8JWtzfgeNM&list=PL9mhQYIlKEheVMo9pVitEm4dJG9i3Jrmt [컴퓨터 알고리즘 이해 1강 - 알고리즘과 점근적 표기법	T아카데미]
https://www.youtube.com/watch?v=8NtCxer9pKM&list=PL9mhQYIlKEheVMo9pVitEm4dJG9i3Jrmt&index=2 [ 컴퓨터 알고리즘 이해 2강 - 정렬 알고리즘	T아카데미 ]