<알고리즘>
알고리즘은 문제 해결 과정을 묘사하는 것으로 어떤 일을 수행하는 일련의 명령어의 집합이라 할 수 있으며 모호하지 않고 이해하기 쉽게 명확해야한다.
<알고리즘의 특성>
알고리즘을 작성하기 위해서는 문제를 풀기 위한 입력이 반드시 필요하며 그 결과인 출력이 존재해야하며, 명령이 수행된 후에는 반드시 종료되어야 하는 유한성과 정확한 출력값을 만들어내야 하는 정확성, 같은 문제에는 모두 적용 가능한 일반성성이 있어야 한다.
<의사코드>
프로그램 명령문 형식을 취하고 각 명령을 사람이 이해하기 쉽게 적당한 뜻을 가진 단어로 나타낸 것이다.
<알고리즘 개념>
알고리즘이란 ? 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어 내는 과정을 기술한것.
알고리즘의 예
1. 요리 -> 레시피가 요리의 질을 좌우하는 결정적 요소
2. 게임 -> 게임에서 목표지점까지 도달하기 위한 과정을 차례로 표현, 출발에서 목표까지의 효율적인 접근 방법과 과정
3. 아침부터 하루 일을 구상하고 스케줄을 짜며 계획하는 일
4. 전자레인지 등 전자제품의 사용 설명서에 나타난 사용 방법
5. 바둑이나 게임을 잘하기 위한 방법론
6. 어떤 목적지로 이동 할 때 효율적인 교통 수단 환승 방법
문제 해결을 위한 알고리즘
두뇌 또는 컴퓨터로 문제를 해결함에 관계없이 적용
문제 복잡성에 따라 컴퓨터 프로그램을 통해 문제를 해결
알고리즘은 컴퓨터 프로그램을 작성하는 바탕
바람직한 알고리즘
1. 명확해야함
- 이해하기 쉽고 가능하면 간명하도록 해야 함
- 지나친 기호적 표현은 오히려 명확성을 떨어뜨림
- 명확성을 해치지 않으면 일반 언어의 사용도 무방
2. 효율적이어야함
- 같은 문제를 해결하는 알고리즘들의 수행 시간이 수백만 배 이상 차이 날 수 있음.
알고리즘 공부의 목적
1. 알고리즘은 문제 해결 절차를 체계적으로 기술한 것
2. 알고리즘 공부의 목적은 특정한 문제를 위한 알고리즘의 습득, 체계적으로 생각하는 훈련, 지적 추상화의 레벨 상승을 위함
3. 같은 문제에서도 효율이 아주 큰 차이가 나는 다양한 알고리즘이 존재함.
4. 이들에 대해 학습하는 과정에서 얻을 수 있는 여러가지 기법과 생각하는 방법도 중요
알고리즘 분석의 필요성
1. 바람직한 알고리즘은 명확하고 효율적이어야함.
2. 알고리즘을 설계하고 나면 이 알고리즘이 자원을 얼마나 소모하는지 분석해야 함.
3. 자원은 소요 시간, 메모리, 통신 대역 등.
4. 자원의 가장 중심 대상은 소요시간
5. 시간의 분석은 최악의 겨웅와 평균적인 경웨 대한 분석이 대표적
-> 시간 분석을 하면 알고리즘이 어느 정도의 입력에서 어느 정도의 시간이 필요한지 미리 짐작 가능하며 주어진 시간에 요구하는 작업이 완료 가능한지를 알 수 있음.
알고리즘의 수행시간
1. 알고리즘의 수행 시간은 입력의 크기에 대해 시간이 어떤 비율로 소요되는지 표현됨.
2. 입력의 크기
- 정렬의 경우 정렬하고자 하는 개체의 수
- 도시 간의 거리를 구하는 경우 계산에 관여되는 도시의 총 수와 도시 간 간선(도로)의 총 수
- 계승을 구하는 경우에는 계승치를 구하고자 하는 자연수의 크기
3. 입력값 n에 따른 알고리즘 수행시간
4. 알고리즘의 수행시간을 좌우하는 기준
- for 루프의 반복횟수
- 특정한 행이 수행되는 횟수
- 함수의 호출 횟수
재귀적(Recursive) 알고리즘
1. 재귀 = 자기호출
2. 재귀적 사고는 해법을 알고 그것을 반복으로 적용시킴
3. 어떤 문제 안에 크기만 다를 뿐 성격이 똑같은 작은 문제들이 포함되어 있는 것.
4. 병렬화 개념은 하나의 일을 나누어 동시에 병렬로 처리
5. 팩토리얼, 수열의 점화식, 피보나치, 병합 정렬 등
알고리즘의 효율성 분석
알고리즘의 분석
1. 알고리즘의 자원 사용량을 분석
2. 자원이란 실행 시간, 메모리, 저장장치, 통신 등
3. 여기서는 실행 시간의 분석에 대해서 다룸.
알고리즘의 복잡도
1. 여러 알고리즘 중 처리 시간이나 차지하는 메모리 용량이 작은 알고리즘이 프로그램 효율성도 높음
2. 알고리즘을 어떤 식으로 작성하느냔에 따라 실행되는 시간과 공간이 다르며 이것을 알고리즘의 복잡도라고 함.
3. 알고리즘의 성능 분석
- 성능 측정 : 실제 구현 필요, 구체적으로 실행 시켜 시간을 확인 * 구현해야 하므로 잘 안씀.
- 성능 분석 : 구현 불필요
- 시간복잡도 : 입력 개수(n)에 따른 실행 횟수
- 공간 복잡도
4. 복잡도
- 시간 복잡도 : 알고리즘이 수행되는 시간
- 알고리즘이 수행될 때 필요한 메모리 공간
* 일반적으로 알고리즘들을 비교할 때에는 시간 복잡도가 주로 사용됨
5. 알고리즘의 복잡도는 처리해야 하는 데이터의 양이나 표현 방법, 컴파일러 등에 따라 달라지므로 성능 측정이 어려움
6. 입력 데이터가 많을수록 실행 속도나 성능이 저하되므로 입력 데이터가 무한히 많아질 때의 알고리즘의 성능을 주로 평가
시간 복잡도
1. 실행 시간은 실행환경에 따라 달라짐 (하드웨어, 운영체제, 언어, 컴파일러 등)
2. 실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트
3. 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현
4. 데이터의 크기가 같더라도 실제 데이터에 따라서 달라짐
5. 시간 복잡도는 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현
예) 10장의 숫자 카드 중에서 최대 숫자 찾기
-> 순차탐색으로 찾는 경우 숫자 비교가 기본적인 연산이고, 총 비교 횟수는 9임
-> 시간복잡도 = n-1
6. 알고리즘의 복잡도를 표현하는 데는 다음과 같은 분석 방법들이 있음
- 최악의 경우 시간 분석(Worst Case Analysis)
- 평균의 경우 분석(Average Case Analysis)
- 최선의 경우 분석(Best Case Analysis)
점근적 표기
점근적 분석
1. 입력크기가 작은 문제는 알고리즘의 효율성이 중요하지 않지만 입력 크기가 충분히 큰 문제는 비효율적인 알고리즘은 치명적임
2. 입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법
3. 유일한 분석법도 아니고 가장 좋은 분석법도 아님
- 다만 상대적으로 가장 간단함
- 알고리즘의 실행 환경에 비의존적임
- 그래서 가장 광범위하게 사용됨