알기쉬운알고리즘

[컴퓨터알고리즘] Ch 3. 분할 정복 알고리즘(1)

PDF 정리본 (출력 가능) 분할 정복 알고리즘 - 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘 : 분할한 입력에 대해 동일한 알고리즘을 적용하여 해를 계산 : 이들의 해를 취합하여 원래 문제의 해를 얻음 - 부분 문제와 부분 해 : 분할된 입력에 대한 문제를 부분 문제라고 함 : 부분 문제의 해를 부분 해라고 함 : 부분 문제는 더 이상 분할할 수 없을 때까지 분할함. - 대부분의 분할 정복 알고리즘은 문제의 입력을 단순히 분할만 해서는 해를 구할 수 없고, 분할된 부분 문제들을 정복해야 함. Q. 입력 크기가 n일 때 총 몇 번 분할하여야 더 이상 분할할 수 없는 크기인 1이 될까? A. 답을 계산하기 위해 분할한 총 횟수를 k라고 하면 n/2k = 1일 때 더 이상 분할할 ..

[컴퓨터알고리즘] Ch 2. 알고리즘을 배우기 위한 준비

PDF 정리본 (출력 가능) 2.1 알고리즘이란 - 알고리즘이란 : 문제를 해결하는 단계적 절차 또는 방법 : 컴퓨터를 이용해 해결할 수 있어야 함. : 입력이 주어지고, 수행 결과인 해(답)을 출력. - 알고리즘의 일반적 특성 정확성 주어진 입력에 대해 올바른 해를 주어야 함. (랜덤 알고리즘은 예외) 수행성 알고리즘의 각 단계는 컴퓨터에서 수행 가능해야 함. 유한성 알고리즘은 유한 시간 내에 종료되어야 함. 효율성 알고리즘은 효율적일수록 그 가치가 높아짐. 일반성 같은 type의 문제에 항상 해당 알고리즘을 적용할 수 있어야 함. 확정성 알고리즘은 동일한 입력에 대해 동일한 출력을 가져야 함. 2.2 최초의 알고리즘 - 유클리드의 최대공약수 알고리즘 : 기원전 300년경에 만들어진 가장 오래된 알고리..

[컴퓨터알고리즘] Ch 1. 알고리즘의 첫걸음

PDF 정리본 (출력 가능) 알고리즘 9세기경 페르시아 수학자인 알코리즈미의 이름으로부터 유래 최초의 알고리즘: BC 300년경 유클리드의 GCD 알고리즘 문제를 해결하기 위한 단계적인 절차를 의미 단계적인 절차를 따라하면 주어진 문제의 해를 찾음(요리법과 유사) 효율적인 알고리즘 고안이 중요: 주어진 문제에 대해 여러 종류의 알고리즘이 있을 수 있으나, 항상 보다 효율적인 알고리즘을 고안하는 것이 매우 중요 1.1 최대 숫자 찾기 Q. 카드놀이 중에서 아주 간단한 가장 큰 숫자 찾기를 생각해보자. 카드 10장이 바닥에 펼쳐져 있다.(45, 60, 90, 75, 20, 55, 85, 35, 10, 25) A. 가장 큰 숫자가 적힌 카드를 찾는 한 가지 방법은 카드의 숫자를 하나씩 비교하면서 본 숫자 중에..