알고리즘

그리디(Greedy)=탐욕법 알고리즘 [이코테-나동빈]

그리디(Greedy) = 탐욕법 알고리즘 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법 *매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향은 고려하지 않음 알고리즘 테스트에서는 창의력, 문제를 풀기위한 아이디어를 떠올리면 그리디 알고리즘은 해결할 수 있다! 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시할 수 있으니 정렬알고리즘과 같이 사용하는 경우가 많다. 거스름돈 문제 카운터에 거스름돈으로 사용할 500원, 100원, 50원, 10원이 무한히 존재할 때 거스름돈으로 N원을 줘야하는데 이때 거슬러 줘야할 동전의 최소 개수를 구하는 경우 단 N은 항상 10의 배수이다. #그리디 알고리즘 #거스름돈 대표적 문제 n = int(input()) coun..

시간복잡도, 공간복잡도 [이코테-나동빈]

복잡도 : 일반적으로 알고리즘의 성능을 나타내는 척도 - 시간 복잡도(Time Complexity) : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 의미 - 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 의미 *복잡도가 낮을 수록 좋은 알고리즘 *시간복잡도와 공간복잡도는 Trade-Off 관계 - 메모리를 많이 사용하는 대신 시간을 줄일 수 있고, 메모리를 적게 사용하는 대신 시간이 늘어날 수 있다. 시간복잡도(Time Complexity) 일반적(알고리즘 문제시)으로 시간복잡도 == 복잡도를 의미한다. *시간복잡도가 중요한 이유는 알고리즘 테스트시에 제한시간을 넘겨 시간초과(Time Limit Exceeded)로 오답이 될 수있음 빅오(Big-O..