그리디18 [BAEKJOON]2212 센서 문제 요약 알고리즘 분류: 그리디, 정렬 난이도:Gold5 문제내용: N개의 센서와 K개 집중국이 있다. K개의 기지국을 설치해서 송신할수 있도록 최소 거리를 구해라. 사이트: https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 문제풀이 이번 문제는 그리디문제인데, 약간 아이디어 문제측에 속한다. 정답을 어떻게 구할지만 구현은 쉽다. 그리디에 설명은 여기에서 확인 해보면된다. 문제 접근 방법 예제 1번을 그림으로 나타낸 것.. 2023. 1. 8. [BAEKJOON] 1092 배 문제 요약 알고리즘 분류: 그리디, 정렬 난이도:Gold5 문제내용: 크래인 N개와 박스 M개가 있다. 각 크레인은 최대 들수 있는 무게와 박스별 무개가 주어진다. 1분당 한 크래인은 한개만 옮길수있다. 모든 박스를 옮기는데 걸리는 시간을 구해라. 사이트: https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 문제풀이 이번 문제는 그리디문제인데, 약간 아이디어 문제측에 속한다. 정답을 어떻게 구할지만 구현은 쉽다. 그리디에 설명은 밑.. 2022. 12. 6. [BAEKJOON] 2012 등수 매기기 문제 요약 알고리즘 분류: 그리디 난이도: Silver3 문제내용: 실제 성적 등수와 학생 예상 등수 최소 차이를 구해라 사이트: https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 문제풀이 이번 문제는 그리디문제인데, 약간 아이디어 문제측에 속한다. 정답을 어떻게 구할지만 구현은 쉽다. 그리디에 설명은 밑에 사이트에 참조하면된다. https://jih3508.tistory.com/70 [알고리즘 이론] 그리디(Greedy) 이론 그리디 알고리즘은 탐욕 .. 2022. 11. 28. [BAEKJOON] 1439 뒤집기 문제 요약 알고리즘 분류: 그리디 난이도: Silver5 문제내용: 0과 1로 이루어진 문자열 S가 있다. 뒤집다는 의미는 0과 1을 바꾸는것이다. 뒤집을 수 경우는 모두다 뒤집거나 a ~ b 길이 만큼 변경이 가능하다. 모든 숫자가 같을라면 몇번 뒤집어야 하는가 사이트: 거스름돈 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 문제풀이 이번 문제는 최대길이가 100만이고 제한시간 1초라서 O(n)으로 풀어야 한다. 브루드포스 알고리즘으로 풀기에는 무리가 있어서 그리디알고리즘으로 적용해야.. 2022. 11. 25. [알고리즘 이론] 그리디(Greedy) 이론 그리디 알고리즘은 탐욕 알고리즘이라고 부르기도 한다. 즉, 매 순간 선택할때 가장 좋은것을 선택하는 알고리즘이다. 이 알고리즘은 이론상 설명 단순하고 다른 알고리즘에서 기초적으로 다루는 알고리즘이다. 2022. 11. 23. [BAEKJOON] 13305 주유소 문제 요약 알고리즘 분류: 그리디 난이도: Silver3 문제내용: 2번째 줄은 각 도시간의 거리 3번째 줄은 도시별 주우쇼가격이다. 맨 왼쪽에서 출발해서 맨 끝 오른쪽까지 도착하는데 최소한의 비용을 출력해라. 문제풀이 이번문제는 그리디 문제이다. 데이터가 1,000,000,000 이상이고 파이썬이 처리할수 있는 초당 처리할수 연산은 약 천만 정도이다. 그래서 O(n)으로 풀어야 통과가 된다. 그리디에 대한 설명은 아래 사이트에 참조하면된다. https://namu.wiki/w/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 그리디 알고리즘 - 나무위키 그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택.. 2022. 11. 15. 이전 1 2 3 다음
