알고리즘9 [기본 다지기] - 그리디 보호되어 있는 글 입니다. 2024. 7. 17. 스패닝 트리(Spanning Tree), 최소비용신장트리(MST), 프림(Prim) 알고리즘 MST와 Prim 알고리즘에 대해 공부해 보자. 목차는 다음과 같다. Spanning Tree란? MST란? Prim알고리즘 Prim알고리즘 실전 문제 그럼 이제 Spanning Tree에 대해 알아보자. Spanning Tree란? 모든 정점(노드)을 포함하면서 간선의 개수가 최소인 트리를 말한다. 특징은 다음과 같다. 앞서 말한 듯 모든 정점을 포함하면서 간선의 개수가 최소다. 사이클이 없는 그래프다.(사이클이 없는 그래프를 트리라고 말한다.) 그럼 위 2가지 특징을 통해 알 수 있는 사실이 있다. Spanning Tree는 모든 정점을 포함하면서 간선의 개수가 최소이려면 간선의 개수는 정점 - 1이 될 수밖에 없다. 이와 관련되어 좀 더 자세히 알아보자. 위와 같이 그래프가 존재할 때 Spannin.. 2024. 3. 19. [후기] 스프린트30 이번에 코드트리 사이트를 구경하다 실전 스프린트30이라는 메뉴를 발견해서 궁금한 마음에 한 번 도전해봤다. 1번 문제부터 쉽지 않았다.(작성자의 능력부족...) 특정 인원 수만큼 뽑아서 특정 점수를 맞추는 문제였다. 틀린 이유:분석을 잘못했고 정답풀이에 해당하는 자료구조를 어떻게 적용해야할지 못했다. 보완점:문제에서 주어진 정보를 가지고 시간제한에 맞는 방법을 구상하는 연습을 꾸준히 해야하고 부족한 자료구조를 더 공부해야 한다. 2번 문제 거스름돈을 이용한 DP문제. 틀린 이유:단순하게 거스름돈을 맞춰주면 된다고 생각해서 그리디로 풀려고 했다... 보완점:예외 발생 구간을 생각하여 반례를 생각해야 한다. DP를 못하기에 꾸준한 DP연습이 필요하다. 3번 문제 X 안 푼 이유:2번까지 다 못풀어서 멘탈이 .. 2023. 12. 21. [개념] Greedy Algorithm 보호되어 있는 글 입니다. 2023. 12. 21. 이전 1 2 3 다음
