'그리디 알고리즘' 태그의 글 목록

[백준] 2457번 공주님의 정원 (C)

출처 2011 지역본선 초등2 문제 주소 백준 2457번 공주님의 정원 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1a>>b>>c>>d; in[i].start=a*100+b; in[i].end=c*100+d; } sort(in,in+n,cmp); int now=301,ans=0,index,max=0; for(int i=0;i1130) break; // 오늘(now)을 포함하는 꽃들 중 가장 오래 심을 수 있는 꽃을 찾는다. if(max

Problem Solve/Greedy 2020. 3. 8. 09:44

[백준] 8980번 택배 (C)

출처 2013 전국 본선 초등2 알고리즘 그리디 힌트 상자를 싣고 갈 구간을 보자. 문제 풀이 그리디 알고리즘으로 간단하게 풀리는 문제지만 뭐에 대해서 그리디를 적용시킬지 찾는게 쉽지 않다. 결론 부터 말하자면 상자가 트럭에 실려 있는 구간이 짧은 순으로 확인하면 된다. 구간이 같다면 먼저 실을 수 있는 상자를 선택한다. 따라서 상자를 목적지, 출발지 순으로 오름차순 정렬하면 된다. 그 뒤 반복문으로 앞에서 부터 살피면 되는데 이번에 선택된 상자(now)가 트럭에 실려있어야 할 구간을 살피고 모두 실을 수 있다면 now의 cost를, 용량이 초과된다면 남은 용량 만큼을 그 구간에 더해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2..

Problem Solve/Greedy 2020. 3. 7. 22:37

[코드업] 4040 : 펜션 (C)

알고리즘 그리디 힌트 손님이 펜션에서 가장 오랫동안 머물 수 있는 방을 찾아준다. 풀이 아이디어는 간단하다. 손님이 오늘부터 가장 오랫동안 머물 수 있는 방을 찾아주면 된다. 여기서 잔재주를 부려보면 펜션의 상태를 char형으로 그대로 저장 말고 0,1로 바꾸어 저장해준다. (O : 1, X : 0) 이러면 비교 연산자를 사용하지 않고 조건문 처리가 가능하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 #include using namespace std; int in..

Problem Solve/Greedy 2020. 3. 7. 15:16

[코드업] 3321 : 최고의 피자 (C)

알고리즘 그리디 힌트 가장 칼로리가 높은 토핑만 생각한다. 풀이 도우는 무조건 포함해야 하므로 cost(가격)와 cal(칼로리)를 도우의 가격과 칼로리로 초기화해준다. 토핑의 가격들이 입력되면 내림차순으로 정렬해준다. (토핑은 한 번만 사용할 수 있으므로 남아 있는 토핑 중 가장 칼로리가 높은 토핑만 고려하면 된다.) 현재의 칼로리/달러가 i번째 토핑을 추가했을 때의 칼로리/달러보다 클 경우 cal과 cost를 갱신해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include #include using namespace std; int cmp(int a, int b)..

Problem Solve/Greedy 2020. 3. 7. 01:44

[코드업] 3301 : 거스름돈 (C)

알고리즘 그리디 힌트 가장 비싼 화폐부터 거슬러 준다. 풀이 이 문제는 대표적인 그리디 문제다. 거슬러 줄 수 있는 가장 비싼 화폐부터 거슬러 주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include using namespace std; int main(){ int money[8]={10,50,100,500,1000,5000,10000,50000}; int n,cnt=0; cin>>n; for(int i=7;i>=0;i--){ cnt+=n/money[i]; n%=money[i]; } cout

Problem Solve/Greedy 2020. 3. 6. 21:43

[코드업] 3120 : 리모컨 (C)

알고리즘 그리디, 백트래킹 힌트 매 시행마다 목표 채널과 현재 채널중 큰 것을 골라 빼거나 작은 것을 골라 더한다. 풀이 a와 b의 대소 관계가 고정되어 있지 않기 때문에 임의로 a>b로 잡아 주었다. 변경할 수 있는 수가 1, -1, 5, -5, 10, -10 인 것에 주목하자. (절대값이 같은 두 수가 3쌍이다.) a에 10을 뺀 것은 b에 10을 더한 것으로 치환할 수 있다. ( 현재 온도를 x도 높인 것은 목표 온도를 x도 낮춘것 과 같고, 현재 온도를 x도 낮춘 것은 목표 온도를 x도 높인 것 과 같다. ) 따라서 두 수 중 큰 수만 값을 줄여주면 되기 때문에 임의로 a와 b의 대소관계를 정해주는 것은 일반성을 잃지 않는다. 시행 횟수에 영향을 미치지 않는다. d 배열에 양수 값만 필요하고 a,..

Problem Solve/Greedy 2020. 3. 6. 15:35

낭만 IT

그리디 알고리즘 → (6)건