루피

그리디 알고리즘이란? 그리디 알고리즘은 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 결과를 도출하는 기법이다. 그리디 알고리즘은 지금 당장의 상황만을 고려하면 되기에 편리하다. 하지만 매 선택의 순간에서의 최적이 종합적 측면에서의 최적을 보장하지는 않기에 주의를 해야한다. 또한 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장하지 못하는 경우가 많다. 따라서 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토가 필요하다. 편의점에서 손님이 물건을 사고 값을 지불하였을 때 N원의 돈을 거슬러 줘야한다. 그럼 이 N을 거슬러 줄 때 사용할 수 있는 동전의 최소 개수는 몇 개일까? (N은 10의 배수이며 동전은 500원, 100원, 50원, 10원짜리이다.) >> 최적의 ..

복잡도(Complexity) 알고리즘의 성능을 어떻게 평가할 수 있을까? 흔히 우리는 복잡도(Complexity)를 이용하여 알고리즘을 평가할 수 있다. 이 때 복잡도는 시간 복잡도와 공간 복잡도로 구성된다. 시간 복잡도: 알고리즘의 수행 시간 분석 공간 복잡도: 알고리즘의 메모리 사용량 분석 같은 기능을 수행하는 알고리즘이 있다면, 복잡도가 낮을숙록 좋은 알고리즘이라고 할 수 있다. (기업의 코딩 테스트에서도 요구사항(복잡도)를 고려해야 불미스러운 사고를 예방할 수 있다...) 빅오 표기법(Big-O Notation) 그렇다면 복잡도를 어떻게 구체적으로 표기할 수 있을까? 그 방법 중 하나는 바로 빅오 표기법(Big-O Notation)이다. 빅오 표기법은 가장 빠르게 증가하는 항만을 고려하는 표기법이..