본문 바로가기
반응형

탐욕 알고리즘14

03.12. 수 묶기 [Greedy Algorithm][백준 1744] https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net Algorithm classification : Greedy Algorithm 03.12.1. Problem Given a sequence of length N, we want to find the sum of the sequences. However, instead of just adding up the sum of the sequences, we are trying to combine two.. 2022. 2. 8.
06. Greedy Algorithm(2) Greedy Technique 01. Greedy Technique suggests constructing a solution to an optimization problem through a sequence of steps, each expanding a partially constructed solution obtained so far, until a complete solution to the problem is reached On each step, the choice made must be(Feasible, i.e., it has to satisfy the problem’s constraints, locally optimal, i.e., it has to be the best local choi.. 2021. 11. 18.
05. Greedy Algorithm(1) 안녕하세요. 오늘은 Greedy Algorithm. 한국어로는 탐욕적 기법이라고 하는 알고리즘을 소개할까 합니다. DP와 함께 굉장히 유명한 알고리즘인데요. 개념 자체는 이해하기 쉽습니다. 하지만 어려운 문제도 많은만큼 마스터는 어려운 파트죠. 탐욕적 기법은 말 그대로 탐욕적으로 당장 눈에 보이는 것 중에 가장 맛있어 보이는 부분(이익) 만 취하겠다는 것입니다. 물론 이런 방법이 통하지 않는 경우도 있습니다. 도시락 데우기, 파일 합치기 등은 탐욕적 기법이 통하는 유명한 문제입니다. 이런 경우는 여러 번의 선택이 모두 잘못되지 않아야 합니다. 즉, 눈 앞에 보이는 것에 대해서 취한 전략이 그 이후에도 계속 성립해야 한다는 것입니다. 많은 문제들이 딱보고 그리디라고 판단하기는 어려운데요. 쉽게 반례가 떠오.. 2021. 11. 18.
03.11. 박스 채우기[Greedy Algorithm][백준 1493] https://www.acmicpc.net/problem/1493 1493번: 박스 채우기 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, www.acmicpc.net Algorithm classification : Greedy Algorithm, Math, Divide and conquer 03.11.1. Problem Sejun has a box with dimensions length × width × height. And Sejun tries to fill this box with cubes. A cube has the .. 2021. 11. 10.
03.10. Rest Stops[Greedy Algorithm][백준 15748] https://www.acmicpc.net/problem/15748 15748번: Rest Stops The first line of input contains four integers: $L$, $N$, $r_F$, and $r_B$. The next $N$ lines describe the rest stops. For each $i$ between $1$ and $N$, the $i+1$-st line contains two integers $x_i$ and $c_i$, describing the position of the $i$-th rest st www.acmicpc.net Algorithm classification : Greedy Algorithm, Sorting 03.10.1. Proble.. 2021. 11. 10.
03.09. 과제[Greedy Algorithm][백준 13904] https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net Algorithm classification : Greedy Algorithm 03.09.1. Problem Woongchan has many challenges. You can complete one assignment per day, but each assignment has a deadline, so you may not be able to finish all of them. Each task has a score for complet.. 2021. 11. 9.
반응형