[컴퓨터알고리즘] Ch 2. 알고리즘을 배우기 위한 준비

사진을 클릭하면 PDF 정리본 다운로드 링크로 이어집니다.

🧐 2.1 알고리즘이란

• 알고리즘이란

  • 문제를 해결하는 단계적 절차 또는 방법

  • 컴퓨터를 이용해 해결할 수 있어야 함.

  • 입력이 주어지고, 수행 결과인 해(답)을 출력.
    
    

• 알고리즘의 일반적 특성

🧐 2.2 최초의 알고리즘

• 유클리드의 최대공약수 알고리즘
  • 기원전 300년경에 만들어진 가장 오래된 알고리즘
  • 최대공약수란 2개의 자연수의 공약수들 중에서 가장 큰 수

• 2개의 자연수의 최대공약수는 큰 수에서 작은 수를 뺀 수와 작은 수와의 최대공약수와 같다.

👨🏻‍🔬 유클리드의 최대공약수 알고리즘에서 뺄셈 대신 나눗셈을 사용하면 빠르게 해를 찾는다.

👩🏻‍💻 의사코드로 표현해본다면?

Alg EuclidRecur(a, b)

1. if b == 0 return a

2. return EuclidRecur(b, a mod b)

👨🏻‍🔬 재귀 호출 대신 반복문을 이용하면 더 빠르게 해를 찾는다.

👩🏻‍💻 의사코드로 표현해본다면?

Alg EuclidIter(a, b)

input integer a, b (a >= b)
output integer gcd

1. gcd <- 1

2. for i <- 1 to b
    if(a % i == 0 && b % i == 0)
        gcd <- i

3. return gcd

👨🏻‍🔬 반복문을 수정하면 더욱 효율적인 알고리즘이 된다.

👩🏻‍💻 의사코드로 표현해본다면?

Alg EuclidIterDown(a, b)

input integer a, b (a >= b)
output integer gcd

1. gcd <- 1

2. for i <- b down to 1 
    if(a % i == 0 && b % i == 0)
        return i

🧐 2.3 알고리즘의 표현 방법

• 일반적으로 알고리즘은 의사 코드(pseudo code)로 표현

• 알고리즘의 각 단계는 보통 말로 서술할 수 있으며, 컴퓨터 프로그래밍 언어로만 표현할 필요는 없음.

• 표현 가능한 방식
  • 보통 말로 표현
  • 의사 코드로 표현
  • 플로우 차트

이후 생략

시간 복잡도 등등.. 자료구조와 동일