전체 글 썸네일형 리스트형 [코딩테스트/개념] 크루스칼 알고리즘 (Kruskal's Algorithm) 크루스칼 알고리즘 (Kruskal's algorithm) 은 주어진 그래프에서 최소 신장 트리를 찾는다. 주로 그래프 내의 모든 정점을 최소 비용으로 연결하기 위해 사용한다. 간선의 개수가 E, 정점의 개수가 V 일 때 O(ElogV) 의 시간복잡도를 가진다. 모든 간선에 대해 (1) 가중치가 최소인 간선을 찾고, (2) 해당 간선으로 인해 사이클이 발생하지 않는다면 (Union-Find 활용) 두 정점을 연결한다. Union-Find 는 상호 배타적인 집합을 효율적으로 표현하기 위한 자료 구조이다. 서로 다른 두 개의 집합을 병합하는 Union 연산과 어떤 원소가 속한 집합을 찾는 Find 연산으로 구성된다. 크루스칼 알고리즘에서 정점 간의 연결 여부를 판단하는 데에 사용한다. 📍 참고 자료 http.. 더보기 [코딩테스트/Python] 프로그래머스 "체육복" 📍 문제 출처 https://school.programmers.co.kr/learn/courses/30/lessons/42862 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📍 풀이 방법 앞번호에게 빌려주는 경우, 뒷번호에게 빌려주는 경우를 다 따져보지 않고도 그리디하게 풀 수 있는 문제이다. 우선 학생 수만큼의 길이를 가지는, 모두 1로 구성된 리스트 students 를 만든다. lost, reserve 를 각각 순회하면서 도난 당한 학생은 1을 빼주고, 여분이 있는 학생은 1을 더해준다. students 의 인접한 두 요소는 총 9가지의 상태 - (.. 더보기 [코딩테스트/개념] 탐욕 알고리즘 (Greedy Algorithm) 탐욕 알고리즘 (Greedy algorithm) 은 매 순간 '지금 당장 최적인 것'을 선택하여 문제를 해결한다. 탐욕 알고리즘으로 전역적인 최적해를 구하기 위해서는 문제가 두 가지 속성 - 탐욕 선택 조건, 최적 부분 구조 - 을 만족해야 한다. 즉, 현재의 선택이 다음의 선택에 영향을 주지 않아야 하고 (탐욕 선택 조건), 부문 문제에 대한 최적해가 전체 문제에 대한 최적해여야 한다 (최적 부분 구조). 📍 참고 자료 https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 탐욕 알고리즘(Greedy algorithm)은 .. 더보기 이전 1 2 다음
