greedy

[백준(BOJ)] #11000- 강의실 배정 (파이썬, Python3)

문제 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제 풀이 이 문제는 그리디 알고리즘과 우선순위 큐를 이용해서 해결할 수 있습니다. 2022.07.18 - [알고리즘/개념] - [파이썬으로 배우는 알고리즘] 그리디(Greedy) 알고리즘 [파이썬으로 배우는 알고리즘] 그리디(Greedy) 알고리즘 그리디(Greedy) 알고리즘이란? Greedy는 '탐욕스러운'이라는 뜻을 가진 단어로 탐욕 알고리즘이라고도 불리며 말 그대로 선택의 순간마다 당장 좋은 것만 고르는 방법을 의미합니다. 순간의..

[파이썬으로 배우는 알고리즘] 그리디(Greedy) 알고리즘

그리디(Greedy) 알고리즘이란? Greedy는 '탐욕스러운'이라는 뜻을 가진 단어로 탐욕 알고리즘이라고도 불리며 말 그대로 선택의 순간마다 당장 좋은 것만 고르는 방법을 의미합니다. 순간의 가장 좋아 보이는 것만 선택하기 때문에 나중에 미칠 영향은 고려하지 않아 지역적으로는 최적이지만 최종적(전역적)인 답에 도달했다고 해서 그것이 최적해라는 보장은 없습니다. 만약 그리디 알고리즘을 적용하여 위와 같은 트리에서 거쳐 가는 노드 값의 합을 최대로 만든다고 하면 순간의 선택만 고려하기 때문에 3 -> 7 -> 9라는 경로로 해는 19가 됩니다. 하지만 실제 최적해는 21(3 -> 5 -> 13)로 이는 그리디 알고리즘이 최적의 해를 보장할 수 없음을 보여줍니다. 따라서 그리디 알고리즘을 적용하려면 지역적으..

[프로그래머스(Programmers)/ Level2] 구명보트 (파이썬, Python3)

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42885 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게..