[알고리즘] 점근성능 1. 점근성능(Asymptotic Performance)-입력 크기에 따라 알고리즘의 성능도 변하기 때문에, 입력 크기 n이 충분히 큰 상태를 전제로 성능을 분석하는 것이 바람직하다.-입력크기 n이 무한히 커짐에 따라 결정되는 성능을 점근 성능이라고 부른다.-알고리즘 간의 우열을 평가할 때는 입력 크기 n의 차수만을 표기한다.-수행시간은 최고 차수를 가진 항에 의해 가장 큰 영향을 받아 결정된다. 따라서 최고차항만을 계수 없이 단순화한 형태로 성능을 표현한다. -> 알고리즘간의 우열을 따질 때 유용하다.-> 점근성능 표기법으로는 O(Big-Oh 빅-오)표기가 대표적이다.  2. 점근성능 표기법-점근성능을 표기하는 방법으로는 주로 O(Big-Oh), Ω(Big-Omega), Θ(Big..

[알고리즘] 알고리즘 분석  알고리즘을 설계한 뒤에는 알고리즘의 정확도와 효율성을 분석해야 한다. 알고리즘 분석은 크게 정확성 분석과 효율성 분석으로 나뉜다. 1. 정확성 분석-정확한 알고리즘은 유효한 입력이 주어졌을 때, 유한 시간 내에 정확한 결과를 생성해야 함-정확성 분석은 수학적 기법을 사용해 알고리즘이 예상대로 동작하는지를 증명하는 과정임  2. 효율성 분석-효율성 분석은 알고리즘을 수행하는 데 얼마나 많은 컴퓨터 자원이 필요한지를 평가하는 과정임-알고리즘을 수행하는 데 드는 시간적/공간적 비용을 분석하게 되며, 이를 각각 시간 복잡도/공간 복잡도라고 부른다. (1) 공간 복잡도(Space complexity)-알고리즘 수행에 필요한 총 메모리 양-컴파일 과정에서 결정되는 정적 공간/실행 과정에..

[알고리즘] 동적 프로그래밍 방법 -알고리즘의 대표적인 설계 기법으로는 욕심쟁이 방법, 분할정복 방법, 동적 프로그래밍 방법이 있다.  1. 동적 프로그래밍 방법(Dynamic Programming)-동적 프로그래밍 방법은 입력의 크기가 가장 작은 부분 문제부터 해를 구해 저장해두고, 이를 이용해서 입력 크기가 보다 큰 문제의 해를 점진적으로 만드는 상향식 접근 방법이다.-작은 문제들은 서로 독립일 필요가 없다.-따라서 한 번 사용한 작은 문제의 해가 다음에 또 사용될 수도 있다.-욕심쟁이 방법과 마찬가지로 최솟값/최댓값을 찾는 최적화 문제에 주로 사용된다. -> 플로이드 알고리즘 역시 동적 프로그래밍이 적용된 알고리즘!

[알고리즘] 분할정복 방법 -알고리즘의 대표적인 설계 기법으로는 욕심쟁이 방법, 분할정복 방법, 동적 프로그래밍 방법이 있다. 1. 분할 정복 방법(Divide-and-Conquer)-분할 정복 방법은 순환적으로 문제를 푸는 하향식 접근 방법이다.-주어진 문제의 입력을 더 나눌 수 없을 때까지 2개 이상의 작은 문제로 순환적 분할하고, 이들을 각각 해결한 뒤, 이들의 해를 결합해 문제의 답을 구하는 방식이다. *분할 정복 방법의 단계(1) 분할(Divide): 주어진 문제의 입력을 여러개의 작은 문제로 분할함(2) 정복(Conquer): 작은 문제들을 순환적으로 분할함. 더이상 나눌 수 없다면 문제를 각각 푼다(3) 결합(Combine): 여러개의 해들을 결합해 문제의 해를 구한다. -분할 정복 방법의 ..

[알고리즘] 욕심쟁이 방법 -알고리즘의 대표적인 설계 기법으로는 욕심쟁이 방법, 분할정복 방법, 동적 프로그래밍 방법이 있다. 1. 욕심쟁이 방법(Greedy Algorithm)-탐욕 알고리즘, 그리디 알고리즘이라고도 불린다.-욕심쟁이 방법이란 일련의 선택 과정을 통해 해를 찾는데, 전후 단계의 선택과정과 관계 없이 각 단계마다 정해진기준에 따라 가장 최선이라고 여겨지는 국부적인 최적해를 찾아나가면 결과적으로 전체적인 최적해를 구할 수 있다는 전략을 취하는 방식이다.-어떤 문제에 욕심쟁이 방법을 적용할 수 있다면, 최적해를 보장하는 효율적인 알고리즘을 가장 간단히 만들 수 있는 방식이다.-가능한 여러 해 중 최솟값/최대값을 찾는 최적해 문제에 주로 사용된다.-ex: 거스름돈 문제, 배당 문제와 같은 비교..

[알고리즘] 알고리즘 설계 1. 알고리즘의 설계 방식-알고리즘은 일련의 과정을 거쳐 생성된다.-주어진 문제의 입출력 조건/처리 조건등을 고려해 문제 분석 -> 이를 바탕으로 알고리즘 설계 -> 적절한 방식으로 표현 및 기술-알고리즘 분야에서는 문제를 푸는 방법과 절차 뿐만이 아니라, 그 방식의 정확성/효율성을 분석하는 과정도 함께 이루어진다.  2. 최솟값 찾기 알고리즘-예를 들어, 아래의 두 방식 중에서 어떤 것이 더욱 효율적인 방식인지 찾아내야 한다고 치자. 아래의 사진은 여러 개의 숫자들 중에서 가장 작은 최솟값을 찾아내는 알고리즘이다. 아래의 두 가지 방법 외에도 여러 방법들이 존재한다.-이렇게 동일한 문제에 대해서도 여러 알고리즘이 존재할 때에는, 적절한 알고리즘을 선택해야 한다. (효율성)  ..

[알고리즘] 알고리즘의 개념  1. 알고리즘의 개념-컴퓨터 과학은 컴퓨터를 활용해 주어진 문제를 해결하기 위한 학문이다.-알고리즘(Algorithm)은 주어진 문제를 해결하기 위한 일련의 단계적인 처리 과정 (ex: 음식의 조리법)-알고리즘은 다양한 분야에서 사용되지만, 특히 컴퓨터를 활용해 문제를 해결하기 위한 분야라고 할 수 있다.  2. 대표적인 알고리즘(1) 퀘닉스버그 다리 문제 (오일러 경로 문제 Eulerian Path)-그래프의 모든 간선을 오직 한 번만 지나가는 경로를 찾는 문제를 '오일러 경로 문제'라고 부른다. 이는 퀘닉스버그 다리 문제에서 유래되었다.-오일러 경로 문제 해결 알고리즘: 각 정점의 차수가 홀수인 정점이 없거나, 2개이면 오일러 경로가 존재한다. 만약 차수가 홀수인 정점이..