[Algorithm] 알고리즘(Algorithm)이란?

안녕하세요 성조입니다

알고리즘에 대해서 본인이 이해했던 내용을 학습 정리하는 시간을 가지려고 합니다.

---

INDEX

ㆍ 알고리즘(Algorithm)이란?

ㆍ 알고리즘을 기술하는 방법

ㆍ 알고리즘 개발의 정형적 단계

ㆍ 알고리즘의 성능 분석

ㆍ 알고리즘 수행 시간 비교 및 공간 복잡도 표기 방법

---

알고리즘(Algorithm)이란 ?

알고리즘은 특정 문제를 해결하기 위해서 정해진 일련을 절차라고 정의할 수 있습니다. 예를 들면 다음과 같습니다.

 

A라는 문제가 발생했습니다.

위의 그림과 같이 A라는 문제를 해결하기 위해서는 B, C, D를 거쳐서 해결이라는 단어에 도달해야 A라는 문제를 해결했다 볼 수 있습니다.

이런 문제에 대해서 풀이될 때 필요한 계산의 절차 또는 B, C, D에 대한 처리 과정의 순서를 뜻합니다.

 

알고리즘이 가지는 5가지 특성입니다.

입력(input) : 0개 이상의 입력이 존재해야 한다. 출력(output) : 1개 이상의 출력 결과물이 존재해야 한다. 명확성(definiteness)  : 각 단계별 명령어는 헷갈리거나 모호하지 않고 명확해야 한다. 유한성(finiteness) : 특정 수의 한정된 작업이 끝난 이후에는 반드시 종료되어야 한다. 효율성(efficiency) : 각 단계별로 명확하게 실행이 가능하며 그 실행 결과가 검증된 것이어야 한다.

더 많은 예시가 있지만 대표적인 예시로 5가지가 나왔으며, 학습할 때 많은 자료들에 효율성과 유효성이 섞여서 나와있는 것을 확인 했습니다.

 

유효와 효율에 대해서 정의를 명확하게 하고자 국립국어원에 있는 자료와 다른 자료들을 바탕으로 포스팅을 진행했습니다.

출처 : https://www.korean.go.kr/front/onlineQna/onlineQnaView.do?mn_id=&qna_seq=15379&pageIndex=13176

정의가 나온 나무위키, 위키피디아는 효율성의 개념으로는 과정의 우수성을 의미했습니다.

여기서 유효성의 보람이나 효과가 있거나, 법률에 관한 부분은 연관성이 비교적 떨어진다 생각했습니다. 효율성에서 과정의 우수성은 하나의 알고리즘에는 다양한 단계가 명확하게 구분되면서 상세하게 작성돼야 하므로 그 과정이 우수하게 나온 다고 판단하여 조금 더 맞는 단어로 효율성이라 판단하고 효율성을 좋은 알고리즘을 만들기 위한 5가지 규칙 중 하나로 골랐습니다.

 

정리하면 효율성은 input과 output이 명확하게 있으며, 산출이 가능한 것입니다.

유효성은 올바른 목표로 성과를 달성했는지를 확인하는 것입니다. 

즉, 컴퓨터공학에서 처리과정을 나타내는 것은 효율성이 유효성 보다 더 가깝다고 생각했습니다.

 

 

알고리즘을 기술하는 방법

자연 언어 (natural language) : 국가에서 민족별로 쓰이는 언어들로 한글 또는 영어와 같이 의사소통을 위해서 사용하는 방법입니다. 하지만 이 방법은 의사소통이 전달성에서 문제가 생겨 모호한 부분이 발생할 수 있습니다. 하지만 사용되는 단어의 의미를 명확하게 정의된 말을 사용하여 작성하면 알고리즘의 기능을 제대로 할 수 있습니다. 

흐름도 또는 순서도 (flowchart) : 도형과 선을 활용하여 프로세스를 보여주는 방법이다. 이 방법은 국제 표준화 기구 SC7 총회에서 이미 표준안으로 결의됐고 기호가 나눠졌지만 초심자 또는 간단한 로직을 나타내기 좋지만 복잡한 알고리즘의 경우 가독성이 떨어지기 쉬워서 간결하지 못한 경우에는 비교적 좋지 못하다.

가장 많이 사용되는 방법으로는 아래의 두 가지가 있다.

의사 코드(Pseudo-Code) : 프로그램을 작성할 때 모듈들이 작동하는 논리를 표현하기 위한 언어이다.

묘사가 많아지면 자연어 기술과 비슷해질 수 있다.

프로그래밍 언어 : C, Java, Python ...등등

 

 

알고리즘 개발의 정형적 단계

해결하고자 하는 문제를 정의한다. -> 어떤 방식으로 접근할 것인지 접근 모델을 정의한다. -> 문제점들을 명세할 명세서를 작성한다. -> 해결하기 위한 로직의 단계를 설계한다. ->  알고리즘이 실제로 사용할 수 있는 것인지 복잡도 등을 분석하고 파악한다. -> 실제 테스트를 위해서 알고리즘 코드로 구현한다. -> 의도한 것이 맞는지 테스트를 진행한다. -> 제대로 실행됐다면 문서화하고 아닌 경우에는 다시 시작한다.

 

 

알고리즘의 성능 분석

알고리즘의 성능 분석을 하는 이유

요즘에는 데이터는 일시적으로 저장했다 삭제하는 것이 아닌 대부분 누적하여 관리합니다. 그러나 최근 컴퓨터 하드웨어의 발전에 비해서 수집되는 데이터는 IOT 서비스 등이 생겨나면서 언제 어디서나 쉽게 인터넷을 접속할 수 있는 것 처럼 언제 어디서나 데이터가 초, 분, 시, 일, 주 단위로 데이터가 쌓이기 시작했습니다.

이렇게 쌓이는 데이터는 정보로 만들기 위해서 처리 과정을 진행해야 하는데 처리 내용이 많아지면서 계산해야 하는 분량이 많아지면서 이전보다 더 효율적인 알고리즘을 고민하고 구현하면서 성능 평가에 힘을 쓰게 됐습니다.

 

알고리즘 수행시간 측정방법

실행 시간이 얼마나 들어가는지와 메모리의 사용량을 구분하여 성능을 평가하는데 컴퓨터 마다 언제든지 실행 지표는 주관적으로 바뀔 수 있기 때문에 객관적인 성능 지표를 갖기 위해서 시간 복잡도로 정의하기로 했습니다.

여기서 주관적 입장으로 효율적인 알고리즘을 정리하면 다음과 같습니다.

"알고리즘이 시작하여 결과가 나올 때까지의 수행 시간이 짧으면서 메모리와 같은 컴퓨터 자원을 덜 쓰이는 알고리즘이다."

 

시간 복잡도 함수의 종류

시간 복잡도(time complexity) : 알고리즘의 수행 시간 복잡도를 분석하는 것은 시작부터 종료까지의 경과 시간을 나타내는 것이 시간이 얼마나 걸리는지 확인할 수 있는 방법이다. 하지만 컴퓨터마다 사용되는 CPU나 인터넷 환경 등 컴퓨팅 자원이 모두 다르기 때문에 이런 시간 복잡도는 연산의 횟수로 측정한다.

 

공간 복잡도(space complexity) : 알고리즘 실행에 필요로 하는 메모리의 크기 즉, 공간 복자도는 메모리 공간의 사용량이 된다.

 

보통 알고리즘을 볼 때는 공간 복잡도에 비해서 시간 복잡도를 더 중요하게 봅니다.

이유로는 공간은 메모리 자원으로 테스트를 하는 것인데 현재 하드웨어 기술에서는 메모리는 충분한 만큼 성능이 올라왔기 때문에 연산 횟수에서 더 효율성을 높이는 것이 주가 되면서 공간 복잡도에 비해서 시간 복잡도가 비교적 더 중요하게 된 것입니다.

 

 

 

알고리즘 수행 시간 비교 및 표기 방법

알고리즘 크기 n에 관한 점근적 표기법

크기	시간의 형태	설명
O(1)	상수형	시작점이 널인지 검사하는 것 정도가 1이다
O(log n)	로그형	이진 탐색으로 사용되는 알고리즘이다.
O(n)	선형	n에 비례하는 시간 내에 수행되는 알고리즘으로 기수 정렬이 예로 있다.
O(n log n)	선형-로그형	정렬 알고리즘 n에 대략 비례할 수 있는 시간이 걸리는 알고리즘이다.
O(n^2)	제곱형	최장 공통 부분 수열에 쓰이고 n^2(n의 2제곱)에 비례하는 시간 이내에 수행되는 알고리즘이다.
O(n^3)	제곱형	행렬 곱셈에 사용되며 n의 3제곱의 시간 내에 사용되는 알고리즘이다.
O(a^n)	지수형	a의 n제곱 시간 이내에 수행되는 알고리즘이며, 충족 가능성 문제를 해결할 때 사용된다.
O(n!)	팩토리얼형	배열의 모든 순열을 검사할 때 사용되는 알고리즘이며, 대부분의 알고리즘은 표기법의 정의상 값이 큰 알고리즘은 그 위의 복잡도를 포함하므로 대부분의 알고리즘은 O(n!)의 수행 시간을 갖게 된다.

 

 

알고리즘 수행시간 순서

왼쪽에서 오른쪽으로 시간이 많이 걸린다.

즉, 좌측으로 갈 수 록 빠른 알고리즘이며, 우측으로 갈 수 록 시간이 오래 걸립니다.

 

 

공간 복잡도 표기 방법

	빅오메가 Ω (최선의 경우 best case)	빅세타 θ (평균적인 average case)	빅오 O (최악의 경우 worst case)
표기 방법	Big(Ω)	Big(θ)	Big(O)
설명	최선의 경우 알고리즘 평균 중에 가장 빠른 경우에 대한 값을 갖고 오는 경우입다.	최악 최선의 평균 값으로 알고리즘의 중간 값을 갖고 오는 경우입니다.	알고리즘이 가장 오래걸린 최악의 경우의 측정 값을 갖고 오는 경우입니다.

.

 

---

잘못된 학습의 내용이나 기타 모든 문제점에 대해서는 댓글 부탁드리겠습니다!

부족한 포스팅 읽어주셔서 감사합니다.

다음 포스팅 때 뵙겠습니다.

 

 

- 참고 자료 주소 -

https://www.korean.go.kr/front/onlineQna/onlineQnaView.do?mn_id=&qna_seq=15379&pageIndex=13176 

국립국어원

https://namu.wiki/w/%ED%9A%A8%EC%9C%A8%EC%84%B1

https://en.wikipedia.org/wiki/Efficiency

Efficiency - Wikipedia

http://www.economyf.com/m/view.asp?idx=7210 

효율성과 유효성 그리고 삶의 태도

https://ko.wikipedia.org/wiki/%EC%88%9C%EC%84%9C%EB%8F%84

순서도 - 위키백과, 우리 모두의 백과사전