그리디 [백준]2513 통학 버스(자바) 또, 이 아파트 단지 주민을 위해 도로 위 한 지점에 학교 하나를 신설하였다. 각각의 아파트 단지와 학교의 위치는 도로 위의 좌표로 주어지며, 또 각 아파트 단지마다 여기에 사는 학생들의 수도 주어진다. 통학버스는 아침에 학교를 출발하여 각 아파트 단지에 있는 학생들을 태우고 학교로 다시 돌아온다. 아파트 단지 A, B, C가 각각 좌표 0, 2, 5에 있고 이 단지에 사는 학생은 각각 1,... Java알고리즘그리디boj통학 버스자바25132513 [백준] 1246_온라인판매 python 경래는 닭을 기르는데 올 겨울 달걀 풍년으로 함박 웃음을 짓고 있다. 그리고 이 달걀을 영양란으로 둔갑하여 옥션에 판매하려한다. 경래는 총 N개의 달걀이 있고, 그의 잠재적인 고객은 총 M명이다. 그리고 각각의 i번째 고객은 각자 달걀 하나를 Pi 가격 이하로 살 수 있다고 밝혔다. 경래는 영양란이라 속인 죄책감에 한 고객에게 두 개 이상의 달걀은 팔지 않기로 하였다. 하지만 위의 규칙 하에... 그리디파이썬bojpython백준boj [백준] 2839_설탕배달 python 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3... 그리디파이썬bojpython백준boj [백준] 5585_거스름돈 python 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미... 그리디백준파이썬그리디 [백준] 11047_동전0 python 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,00... 그리디백준파이썬그리디 [백준] 12927_배수 스위치 python 강호는 전구 N개를 가지고 있다. 전구는 1번부터 N번까지 번호가 매겨져 있으며, 일렬로 놓여져 있다. 전구는 켜져있거나 꺼져있다. 강호는 모든 전구를 끄려고 한다. 강호는 전구를 켜고 끌 수 있는 스위치 N개를 가지고 있고, 스위치도 1번부터 N번까지 번호가 매겨져 있다. i번 스위치는 i의 배수 번호를 가지는 전구의 상태를 모두 반전시킨다. 현재 전구의 상태가 주어졌을 때, 모든 전구를 ... python백준파이썬그리디python 그리디 : 숫자 카드 게임 여러 카드 덱에서 가장 낮은 숫자를 뽑고, 낮은 숫자 중 가장 높은 카드 한장을 뽑은 사람이 승리하는 게임이다. 카드들은 nxm (행 x 열) 형태로 놓여있다 카드를 뽑고자하는 행을 선택 선택한 행 중 가장 낮은 카드 뽑아야함 낮은 카드 중 최종적으로 가장 높은 카드를 뽑은 사람이 승리 🥕입력예시 : 첫줄에는 행과열, 그 뒤에는 카드들 주어짐 🥕출력예시 각 행마다 가장 작은 수를 찾은 뒤에 ... 그리디알고리즘코딩테스트그리디 BOJ 9237번 이장님 초대 파이썬 농부 상근이는 마당에 심기 위한 나무 묘목 n개를 구입했다. 묘목 하나를 심는데 걸리는 시간은 1일이고, 상근이는 각 묘목이 다 자라는데 며칠이 걸리는지 정확하게 알고 있다. 상근이는 마을 이장님을 초대해 자신이 심은 나무를 자랑하려고 한다. 이장님을 실망시키면 안되기 때문에, 모든 나무가 완전히 자란 이후에 이장님을 초대하려고 한다. 즉, 마지막 나무가 다 자란 다음날 이장님을 초대할 것이... 백준알고리즘그리디그리디 BOJ 1826번 연료 채우기 파이썬 성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 1km를 가는데 1L의 연료가 새 나가게 되었다. 이것을 고치기 위해서는 가장 가까운 마을에 가야 한다. 그런데 그냥 가다가는 중간에 연료가 다 빠질 수가 있다. 다행스럽게도 정글 곳곳에 연료를 채울 수 있는 주유소가 N개 있다. 그런데 정글 속에서 중간에 차를 멈추는 행위는 매우 위험한 행위이므로 주유소에서 멈추는... 백준알고리즘우선순위 큐그리디그리디 BOJ 17521번 Byte Coin 파이썬 실제로는 바이트 코인 가격을 예상할 수 없지만 이 문제에서는 바이트 코인 가격 등락을 미리 정확히 예측할 수 있다고 가정하자. 우리는 1일부터 n일까지 n일 동안 그림 1과 같이 바이트 코인의 등락을 미리 알 수 있으며 우리에게는 초기 현금 W가 주어져 있다. 그림 1의 빨간색 네모는 해당 일자의 바이트 코인 가격을 나타낸다. 매일 바이트 코인을 매수하거나 매도할 수 있다고 하자. 우리는 n... 백준알고리즘그리디그리디 BOJ 2720번 세탁소 사장 동혁 파이썬 간단한 브론즈 문제인데 부동소수점 타입 계산할 때 생기는 오차 때문에 꽤 시간을 소용했다. 미국으로 유학간 동혁이는 세탁소를 운영하고 있다. 동혁이는 최근에 아르바이트로 고등학생 리암을 채용했다. 거스름돈의 액수가 주어지면 리암이 줘야할 쿼터(Quarter, $0.25)의 개수, 다임(Dime, $0.10)의 개수, 니켈(Nickel, $0.05)의 개수, 페니(Penny, $0.01)의 개... 백준알고리즘그리디그리디 [BOJ] 2839번: 설탕배달(Java) 가장 적은 수의 봉지로 배달하기 위해서는 5kg의 봉지로 가져갈 수 있는 만큼 최대한 가져가야 한다. 코드... 그리디그리디 백준 1082, 방 번호 - DP, Greedy, 문자열 1) DP 배열 정의: String[] dp dp[cost]: cost원 금액 내로 만들 수 있는 최대 숫자 문자열 출력, 최대 숫자: BigInteger(dp[m]) => dp[] 원소에 Leading-Zero 문자열이 저장될 수 있으므로, BigInteger를 이용하여 Leading-Zero 문자열을 제거 BigInteger 클래스 int, long 범위를 넘어가는 매우 큰 정수를 사용,... DPString백준 1082 방 번호알고리즘그리디greedydynamic programming동적 계획법코딩 테스트DP [Lv2] 큰 수 만들기 문제 풀이... 그리디그리디 [JO] 1828번: 냉장고(Java) 한 냉장고의 화학물질을 최대로 담아야 하므로 '그리디' 알고리즘 적용 화학물질의 최저 보관온도와 최고 보관 온도를 저장할 Material 클래스 선언 Material클래스에 Comparable를 implement하여 max값에 따라 오름차순으로 정렬될 수 있도록 함. 오름차순 정렬 후, Max를 첫번째 원소의 max값으로 저장. mat[i]의 min 값이 현재 max값보다 클 경우 같이 저장... 그리디그리디 [BOJ] 11000번 강의실 배정(java) 우선순위 큐(PriorityQueue) 활용 우선순위 큐란? 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조 문제에서는 강의가 가장 일찍 끝나는 강의실이 우선순위로 배정되어야 함(PriorityQueue Default) 강의의 start와 end를 int[]로 입력받아 저장.끝나는 시간을 기준으로 오름차 순 정렬.첫 번째... 그리디그리디 [백준/ 파이썬] 1105 팔 백준 1105번 팔 이번에 풀어볼 문제는 1105번 팔 문제입니다. 1105번 문제는 최적의 해를 찾는 그리디 문제입니다. 문제를 이해하는데에는 크게 어려움이 없고 머릿속으로 이렇게 저렇게하면 되겠다는 생각이 들것입니다. 우선 크게 보면 자릿수가 같을때와 자릿수가 다를때를 생각할 수 있습니다. 자릿수가 다르다면 8은 필요하지 않을것입니다. 그래서 우리가 생각을 해줘야 하는 부분은 자릿수가 같... 그리디백준1105파이썬1105 백준 1461, 도서관 - Greedy 모든 책을 제자리에 놔둔 후, 다시 원점 0 으로 돌아올 필요 X => 가장 먼 거리의 m개 책을 마지막에 놔두고 종료해야 함 1) 각 책의 위치 리스트를 거리가 먼(절댓값이 큰) 순으로 정렬 음수 위치 리스트, 양수 위치 리스트 각각 나누어 저장 및 정렬 => 원점을 기준으로 서로 반대편(음수, 양수)에 있는 책들은 왕복을 각각 수행하므로 e.g. 한 번에 들 수 있는 책이 2권이고 남은 ... 그리디greedy백준 1461 도서관알고리즘코딩 테스트greedy 백준 18310 - 안테나 일직선 상의 마을에 여러 채의 집이 위치해 있다. 이중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 결정했다. 효율성을 위해 안테나로부터 모든 집까지의 거리의 총 합이 최소가 되도록 설치하려고 한다. 이 때 안테나는 집이 위치한 곳에만 설치할 수 있고, 논리적으로 동일한 위치에 여러 개의 집이 존재하는 것이 가능하다. 집들의 위치 값이 주어질 때, 안테나를 설치할 위치를 선택하는... 백준그리디그리디 백준 1105, 팔 - Greedy 1) L 의 전체 자릿 수 != R 의 전체 자릿 수인 경우 8의 최소 개수는 0 2) L 의 전체 자릿 수 == R 의 전체 자릿 수인 경우 높은 자릿 수 부터 각 동일 자릿 수를 비교하여, 8로 같은 자릿 수의 개수 두 자릿 수가 다르면, 비교 종료 ex) 800, 899 => 1 (백의 자리 8) 8808, 8880 => 2 (천의 자리 8, 백의 자리 8) 1208, 1288 => 0... 그리디greedy알고리즘코딩 테스트백준 1105 팔greedy 백준 2437, 저울 - Greedy, 누적 합 n개의 추들의 조합으로 만들 수 없는 최소 무게 구하기 ① n개 추들의 조합으로 만들 수 있는 "최대 무게" = 모든 추들의 무게 합 ② n개 추들의 조합으로 만들 수 없는 "최대 무게" = 모든 추들의 무게 합 + 1 ③ 작은 무게 ~ 큰 무게 순으로 정렬했을 때, 인접한 추 끼리 무게 차이가 작아야 더 촘촘히(?) 추의 무게 합 구성 가능 n개 추들을 무게 작은 순으로 정렬 ①에서 유추한... 그리디greedy누적 합알고리즘백준 2437 저울코딩 테스트greedy 백준 1092, 배 - Greedy 각 크레인의 최대 무게 리스트, 각 박스의 무게 리스트를 큰 순으로 정렬 가장 큰 무게의 박스, 가장 큰 무게의 크레인부터 확인 1) 해당 박스를 해당 크레인으로 옮길 수 있는 경우 해당 박스를 박스 리스트에서 삭제 다음 박스, 다음 크레인 확인 2) 해당 박스를 해당 크레인으로 옮길 수 없는 경우 다음 박스(현재 해당 박스 이하의 무게)를 현재 크레인으로 옮길 수 있는지 확인 => 모든 크... 그리디greedy백준 1092 배알고리즘코딩 테스트greedy 1783번 병든 나이트 파이썬 병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자. 병든 나이트가 여행에서 방문할 수 있는 칸의 개수중 최댓값을 출력한다. 최대로 많이 방문할 수 있는 최댓값을 구하는 것 이동방식 ... 백준조건분기알고리즘그리디그리디 백준 20115, 에너지 드링크 - Greedy 규칙에 따라 합친 최종 에너지 드링크의 양을 최대로 만들기 => 절반을 버리고 합치므로, 절반을 버리는 드링크는 양이 작아야 함 규칙: 가장 작은 양의 드링크의 절반을 가장 큰 양의 드링크에다 부어서 합치기 => 가장 큰 양의 드링크가 계속 늘어나면서 갱신됨 1) 드링크 양 배열을 작은 순으로 정렬 2) 가장 큰 양(배열의 맨 뒤 원소)을 선택하여, 맨 앞의 작은 양부터 차례로 합쳐나감 in... 그리디greedy알고리즘백준 20115 에너지 드링크코딩 테스트greedy 백준 1715, 카드 정렬하기 - Greedy n개 카드 묶음의 경우, 총 (n-1)번 합침 2개 카드 묶음을 합치고, 합쳐진 카드 묶음은 또 다시 다른 카드 묶음과 합침 => 최소 비교 횟수로 모두 합치려면, 적은 카드 묶음끼리 합쳐나가야 함 => 각 카드 개수를 우선순위 큐에 저장 및 정렬해가면서 합침 1) PriorityQueue에 각 묶음의 카드 개수를 저장하여 정렬 카드 개수 적은 순으로 정렬 2) PriorityQueue에 원... 그리디greedy알고리즘백준 1715 카드 정렬하기코딩 테스트greedy 1080번 행렬 파이썬 만약 A를 B로 바꿀 수 없다면 -1을 출력한다. 최적 부분 구조: 각 부분 문제의 최적해만 있으면, 전체 문제의 최적해를 쉽게 얻어낼 수 있을 경우 최적 부분 구조 조건을 성립한다고 함 탐욕적 선택 속성: 탐욕적으로만 선택을 해도 최적해를 구할 수 있음. <예를 들어 도착했을 때 최댓값을 구하려고 할 때, 맞닥뜨리는 양갈래길마다 값이 큰 길만 선택> 다른 특징으로는, 한번 선택한 것은 번복... 백준알고리즘그리디그리디 백준 7983, 내일 할거야 - Greedy e.g. 예제 1에서 과제1의 종료일은 7일, 과제2의 종료일은 8일로 서로 안겹치게 배치됨 1) 과제 객체(과제 소요일 d_i, 과제 마감일 t_i) 배열을 정렬 과제 마감일(t_i)이 큰 순(뒷 일자가 먼저 오도록 늦은 순)으로 정렬 2) 마감일이 큰 과제부터 과제 (시작 일자, 종료 일자)를 지정 조건 ①: [기본 조건] 현재 과제의 종료 일자 <= 현재 과제의 마감일 현재 과제의 종료... 그리디greedy알고리즘백준 7983 내일 할거야코딩 테스트greedy 2847번 게임을 만든 동준이 파이썬 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어의 점수는 레벨을 클리어하면서 얻은 점수의 합으로, 이 점수를 바탕으로 온라인 순위를 매긴다. 동준이는 레벨을 난이도 순으로 배치했다. 하지만, 실수로 쉬운 레벨이 어려운 레벨보다 점수를 많이 받는 경우를 만... 백준알고리즘그리디그리디 1543번 문서검색 파이썬 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다. 세준이는 ... 백준문자열알고리즘그리디그리디 이전 기사 보기
[백준]2513 통학 버스(자바) 또, 이 아파트 단지 주민을 위해 도로 위 한 지점에 학교 하나를 신설하였다. 각각의 아파트 단지와 학교의 위치는 도로 위의 좌표로 주어지며, 또 각 아파트 단지마다 여기에 사는 학생들의 수도 주어진다. 통학버스는 아침에 학교를 출발하여 각 아파트 단지에 있는 학생들을 태우고 학교로 다시 돌아온다. 아파트 단지 A, B, C가 각각 좌표 0, 2, 5에 있고 이 단지에 사는 학생은 각각 1,... Java알고리즘그리디boj통학 버스자바25132513 [백준] 1246_온라인판매 python 경래는 닭을 기르는데 올 겨울 달걀 풍년으로 함박 웃음을 짓고 있다. 그리고 이 달걀을 영양란으로 둔갑하여 옥션에 판매하려한다. 경래는 총 N개의 달걀이 있고, 그의 잠재적인 고객은 총 M명이다. 그리고 각각의 i번째 고객은 각자 달걀 하나를 Pi 가격 이하로 살 수 있다고 밝혔다. 경래는 영양란이라 속인 죄책감에 한 고객에게 두 개 이상의 달걀은 팔지 않기로 하였다. 하지만 위의 규칙 하에... 그리디파이썬bojpython백준boj [백준] 2839_설탕배달 python 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3... 그리디파이썬bojpython백준boj [백준] 5585_거스름돈 python 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미... 그리디백준파이썬그리디 [백준] 11047_동전0 python 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,00... 그리디백준파이썬그리디 [백준] 12927_배수 스위치 python 강호는 전구 N개를 가지고 있다. 전구는 1번부터 N번까지 번호가 매겨져 있으며, 일렬로 놓여져 있다. 전구는 켜져있거나 꺼져있다. 강호는 모든 전구를 끄려고 한다. 강호는 전구를 켜고 끌 수 있는 스위치 N개를 가지고 있고, 스위치도 1번부터 N번까지 번호가 매겨져 있다. i번 스위치는 i의 배수 번호를 가지는 전구의 상태를 모두 반전시킨다. 현재 전구의 상태가 주어졌을 때, 모든 전구를 ... python백준파이썬그리디python 그리디 : 숫자 카드 게임 여러 카드 덱에서 가장 낮은 숫자를 뽑고, 낮은 숫자 중 가장 높은 카드 한장을 뽑은 사람이 승리하는 게임이다. 카드들은 nxm (행 x 열) 형태로 놓여있다 카드를 뽑고자하는 행을 선택 선택한 행 중 가장 낮은 카드 뽑아야함 낮은 카드 중 최종적으로 가장 높은 카드를 뽑은 사람이 승리 🥕입력예시 : 첫줄에는 행과열, 그 뒤에는 카드들 주어짐 🥕출력예시 각 행마다 가장 작은 수를 찾은 뒤에 ... 그리디알고리즘코딩테스트그리디 BOJ 9237번 이장님 초대 파이썬 농부 상근이는 마당에 심기 위한 나무 묘목 n개를 구입했다. 묘목 하나를 심는데 걸리는 시간은 1일이고, 상근이는 각 묘목이 다 자라는데 며칠이 걸리는지 정확하게 알고 있다. 상근이는 마을 이장님을 초대해 자신이 심은 나무를 자랑하려고 한다. 이장님을 실망시키면 안되기 때문에, 모든 나무가 완전히 자란 이후에 이장님을 초대하려고 한다. 즉, 마지막 나무가 다 자란 다음날 이장님을 초대할 것이... 백준알고리즘그리디그리디 BOJ 1826번 연료 채우기 파이썬 성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 1km를 가는데 1L의 연료가 새 나가게 되었다. 이것을 고치기 위해서는 가장 가까운 마을에 가야 한다. 그런데 그냥 가다가는 중간에 연료가 다 빠질 수가 있다. 다행스럽게도 정글 곳곳에 연료를 채울 수 있는 주유소가 N개 있다. 그런데 정글 속에서 중간에 차를 멈추는 행위는 매우 위험한 행위이므로 주유소에서 멈추는... 백준알고리즘우선순위 큐그리디그리디 BOJ 17521번 Byte Coin 파이썬 실제로는 바이트 코인 가격을 예상할 수 없지만 이 문제에서는 바이트 코인 가격 등락을 미리 정확히 예측할 수 있다고 가정하자. 우리는 1일부터 n일까지 n일 동안 그림 1과 같이 바이트 코인의 등락을 미리 알 수 있으며 우리에게는 초기 현금 W가 주어져 있다. 그림 1의 빨간색 네모는 해당 일자의 바이트 코인 가격을 나타낸다. 매일 바이트 코인을 매수하거나 매도할 수 있다고 하자. 우리는 n... 백준알고리즘그리디그리디 BOJ 2720번 세탁소 사장 동혁 파이썬 간단한 브론즈 문제인데 부동소수점 타입 계산할 때 생기는 오차 때문에 꽤 시간을 소용했다. 미국으로 유학간 동혁이는 세탁소를 운영하고 있다. 동혁이는 최근에 아르바이트로 고등학생 리암을 채용했다. 거스름돈의 액수가 주어지면 리암이 줘야할 쿼터(Quarter, $0.25)의 개수, 다임(Dime, $0.10)의 개수, 니켈(Nickel, $0.05)의 개수, 페니(Penny, $0.01)의 개... 백준알고리즘그리디그리디 [BOJ] 2839번: 설탕배달(Java) 가장 적은 수의 봉지로 배달하기 위해서는 5kg의 봉지로 가져갈 수 있는 만큼 최대한 가져가야 한다. 코드... 그리디그리디 백준 1082, 방 번호 - DP, Greedy, 문자열 1) DP 배열 정의: String[] dp dp[cost]: cost원 금액 내로 만들 수 있는 최대 숫자 문자열 출력, 최대 숫자: BigInteger(dp[m]) => dp[] 원소에 Leading-Zero 문자열이 저장될 수 있으므로, BigInteger를 이용하여 Leading-Zero 문자열을 제거 BigInteger 클래스 int, long 범위를 넘어가는 매우 큰 정수를 사용,... DPString백준 1082 방 번호알고리즘그리디greedydynamic programming동적 계획법코딩 테스트DP [Lv2] 큰 수 만들기 문제 풀이... 그리디그리디 [JO] 1828번: 냉장고(Java) 한 냉장고의 화학물질을 최대로 담아야 하므로 '그리디' 알고리즘 적용 화학물질의 최저 보관온도와 최고 보관 온도를 저장할 Material 클래스 선언 Material클래스에 Comparable를 implement하여 max값에 따라 오름차순으로 정렬될 수 있도록 함. 오름차순 정렬 후, Max를 첫번째 원소의 max값으로 저장. mat[i]의 min 값이 현재 max값보다 클 경우 같이 저장... 그리디그리디 [BOJ] 11000번 강의실 배정(java) 우선순위 큐(PriorityQueue) 활용 우선순위 큐란? 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조 문제에서는 강의가 가장 일찍 끝나는 강의실이 우선순위로 배정되어야 함(PriorityQueue Default) 강의의 start와 end를 int[]로 입력받아 저장.끝나는 시간을 기준으로 오름차 순 정렬.첫 번째... 그리디그리디 [백준/ 파이썬] 1105 팔 백준 1105번 팔 이번에 풀어볼 문제는 1105번 팔 문제입니다. 1105번 문제는 최적의 해를 찾는 그리디 문제입니다. 문제를 이해하는데에는 크게 어려움이 없고 머릿속으로 이렇게 저렇게하면 되겠다는 생각이 들것입니다. 우선 크게 보면 자릿수가 같을때와 자릿수가 다를때를 생각할 수 있습니다. 자릿수가 다르다면 8은 필요하지 않을것입니다. 그래서 우리가 생각을 해줘야 하는 부분은 자릿수가 같... 그리디백준1105파이썬1105 백준 1461, 도서관 - Greedy 모든 책을 제자리에 놔둔 후, 다시 원점 0 으로 돌아올 필요 X => 가장 먼 거리의 m개 책을 마지막에 놔두고 종료해야 함 1) 각 책의 위치 리스트를 거리가 먼(절댓값이 큰) 순으로 정렬 음수 위치 리스트, 양수 위치 리스트 각각 나누어 저장 및 정렬 => 원점을 기준으로 서로 반대편(음수, 양수)에 있는 책들은 왕복을 각각 수행하므로 e.g. 한 번에 들 수 있는 책이 2권이고 남은 ... 그리디greedy백준 1461 도서관알고리즘코딩 테스트greedy 백준 18310 - 안테나 일직선 상의 마을에 여러 채의 집이 위치해 있다. 이중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 결정했다. 효율성을 위해 안테나로부터 모든 집까지의 거리의 총 합이 최소가 되도록 설치하려고 한다. 이 때 안테나는 집이 위치한 곳에만 설치할 수 있고, 논리적으로 동일한 위치에 여러 개의 집이 존재하는 것이 가능하다. 집들의 위치 값이 주어질 때, 안테나를 설치할 위치를 선택하는... 백준그리디그리디 백준 1105, 팔 - Greedy 1) L 의 전체 자릿 수 != R 의 전체 자릿 수인 경우 8의 최소 개수는 0 2) L 의 전체 자릿 수 == R 의 전체 자릿 수인 경우 높은 자릿 수 부터 각 동일 자릿 수를 비교하여, 8로 같은 자릿 수의 개수 두 자릿 수가 다르면, 비교 종료 ex) 800, 899 => 1 (백의 자리 8) 8808, 8880 => 2 (천의 자리 8, 백의 자리 8) 1208, 1288 => 0... 그리디greedy알고리즘코딩 테스트백준 1105 팔greedy 백준 2437, 저울 - Greedy, 누적 합 n개의 추들의 조합으로 만들 수 없는 최소 무게 구하기 ① n개 추들의 조합으로 만들 수 있는 "최대 무게" = 모든 추들의 무게 합 ② n개 추들의 조합으로 만들 수 없는 "최대 무게" = 모든 추들의 무게 합 + 1 ③ 작은 무게 ~ 큰 무게 순으로 정렬했을 때, 인접한 추 끼리 무게 차이가 작아야 더 촘촘히(?) 추의 무게 합 구성 가능 n개 추들을 무게 작은 순으로 정렬 ①에서 유추한... 그리디greedy누적 합알고리즘백준 2437 저울코딩 테스트greedy 백준 1092, 배 - Greedy 각 크레인의 최대 무게 리스트, 각 박스의 무게 리스트를 큰 순으로 정렬 가장 큰 무게의 박스, 가장 큰 무게의 크레인부터 확인 1) 해당 박스를 해당 크레인으로 옮길 수 있는 경우 해당 박스를 박스 리스트에서 삭제 다음 박스, 다음 크레인 확인 2) 해당 박스를 해당 크레인으로 옮길 수 없는 경우 다음 박스(현재 해당 박스 이하의 무게)를 현재 크레인으로 옮길 수 있는지 확인 => 모든 크... 그리디greedy백준 1092 배알고리즘코딩 테스트greedy 1783번 병든 나이트 파이썬 병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자. 병든 나이트가 여행에서 방문할 수 있는 칸의 개수중 최댓값을 출력한다. 최대로 많이 방문할 수 있는 최댓값을 구하는 것 이동방식 ... 백준조건분기알고리즘그리디그리디 백준 20115, 에너지 드링크 - Greedy 규칙에 따라 합친 최종 에너지 드링크의 양을 최대로 만들기 => 절반을 버리고 합치므로, 절반을 버리는 드링크는 양이 작아야 함 규칙: 가장 작은 양의 드링크의 절반을 가장 큰 양의 드링크에다 부어서 합치기 => 가장 큰 양의 드링크가 계속 늘어나면서 갱신됨 1) 드링크 양 배열을 작은 순으로 정렬 2) 가장 큰 양(배열의 맨 뒤 원소)을 선택하여, 맨 앞의 작은 양부터 차례로 합쳐나감 in... 그리디greedy알고리즘백준 20115 에너지 드링크코딩 테스트greedy 백준 1715, 카드 정렬하기 - Greedy n개 카드 묶음의 경우, 총 (n-1)번 합침 2개 카드 묶음을 합치고, 합쳐진 카드 묶음은 또 다시 다른 카드 묶음과 합침 => 최소 비교 횟수로 모두 합치려면, 적은 카드 묶음끼리 합쳐나가야 함 => 각 카드 개수를 우선순위 큐에 저장 및 정렬해가면서 합침 1) PriorityQueue에 각 묶음의 카드 개수를 저장하여 정렬 카드 개수 적은 순으로 정렬 2) PriorityQueue에 원... 그리디greedy알고리즘백준 1715 카드 정렬하기코딩 테스트greedy 1080번 행렬 파이썬 만약 A를 B로 바꿀 수 없다면 -1을 출력한다. 최적 부분 구조: 각 부분 문제의 최적해만 있으면, 전체 문제의 최적해를 쉽게 얻어낼 수 있을 경우 최적 부분 구조 조건을 성립한다고 함 탐욕적 선택 속성: 탐욕적으로만 선택을 해도 최적해를 구할 수 있음. <예를 들어 도착했을 때 최댓값을 구하려고 할 때, 맞닥뜨리는 양갈래길마다 값이 큰 길만 선택> 다른 특징으로는, 한번 선택한 것은 번복... 백준알고리즘그리디그리디 백준 7983, 내일 할거야 - Greedy e.g. 예제 1에서 과제1의 종료일은 7일, 과제2의 종료일은 8일로 서로 안겹치게 배치됨 1) 과제 객체(과제 소요일 d_i, 과제 마감일 t_i) 배열을 정렬 과제 마감일(t_i)이 큰 순(뒷 일자가 먼저 오도록 늦은 순)으로 정렬 2) 마감일이 큰 과제부터 과제 (시작 일자, 종료 일자)를 지정 조건 ①: [기본 조건] 현재 과제의 종료 일자 <= 현재 과제의 마감일 현재 과제의 종료... 그리디greedy알고리즘백준 7983 내일 할거야코딩 테스트greedy 2847번 게임을 만든 동준이 파이썬 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어의 점수는 레벨을 클리어하면서 얻은 점수의 합으로, 이 점수를 바탕으로 온라인 순위를 매긴다. 동준이는 레벨을 난이도 순으로 배치했다. 하지만, 실수로 쉬운 레벨이 어려운 레벨보다 점수를 많이 받는 경우를 만... 백준알고리즘그리디그리디 1543번 문서검색 파이썬 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다. 세준이는 ... 백준문자열알고리즘그리디그리디 이전 기사 보기