관리 메뉴
목록2025/01/03 (1)
'll Hacker
EVI$ION 겨울방학 코테스터디 1주차 과제
그리디 알고리즘 눈앞의 이익만 우선 추구하는 알고리즘최적해를 찾을 수 있으면 그것을 목표로 삼고 찾기 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼는다 - 그래서 대부분 최적화 문제를 대상으로 함 예를 들어, n개의 정점을 가지고 사이클을 이루지 않은 총 n-1개의 간선으로 이뤄지는 최소 신장 트리를 만들고자 한다.아직 간선이 하나도 없는 상태라고 하면, n-1개의 간선이 될 때까지 집합을 키워나가게 된다. 이때, 어떤 간선을 선택할지 결정해야한다.최소신장트리같은 경우에는 간선을 하나 더할 때마다 해당 간선이 기존에 선택된 간선들과 사이클이 형성되면 안된다.Greedy(c){ s 1) 원소를 선택하는 기준이 눈앞의 이익을 우선2) 원소를 하나 더하기 전에 해당 원소를 더함으..
Dev
2025. 1. 3. 14:11