# CS/Algorithm (3) 썸네일형 리스트형 그리디(Greedy) 알고리즘 그리디(Greedy) 알고리즘 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하는 알고리즘이다. 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지 고려하지 않는다. 그래서 모든 경우의 수를 고려하는 완전 탐색이나 동적 계획법 알고리즘과 달리, 그리디 알고리즘은 매 선택이 그 순간에 대해서는 최적 여부만 고려하므로 최종 도출된 해가 최적이 아닐수도 있다. 그리디 알고리즘을 사용하면 좋은 경우 최적 부분 구조 문제의 최적해가 부분 문제의 최적해로 구성되는 경우에 그리디 알고리즘이 유용하다. 이런 경우에는 각 단계에서 최적의 선택을 하면 전체 문제의 최적해를 얻을 수 있다. 탐욕 선택 속성 각 단계에서 최적의 선택을 하는 것이 문제 전체에 대한 최적해를 구하는 데 필요한 조건이라면 그리디 알.. 다익스트라(Dijkstra) 알고리즘: 최단경로 구하기 다익스트라(Dijkstra) 알고리즘: 최단경로 구하기 다익스트라 알고리즘이란? 다익스트라 알고리즘은 그래프 내의 가중치를 가진 정점들 간의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 그리디 알고리즘으로 분류된다. 매 단계마다 현재까지 알려진 최단 경로와 가장 가까운 정점을 선택하여 최단 경로를 확장해나간다. 이 알고리즘은 한 번의 루프마다 하나의 정점을 처리하므로, 모든 정점들을 고려해야 할 경우 시간 복잡도가 O(V^2)가 될 수 있다. 가중치가 양수인 그래프에서 사용 가능하며, 음수 가중치가 있는 경우에는 정확한 결과를 보장하지 않는다. 작동과정 1. 출발 노드 설정 2. 출발 노드 기준으로 각 노드의 최소 비용 저장 3. 방문하지 않은 누드 중에서 가장 비용이 적은 노드 선택 4. 해당 노드를.. 알고리즘 시간 복잡도 계산하기: Big-O 표기법 시간 복잡도: Big-O 표기법 알고리즘의 효율성을 이론적으로 분석하는 방법으로, Big-O 표기법은 불필요한 연산을 제거하여 시간 복잡도를 간단히 나타낸다. 시간 복잡도 입력값과 연산 수행 시간의 상관관계를 나타내는 척도 시간 복잡도 분석 시간 복잡도 분석에서는 알고리즘이 수행하는 연산의 횟수를 계산한다. 입력의 개수가 증가함에 따라 연산의 횟수가 어떤 형태로 증가하는지에 관심을 둔다. 시간 복잡도 함수 알고리즘이 수행하는 연산의 횟수를 나타내는 함수이다. 입력의 개수 n에 대한 함수(T(n))으로 표현한다. n2을 구하는 문제에 대한 3가지 알고리즘이 다음과 같을때, def Algorithm_A T_A(n)=2 # Algorithm_B 덧셈연산: sum+n # n 대입연산: { i T_B(n)=2n+.. 이전 1 다음
