반응형 분류 전체보기158 부하테스트 - 컨텐츠 생성- 학습지 다운- 마이페이지 2025. 6. 21. DP(동적계획법) 복잡한 문제를 작은 문제루 나누고 해결한 결과를 저장해 두었다가 나중에 큰 문제의 결과하여 합하여 풀이하는 알고리즘알고리즘의 이름이 동적 계획법이라고 하지만 원리에 가까운 용어는 '기억하며 풀기'가 더욱 적합하다. dp의 조건(사용조건)최적 부분 구조문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성된 문제중복 부분 문제같은 작은 문제를 여러번 반복적으로 해결해야함dp에서는 이를 메모이제이션을 통해 저장해두고 결과를 합하여 큰 문제를 해결함 dp와 그리디의 비교최적 부분 문제를 풀어나간다는 점은 그리디 알고리즘과 같다.하지만 그리디 알고리즘은 항상 최적이라고 생각하는 것을 선택한 후 풀이를 진행해나가고,dp는 이를 저장시켜두고 전체 해를 구할 때 활용한다는 것이다.그리디 알고리즘에 해당되.. 2025. 6. 15. 크루스칼과 프림 (최소신장 트리) 신장트리(Spanning Tree)신장트리의 조건N개의 정점을 가지는 그래프에서 최소 N-1 개의 간선으로 연결되어 있다.그래프의 모든 정점을 포함한다.신장트리는 최소한의 간선으로 모든 정점을 연결한 트리이다.따라서 사이클이 존재하지 않는 특징이 있다. 최소 신장 트리(Minimum Spanning Tree)최소한의 간선으로 모든 정점을 연결하며, 이때 간선의 가중치의 합이 최소로 이루어진 트리 크루스칼 알고리즘크루스칼 알고리즘은 최소 신장 트리를 만들기 위한 알고리즘으로 그리디 알고리즘의 한 종류이다.매 순간 가중치가 가장 낮은 간선을 선택한다.이러한 그리디 알고리즘 방식은 로컬 최적해를 구하지만 전체 최적해를 보장하지 않는다.하지만, 크루스칼 알고리즘은 사이클이 존재하지 않는 조건을 통해 로컬 최적해.. 2025. 6. 15. 그리디 알고리즘(feat. 다익스트라) 그리디(탐욕) 알고리즘최적의 해를 구하는 데에 사용되는 근시안적인 방법이다.각 단계에서 최적이라고 판단하는 것을 선택해 나가는 방식으로 최종적인 해답에 도달하는 알고리즘이다.문제에 따라 최적해를 보장하기도 하지만, 일반적으로 근사 해를 구하는데 사용된다. 따라서 그리디 알고리즘을 사용하기 위해서는 부분 문제의 최적해가 전체 문제의 최적해를 보장하는 경우에 사용해야한다.실생활에서는 이러한 문제가 상당히 많이 있기 때문에 많은 문제에 적용될 수 있다. 그리디 알고리즘의 조건탐욕 선택 속성매 순간 가장 좋아보이는 선택을 해도 전체 최적해를 구할 수 있는 성질최적 부분 구조작은 부분 문제의 해로 전체 문제의 최적해를 구할 수 있는 성질그리디 알고리즘은 위의 두 성질을 만족해야한다.dp의 경우에도 최적 부분 구조.. 2025. 6. 15. 이전 1 2 3 4 ··· 40 다음 반응형