[알고리즘] 분할정복 방법 -알고리즘의 대표적인 설계 기법으로는 욕심쟁이 방법, 분할정복 방법, 동적 프로그래밍 방법이 있다. 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개이면 오일러 경로가 존재한다. 만약 차수가 홀수인 정점이..