Algorithm/Python

파이썬 알고리즘 : 백준 11000번 - 강의실 배정

이번 풀이의 핵심 힌트는 우선순위 큐 입니다. 우선순위 큐를 이용해 백준 11000번 (강의실 배정) 문제를 파이썬으로 풀어 보도록 하겠습니다. 해당 자료구조를 잘 사용하시면 문제가 쉬워지는 것을 느끼실 수 있을 것 입니다. 이번 글에서 알아볼 내용 문제 설명 문제의 핵심 아이디어 문제 풀이 문제 설명 11000번과 같은 경우 문제 설명 자체에 오해의 소지가 있습니다. 수강신청의 마스터 김종혜 선생님이 아니라 수강신청 관리자 김종혜 선생님이 더 알맞는 표현 같습니다. 즉 이번 문제는 수강신청을 관리해서 강의실을 올바르게 배치하는 것을 요구합니다. 강의의 시간이 주어지면 해당 강의에 필요한 강의실을 배치해주는 것 입니다. 이때 가장 적게 강의실을 사용할 수 있는 방법을 묻고 있습니다. 문제의 핵심 아이디어..

Union find 알고리즘 - Python

대표적인 그래프 알고리즘. 오늘은 Union find 알고리즘에 대해 알아보겠습니다. 이번글은 아래의 자료를 참고했습니다. TopCoder 알고리즘 트레이닝 Union find 알고리즘 블로그 1 이 글에서 알아볼 내용 Union find 알고리즘 핵심 아이디어 예제 문제 마치면서 Union find 알고리즘 기본적으로 Union-find 알고리즘은 자료구조라고 볼 수 있습니다. 그래서 Disjoint Set (상호배타적인 집합) 이라고 불리기도 하는데요. 아래의 그림을 통해 간단히 파악해봅시다. 어떤 차이가 있는지 파악하셨나요? 상호배타적 집합은 같은 그룹에 속하지만 공통점은 없는 집합을 뜻합니다. 그리고 Union-find는 이런 상호배타적 집합에서의 데이터 조작을 하는 자료구조 입니다. 그렇다면 이..

크루스칼 알고리즘 - Python

오늘은 크루스칼 알고리즘에 대해서 알아보겠습니다. 크루스칼 알고리즘은 기본적으로 그리디 알고리즘에 속하는데요. 여러개의 노드를 최소비용으로 연결하는 것을 목표로 하고 있습니다. 이번 글은 아래의 자료를 바탕으로 작성됐습니다. 안경잡이 개발자 (크루스칼 알고리즘) 위키백과 (크루스칼 알고리즘) Union-find 알고리즘 (sunghyunpatricklee) 이 글에서 알아볼 내용 크루스칼 알고리즘이란 핵심 아이디어 예제 문제 마치면서 크루스칼 알고리즘이란 "MST (Minimum Spanning Tree) 를 찾기위한 알고리즘". 크루스칼 알고리즘을 설명하는 핵심적인 문장입니다. 그렇다면 MST 는 도대체 무엇일까요? "그래프의 노드들을 가장 적은 연결, 비용으로 모두 연결한트리". 크루스칼 알고리즘은 ..