Table of Contents
목차
알고리즘 Algorithm
- 사전적 의미: 어떤 문제를 해결하는 한 방법의 상세한 특징을 기술하는 것
- 컴퓨터로 문제를 풀기 위한 단계적인 절차
- 특정한 일을 수행하는 명령어들의 유한 집합
- 하나의 문제에 여러 방법의 알고리즘이 가능하며, 가장 효율적인 알고리즘을 찾는 것이 중요
- 순서도, 유사코드, 프로그래밍 언어 등 여러 방법으로 표현
- 누구나 이해할 수 있게 명확하게 기술하는게 중요
조건, 특성
- 입력(input): 문제를 풀기 위한 입력이 있어야 함
- 외부에서 제공되는 자료가 0개 이상 존재
- 출력(output) : 문제를 해결했을 때 답이 나와야 함
- 적어도 2개 이상의 서로 다른 결과를 내어야 한다.(즉 모든 입력에 하나의 출력이 나오면 안됨)
- 명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다!
- 유한성(종결성)(finiteness) : 유한 번의 명령이 수행된 후에는 끝나야 함
- 유한 번의 명령어를 수행 후(유한 시간 내)에 종료한다.
- 정확성(correctness) : 주어진 문제를 정확하게 해결해야 함
- 확정성(definiteness) : 각 단계가 실행된 후에는 결과가 확정됨
- 일반성(generality) : 같은 유형의 문제에 문제에 모두 적용됨
- 효율성(effectiveness) : 정확하면서도 효율적이어야 함
- 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다.
표현 방법
프로그래밍 언어
- 평소 하던대로 코드 짜는 것
자연어
- 그냥 한국어, 영어로 말하듯이 풀어놓는 것
흐름도(flow chart)
- = 순서도
- 문제 처리 순서를 단계화
- 상호간의 관계를 표준 기호를 사용하여 입력, 처리, 결정, 출력 등의 박스와 연결선으로 나타낸 도표
수도코드(Pseudo-code)
- = 유사코드 = 의사코드
- 알고리즘의 고수준 기술 방법
- 자연어보다는 더 구조적인 표현 방법
- 프로그래밍 언어보다는 덜 구체적
-
알고리즘 기술에 가장 많이 사용
- 알고리즘을 프로그래밍 언어와 유사한 형태로 풀어 놓은 것
정확한 문법적 측면은 배제하고 사고의 흐름을 간결하고 효과적으로 전달하는 표현 방법- 유사코드는 알고리즘을 개략적으로 표현하는데 에 쓰임
알고리즘 성능 분석
수행 시간 측정
- 두개의 알고리즘의 실제 수행 시간을 측정
- 실제로 작접 구현하여 비교
- 동일한 환경 (H/W or S/W)에서 측정 필요
복잡도 분석
직접 구현하지 않고 수행시간을 분석- 알고리즘이 수행하는 연산의 횟수를 측정하여 비교
- 입력 개수 n에 대한 함수의 형태로 표현
- 시간 복잡도 분석: 수행시간 분석
- 공간 복잡도 분석: 수행시 필요한 메모리 공간 분석
Big-O notation
- Big-O 표기법 : 연산 횟수를 대략적으로 표시함.(최악의 경우(상한))
more learn
데이터 수가 많은 경우 차수가 큰 항이 성능에 가장 큰 영향을 미치기 때문에 다른 항들은 무시한다.
(ex) - 알고리즘 1 → 전체 연산수 : 2 → O(1)
- 알고리즘 2 → 전체 연산수 : 2n + 1 → O(n)
- 알고리즘 3 → 전체 연산수 : 2n2 + 1 → O(n2)
(종류)
• O(1) : 상수형
• O(logn) : 로그형
• O(n) : 선형
• O(nlogn) : 로그선형(bst)
• O(\(n^2\)) : 2차형
• O(\(n^3\)) : 3차형
• O(\(n^k\)) : k차형
• O(\(2^n\)) : 지수형
• O(n!) : 팩토리얼형
-> 데이터에 따라서 뭐가 더 좋은지 바뀔 수 있음
