프로그래밍/알고리즘
-
[알고리즘] 탐욕법 알고리즘(Greedy Algorithm)프로그래밍/알고리즘 2024. 9. 17. 22:01
탐욕법 알고리즘(Greedy Algorithm)은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법으로 최적화 문제를 해결하기 위해 사용하는 알고리즘 방법 중 하나이다. 예시) 노드의 합이 가장 높은 방법을 생각해보자. 이 처럼 탐욕법 알고리즘은 매 단계에서 현재 상황에서 가장 최선의 선택을 하는 방식으로 최종 해답을 찾지만 항상 최적의 값을 보장하는것은 아니다. 이러한 탐욕법 알고리즘은 모든 상황에서 보다는 탐욕 선택 속성(greedy choice property), 최적 부분 구조(optimal substructure) 특성을 가지는 문제들을 해결하는 데 강점이 있다. - 탐욕 선택 속성(greedy choice property) 이전 단..
-
[알고리즘] 시간 복잡도(Time complexity)프로그래밍/알고리즘 2024. 9. 9. 00:19
시간복잡도(Time complexity)는 문제를 해결하는데 걸리는 수행 시간과 입력 데이터의 함수 관계를 분석하는 개념으로, 입력 데이터의 크기가 커질 때, 알고리즘이 얼마나 효율적인지 평가할 수 있다. 시간 복잡도는 주로 빅오 표기법(Big-O Notation)으로 표현되며, 알고리즘의 수행 시간은 동일 크기의 다양한 입력 데이터에 의해 달라질 수 있기 때문에, 가장 많이 쓰이는 최악의 시간 복잡도의 알고리즘 시간을 T(n)이라고 했을 때, 이것은 크기 n의 모든 입력 데이터에 대해 걸리는 최대의 시간으로 정의할 수 있다. 그 수치가 작을 수록 효율적인 알고리즘을 의미한다. 시간 복잡도에는 빅오(Big-O) 외에도 빅오메가(Big-Omega), 빅세타(Big-Theta)라는 개념도 존재한다.빅오는..