[알고리즘] 알고리즘의 설계와 분석 - 시간 복잡도와 점근성능 1. 알고리즘 설계 기법 주어진 문제, 속성, 조건 등에 따라 매우 다양한 알고리즘이 존재할 수 있다. 따라서 일반적이고 범용적인 알고리즘 설계 기법은 존재하지 않지만 그 중 대표적인 설계 기법 세 가지를 꼽으면 다음과 같다. 분할 정복 방법(Divide-and-Conquer) 동적 프로그래밍 방법(Dynamic Programming) 욕심쟁이 방법(Greedy) 따라서 알고리즘을 공부하며 위 세 가지 설계 기법은 꼭 알아둬야 할것이다. 2. 알고리즘의 효율성 분석 알고리즘의 효율성 분석은 알고리즘 수행에 필요한 메모리 양과 수행 시간을 계산하는 것이다. 메모리 양 → 공간 복잡도(Space Complexity) = 정적 공간 + 동적 공간 ..

[알고리즘] 알고리즘의 개념과 기본 자료구조 1. 알고리즘의 정의와 조건 1) 알고리즘의 정의 주어진 문제를 풀기 위한 명령어들의 단계적 나열 2) 알고리즘의 조건 입력 : 0개 이상의 외부 입력 출력 : 1개 이상의 출력 명확성 : 각 명령은 모호하지 않고 명확해야 함 유한성 : 한정된 수의 단계를 거쳐 반드시 종료됨 유효성 : 모든 명령은 컴퓨터에서 수행 가능해야 함 알고리즘의 조건을 합쳐서 정의하자면 알고리즘이란 주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 컴퓨터가 수행 가능한 일련의 유한개의 명령들을 순서적으로 구성한 것이다. 2. 알고리즘 생성 단계 3. 알고리즘의 표현/기술 방법 알고리즘은 크게 일상 언어, 의사 코드(Pseudo code), 순서도의 세 가지 방법으로 표현할 수 있..

[알고리즘] 알고리즘 수행시간 유형 N 알고리즘 분석의 결과는 입력되는 자료의 수 N에 대하여 수행 시간을 함수 관계로 표현한 것이다. 1. 1 - 입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘이다. 프로그램에서 대부분의 명령들은 한 번만 실행되거나, 단지 몇 번만 실행이 된다. 전체적인 프로그램이 이런 경우라면 실행 시간은 상수가 된다. 이 유형은 알고리즘의 설계시 도전해 볼 만한 것이다. 2. log N - 만약 입력 자료의 수에 따라 실행 시간이 log N의 관계를 만족한다면 N이 증가함에 따라 실행 시간이 조금씩 늘어난다. 이 유형은 주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤 때 나타나는 유형이다. log의 성질상 밑(base)의 값에 따라 결과는 달라지지만 그렇게 크..