반응형 그리디2 [코딩 테스트] 21일차: 그리디 알고리즘 문제 그리디 알고리즘 문제이번 글에서는 그리디 알고리즘을 이용한 문제 해결 방법에 대해 다뤄보겠습니다. 주로 거스름돈 문제와 활동 선택 문제를 예제로 사용하여 그리디 알고리즘의 적용 방법을 이해하겠습니다.거스름돈 문제거스름돈 문제는 가장 적은 수의 동전으로 거스름돈을 주는 방법을 찾는 문제입니다. 그리디 알고리즘을 이용하여 가장 큰 단위의 동전부터 거슬러주면 됩니다. 예제: 거스름돈 문제 구현JavaScriptfunction minCoins(coins, amount) { coins.sort((a, b) => b - a); let count = 0; for (let coin of coins) { while (amount >= coin) { amount -= coin; count++;.. 2024. 9. 21. [코딩 테스트] 15일차: 그리디 알고리즘 그리디 알고리즘 (Greedy Algorithm)그리디 알고리즘은 매 순간 가장 최적이라고 생각되는 해를 선택하여 문제를 해결하는 방법입니다. 이 방법은 부분적인 최적 해가 전체적인 최적 해가 될 수 있는 문제에 적합합니다.그리디 알고리즘의 주요 개념현재 시점에서 가장 좋은 선택: 각 단계에서 가장 좋은 선택을 하여 문제를 해결부분 최적 해: 각 부분 문제에서의 최적 해가 전체 문제에서도 최적 해가 되는 경우최소 신장 트리 (MST)최소 신장 트리는 그래프의 모든 정점을 포함하면서, 사이클이 없고, 간선의 가중치 합이 최소인 트리입니다. 대표적인 알고리즘으로는 크루스칼 알고리즘(Kruskal's Algorithm)과 프림 알고리즘(Prim's Algorithm)이 있습니다.크루스칼 알고리즘 (Kruska.. 2024. 9. 15. 이전 1 다음 반응형