gyeong3un2

'당장 좋은 것만을 선택'하는 그리디 문제에서 '가장 큰 순서대로' 혹은 '가장 작은 순서대로'와 같은 기준을 제시한다면, 정렬 알고리즘을 사용한다. 이때, 그리디 알고리즘은 자주 정렬 알고리즘과 짝을 이뤄 출제된다. 그리디의 대표적인 문제로는 '거스름돈 문제'이다. 거스름돈 예제에서의 시간 복잡도는 O(K)로 이때 K는 화폐의 종류이다. 즉, 이 알고리즘의 시간 복잡도는 화폐의 종류에 영향을 받는다. 실전 문제 1. 큰 수의 법칙 다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없음 ex) 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때, M이 8이고, K가 3이라고 가정하자..

복잡도, Complexity 복잡도는 알고리즘의 성능을 나타내는 척도이다. 복잡도는 크게 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나눌 수 있다. 알고리즘 문제를 풀때, 단순히 '복잡도'라고 하면 보통은 시간 복잡도를 의미한다. 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미한다. 이를 측정함으로써 알고리즘을 위해 필요한 연산의 횟수를 계산할 수 있다. 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의마한다. 이를 측정함으로써 알고리즘을 위해 필요한 메모리의 양을 계산할 수 있다. 효율적인 알고리즘을 사용한다고 했을 때 보통 시간 복잡도와 공간 복잡도는 일종의 거래 관계(Trade..