Greedy
-
[프로그래머스] - 최고의 집합Algorithm/프로그래머스 2022. 9. 8. 16:47
문제 [프로그래머스] - 최고의 집합 https://school.programmers.co.kr/learn/courses/30/lessons/12938 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 더보기 문제 설명 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합 예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4..
-
[Programmers] - 구명보트Algorithm/프로그래머스 2022. 7. 7. 12:55
[Programmers] - 구명보트 https://school.programmers.co.kr/learn/courses/30/lessons/42885 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 구명보트를 최대한 적게 사용하여 많은 사람들을 나르고 싶다. 보트가 견디는 무게가 100kg 이고 사람들의 몸무게가 다음과 같다면 [70kg, 50kg, 80kg, 50kg] 50+50 / 70 / 80 위와 같은 식으로 탈 수 있는 것이다. 알고리즘 그리디 알고리즘과 투포인터를 사용하여 풀었다. 가장 큰 무게를 가진 사람이 가장 무게를 적은 사람을..
-
[BOJ] 8980번 - 택배Algorithm/BOJ 2022. 6. 20. 17:36
[BOJ] 8980번 - 택배 https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 알고리즘 트럭 한대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 한다. 최대한 많은 박스들을 가져가야 함으로 그리디 알고리즘으로 생각하여 구현하였습니다. 처음에는 Truck을 Time에 따라 구현하였으나, 시간 복잡도가 부족하여 75점이 나왔기 때문에 후에 정렬된 박스들의 표를 보고 얼마나 보낼 수 있는지로 구현하여 O..
-
[BOJ] 1700번 - 멀티탭 스케줄링Algorithm/BOJ 2022. 6. 13. 22:07
[BOJ] 1700번 - 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 알고리즘 그리디 알고리즘 멀티탭을 오랫동안 유지하고 싶음으로 가장 나중에 사용할것을 바꾸어주는게 좋다. 1. 멀티탭에 이미 있는 경우 -> PASS 2. 멀티탭에 빈자리가 있는 경우 -> 빈자리에 꼽는다. 3. 멀티탭에 있는것을 뺀 다음 새롭게 꼽는다. 4. 단 멀티탭에 있는 것을 빼기 위해서는 다음에 사용하지 않을 것이 우선순위 5. 다음에 사용된다면 가..
-
[BOJ] 2170번 - 선 긋기Algorithm/BOJ 2022. 6. 11. 13:56
[BOJ] 2170번 - 선 긋기 https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 주의할 점이 선을 긋는다고 하여 0부터 시작하는 것이 아닌 음수부터 시작이 된다 및 여러 번 그은 부분이나 한번 그은 부분이나 동일하게 계산되어야 한다. 알고리즘 그리디 알고리즘을 이용하여 풀었다. 시작점이 작은 좌표부터 시작하여 가장 긴 값을 찾아가는 형태로 찾아가면 최소 최대 길이를 구할 수 있다. 최소 값을 갱신하면서 찾아야 하기..
-
[BOJ] 15903번 - 카드 합체 놀이Algorithm/BOJ 2022. 6. 10. 14:11
[BOJ] 15903번 - 카드 합체 놀이 https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 알고리즘 그리디로 생각하여 풀었다. 작게 만들기 위해서는 작은 두수를 뽑아내서 갱신시켜주어야 한다. 이때 시간 복잡도가 가장 낮은 Heap을 이용 1. heapq를 이용하여 Data 초기화 2. 요청받은 갯수만큼 heapq 갱신 3. 갯수 출력 코드 #BOJ 15903번 import heapq n , m = map(i..