Algorithms/Greedy 검색 결과

해당 글 7건

[BOJ 2457] 공주님의 정원(C++)

공주님의 정원(Gold 4) 문제 전체 문제 보기 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 접근법 이번 문제는 주어진 날짜 형식(mm dd)을 정수형으로 변환한 후 그리디로 풀 수 있는 문제입니다. 먼저 날짜를 정수형으로 변환하는 방법에 대해서 살펴봅니다. 날짜 형식을 정수형으로 변환 constexpr int monToInt[13] = { 0, 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334 }; int DayToInt(int mm, ..
Algorithms/Greedy 2021. 12. 16. 09:42

[BOJ 8980] 택배 (C++)

택배 Gold 3 문제 전체 문제 보기 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 접근법 이번 문제는 어떻게 접근할지 생각하기 다소 어려운 문제였습니다. 이번 문제 같은 경우 그리디로 풀 수 있지만 DP로 풀어야할지 그리디로 풀어야할지 여러 방향으로 오래 고민을 했습니다. 제가 풀었던 방법은 다음과 같습니다. 가장 많은 택배를 배송하기 위해서는 새로운 택배를 많이 받아야 합니다. 새로운 택배를 많이 받기 위해서는 빨리 내릴 수 있는 택배를 먼저 받고 바로 새로운 택배를 받아야 합니다...
Algorithms/Greedy 2021. 11. 12. 10:13

[프로그래머스] (Greedy) 단속카메라 (C++)

단속카메라 (Level 3) 문제 전체 문제 보기 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 접근법 이 문제에서 구해야 하는 값은 전체 차량의 이동경로가 주어졌을 때 모든 차량이 한 번은 단속용 카메라를 만나도록 하기 위한 최소 카메라 설치대수이다. 차량의 이동 경로는 아래와 같이 규칙 없이 입력될 수 있다. 카메라를 가장 최소한으로 설치 하기 위해서는 "가능한" 시작 지점에서 최대한 떨어진 곳에 설치하고, 그다음 카메라는 한번 설치한 카메라와 "가능한" 가장 멀리 떨어진 곳에 설치해야 한다. 그러면 "가능한" 이라고 추상적으로 표현한 부분을 어떻게 구체화 할 수 있을까? 먼저 가장 시작 지점에서 최대한 멀리..
Algorithms/Greedy 2021. 7. 31. 14:20

[프로그래머스] (Greedy)섬 연결하기 (C++)

섬 연결하기 (Level 3) 문제 전체 문제 보기 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 접근법 최소 비용 신장 트리 이번 문제는 두 가지 방법으로 풀었다. 처음 접근하는 방법은 동일하고 구현하는 방법에서 차이가 있기 때문에 공통된 부분을 설명한 뒤 두 가지 풀이법을 모두 다뤄본다. 문제에서 요구하는 바는 모든 섬을 가장 적은 비용으로 연결했을 때의 비용이다. 이를 자료구조에서는 최소 비용 신장 트리 (MST)라고 한다. 이에 대한 설명은 예전에 다룬 글이 있어 링크를 남긴다. 간략하게만 정리하면 최소 비용 신장 트리는 신장 트리의 일종인데, 먼저 신장 트리가 되기 위해서는 다음의 조건을 만족해야..
Algorithms/Greedy 2021. 7. 30. 12:21