알고리즘이란

Sep 19, 2021

알고리즘이란?

알고리즘의 정의

• 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법

• 컴퓨터가 계산 문제를 수행하기 위한 단계적 방법이나 도구

• 입력값을 받아 원하는 출력값을 내보내는 잘 정의된 계산 과정

코드 예시 (1~100까지 더하는 코드의 2가지 방법)

def calcSum(n) :
  sum = 0
  for i in range(1, n+1):
      sum = sum + i
  return sum

def calcSum2(n):
    return n*(n+1)//2

print(calcSum(100))
print(calcSum2(100))

알고리즘 표현법

슈도 코드(의사 코드)

Merge(A,p,q,r)
  n1=q-p+1
  n2=r-q
  //let L[1..n1+1] and R[1..n2+1] be new arrays
  for i = 1 to n1
      L[i] = A[p+i-1]
  for j = 1 to n2
      R[j] = A[q+j]
  L[n1+1] = inf
  R[n2+1] = inf
  i = 1
  j = 1
  for k = p to r
      if L[i]<=R[j]
          A[k] = L[i]
          i = i + 1
      else A[k] = R[j]
          j = j + 1

병합 정렬의 의사 코드

특정 프로그래밍 언어의 문법을 따라 쓰여진 것이 아니라, 일반적인 언어로 코드를 흉내 내어 알고리즘을 써 놓은 코드

• 의사 코드로 흉내만 냈으며, 컴퓨터에서 실행 불가능

• 알고리즘을 대략적으로 모델링하는데 쓰임

순서도(flow diagram)

• 프로그램, 작업의 진행 흐름을 순서에 따라 여러 가지 기호나 문자로 나타낸 도표

• 흐름도라고도 함, 프로그램의 논리적인 흐름, 데이터의 처리과정을 표현하는데 사용.

• 프로그램을 작성하기 전에 프로그램의 전체적인 흐름과 과정 파악을 위해 거쳐야하는 작업

알고리즘의 성능 분석

• 정확성: 얼마나 정확하게 동작하는가?

• 작업량: 얼마나 적은 연산으로 원하는 결과를 얻어내는가? (=시간 복잡도)

• 메모리 사용량 : 얼마나 적은 메모리를 사용하는가? (=공간 복잡도)

• 단순성: 얼마나 단순한가?

• 최적성 : 더 이상 개선할 여지 없이 최적화되었는가?

많은 문제에서 알고리즘의 성능 분석 기준으로 알고리즘의 작업량을 비교하여 실제 걸리는 시간을 측정, 또는 실행되는 명령문의 개수(주로 쓰임)를 계산한다.

이를 시간 복잡도로 많이 표기한다.

알고리즘 1 비교적 성능이 떨어진다.

def calcSum(n) :
  sum = 0 # 1번
  for i in range(1, n+1): # n 갯수마다 1번
      sum = sum + i # n 갯수마다 1번
  return sum
# 시간 복잡도 : 1 + n * 2= 2n+1
print(calcSum(100)) # 총 99번의 덧셈 연산

알고리즘 2 비교적 성능이 낫다.

def calcSum(n):
    return n*(n+1)//2 #3번
# 시간 복잡도 : 3
print(calcSum(100)) # 단 3번의 연산