[Algorithm] 알고리즘이란?

알고리즘

알고리즘은 '절차'다. 구체적으로 설명하면, 알고리즘은 '문제나 과제를 해결하기 위한 처리 절차를 하나하나 구체적인 순서에 따라 표현한 아이디어나 생각' 이라고 할 수 있다.
알고리즘이란 '생각' 또는 '아이디어'이기 때문에 형태가 없다. 따라서 어떤 것을 다른 사람에게 전달하려면 눈에 보이도록 표현해야 한다. 레시피, 악보, 사용 설명서는 알고리즘을 다른 사람에게 전달하기 위해 사람이 이해하기 쉬운 문장, 사진, 도형, 일러스트 등을 이용해 표현한 것이다.

• 알고리즘의 예
  • 요리의 레시피: 요리 절차 -> 문장화 -> 레시피
  • 음악의 악보: 연주 절차 -> 도면화 -> 악보
  • 가전제품 등의 사용 설명서: 기계 조작, 사용 절차 -> 일러스트화 -> 사용 설명서
    
    출처

알고리즘의 조건

알고리즘은 다음의 조건을 만족해야 한다.

• 입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.
• 출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다.(즉 모든 입력에 하나의 출력이 나오면 안됨)
• 명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.
• 유한성(종결성) : 유한번의 명령어를 수행 후(유한 시간 내)에 종료한다.
• 효율성 : 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다.

알고리즘과 프로그램의 관계

사람에게 전달하듯 컴퓨터에게도 어떤 명령을 내려야 하는데, 이때 문장, 일러스트, 그림, 사진 등은 컴퓨터가 이해할 수 없기 때문에 컴퓨터가 이해할 수 있는 언어로 명령을 내리게된다. 그리고 이때 내리는 명령어가 '프로그래밍 언어'이다.

• 알고리즘을 프로그래밍 언어로 기술한 것을 '프로그램', 프로그램을 작성하는 작업을 '프로그래밍'이라 한다.
• 알고리즘을 프로그래밍 언어로 기술하면 프로그램이 된다.
• 프로그래밍 언어는 컴퓨터에 지시하기 위한 인공 언어이다.

프로그램 작성의 흐름: 기획 -> 설계 -> 프로그래밍(코딩) -> 디버깅 -> 문서 작성

• 기획: 고객이 요구한 내용과 기능, 사양을 구체적으로 수용하여 기획서를 작성.
• 설계: 요구에 부응하기 위해 어떠한 기능이 필요하고 어떤 프로그램을 만들지를 고려, 알고리즘을 고려.
• 프로그래밍(코딩): 프로그래밍 언어를 사용하여 알고리즘을 프로그램으로 만들어가는 과정.
• 디버깅: 동작 테스트를 하는 것. 기대한만큼의 결과가 나타나지 않았을 때, 어디에 문제가 있는지 규명하여 이를 수정하여야 하는데 이렇게 오류를 찾아내어 수정하는 과정을 '디버그(debug)'라고 한다.
• 문서 작성: 프로그래머를 위한 문서와 사용자를 위한 문서를 작성한다.

알고리즘 분석 방법

알고리즘의 분석에서는 2가지 측면을 고려할수 있다

1. 시간복잡도(time complexity) - 속도
2. 공간복잡도(space complexity) - 메모리 사용량
   대게 알고리즘의 복잡도를 이야기할 때는 시간복잡도를 말한다. 이유는 위에서 언급했듯이 알고리즘은 시간을 더 중요시 생각하기 때문이다.

빅오 표기법(Big-O notation)

빅오 표기법을 사용하면 시간 복잡도 함수의 증가에 많이 기여하지 못하는 항을 생략함으로써 시간 복잡도를 간단한게 표시할 수 있다.
빅오표기법을 얻는 간단한 방법은 최고차 항만 남기고 다른 항들과 상수를 버리는것이다. 궁극적으로 최고차 항의 계수도 버리고 최고차 항의
차수만을 사용한다.
이처럼 최고차 항만 남기고 다른 항들과 상수를 버리는 것은 다른 항들과 상수는 시간 복잡도 함수의 증가에 많이 기여하지 못한다는 뜻이다
입력 값이 작을 때는 영향을 끼칠 수 있겠지만 입력값이 커지면 커질수록 다른항들이나 상수가 실행속도에 영향을 미치는 부분은 미비하다.

많이 쓰이는 빅오 표기법 (실행시간이 빠른 순)

출처

• O(1) : 입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘 (상수형)
• O(log N) : 입력 자료의 크기가 N일경우 log2N 번만큼의 수행시간을 가진다. (로그형)
• O(N) : 입력 자료의 크기가 N일경우 N 번만큼의 수행시간을 가진다. (선형)
• O(N log N) : 입력 자료의 크기가 N일경우 N*(log2N) 번만큼의 수행시간을 가진다. (선형로그형)
• O(N2) : 입력 자료의 크기가 N일경우 N2 번만큼의 수행시간을 가진다. (2차형)
• O(N3) : 입력 자료의 크기가 N일경우 N3 번만큼의 수행시간을 가진다. (3차형)
• O(2n) : 입력 자료의 크기가 N일경우 2N 번만큼의 수행시간을 가진다. (지수형)
• O(n!) : 입력 자료의 크기가 N일경우 n(n-1)(n-2)... * 1(n!) 번만큼의 수행시간을 가진다. ex)외판원 문제(TSP)의 기본적인 해법(팩토리얼형)

알고리즘의 세가지 기본형(기본 구조)

• 순차 구조: 처음부터 순서대로 처리하는 절차
• 선택 구조: 조건식으로 판단해 실행할 처리를 전환하는 절차
• 반복 구조: 조건을 만족하는 동안 같은 처리를 반복하는 절차

알고리즘 기술 방법

• 순서도(Flow Chart)
  • 순서도는 프로그래밍 언어를 사용하지 않고 알고리즘을 도형으로 기술하는 방법으로, 'Flow Chart'라고 하는데 그 이유는 말 그대로 '흐름(Flow)'을 '그림(Chart)'으로 나타냈기 때문이다.
    
    출처
• 프로그래밍 언어
  • 프로그래밍 언어에는 C, Visual Basic, C++, COBOL, Java, PHP, JavaScript, Python 등이 있다. 각 프로그램마다 사용되는 전문 분야가 있으며, 프로그래밍 학습에서 일반적으로 사용되는 언어는 C와 Java이고 웹 프로그래밍 경우 주로 PHP와 JavaScript가 사용된다.

reference

김쏴장
ONnONs
wowrupi