비밀공부방

복잡도(Complexity) 알고리증 성능을 나타내는 척도. 시간복잡도 : 입력에대한 알고리즘의 수행시간 분석 공간복잡도 : 입력에대한 알고리즘의 메모리 사용량 분석 시간 복잡도가 높다는것은 알고리즘의 수행시간이 높은것을 나타낸다. 시간 복잡도가 낮다는것은 알고리즘의 수행시간이 낮은것을 나타낸다. 따라서 같은 기능을 수행하는 알고리즘에 대해서는 시간복잡도가 낮을수록 품질이 좋다. 시간복잡도의 표기법 빅오 표기법(Big-O Notation) 가장 빠르게 증가하는 항만을 고려하는 표기법 : 함수의 상한만을 나타낸다. 예를 들어 연산횟수가 3N^3 + 15^2 +15520 인 알고리즘이 있다고 했을경우 빅오표기법으로는 O(N^3)으로 표기됩니다. N의 값이 아주 큰 수라고했을경우 나머지 연산횟수는 비교적 작은..

그리디 알고리즘이란 ? 주어진 상황에서 가장 좋은것(큰 값)을 구하는 알고리즘이다. 단순히 가장 좋은것을 선택하는 행위를 반복하여도 최적의 값이 추출되는지 검증이 필요하다. 1. 해결 아이디어 제시 거스름돈으로 사용할 화폐단위를 정의한다. 가장 적은 개수를 구하는 문제이기에 화폐단위중 가장 큰 값으로 거슬러 줄수 있는 개수를 구한다. 그다음으로 적은 금액으로 거슬러 줄 수 있는 개수를 구한다. 해당 작업을 반복한다. 2. 정당성 분석 해당 문제는 거슬러 주어야할 최소 동전 개수를 구하는 문제 이기에, 화폐의 가장큰 단위로 거슬러 준다면 , 거스름돈의 개수를 최소화할 수 있다. 예 : 거스름돈 1,000 일 경우 500 * 2 100 * 10 50 * 20 10 * 100 이기에 가장큰 화폐단위인 500원..