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