차차로그

좋은 코드의 조건 1. Readble : 읽고 이해할 수 있는가 2. Efficieny : 메모리를 효율적으로 사용하는가 3. Scalable : input의 규모가 커져도 느려지지 않는가 BIG-O는 코드가 Scalable한 코드인지, 알고리즘을 수행할 때 시간이 얼마나 걸리는지를 측정할 때 사용하는 일종의 언어 컴퓨터는 한정된 메모리 공간만을 가지기 때문에 메모리를 효율적으로 관리해야 한다. BIG O의 종류 BIG-O는 input의 증가에 따라서 runtime이 얼마나 빠르게 증가하는지를 측정하는 것이지, 특정 작업이 수행되는데 시간이 얼마나 걸리는지 측정하는 것이 아니다! 1. O(1) : Constant Time 상수시간이라 부르며 input이 얼마가 되었든 runtime이 변하지 않는다. 배열..

탐욕 알고리즘 aka 그리디의 핵심은 선택의 순간 때 가장 최선의 상황만을 선택한다는 것이다 그 상황의 최적해를 구해 최종 해답에 도달하는 것이기 때문에 이 해답이 최적의 답이라는 보장은 할 수가 없다. 단, 어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있다. 이러한 구조를 매트로이드라고 한다. 탐욕 알고리즘 문제를 해결하는 방법 1. 선택 절차 : 현재 상태에서의 최적의 해답을 선택한다. 2. 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사한다. 3. 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차(1단계)로 돌아가 위의 과정을 반복 탐욕 알고리즘로 최적해를 구할 수 있는 문제는 두 가지 조건을 만족해야 한다. 1. 탐욕..

'에라토스테네스의 체'는 소수를 구할 수 있는 알고리즘이다. 에라토스테네스는 고대 그리스의 수학자 이름이고 체는 체에 거른다고 할 때의 그 체다. 이 알고리즘은 주어진 수의 배열에서 2의 배수를 삭제하고, 3의 배수를 삭제하고, 5의 배수를 삭제하고... 이걸 계속 반복해 소수만을 알 수 있게 하는 알고리즘이다. 1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 2. 2는 소수이므로 오른쪽에 2를 쓴다. 3. 자기 자신을 제외한 2의 배수를 모두 지운다. 4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. 5. 자기 자신을 제외한 3의 배수를 모두 지운다. 6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. 7. 자기 자신을 제외한 5의 배수를 모두 지운다. 8. 남아있..