BOJ - 그리디

문제 백준 1715번 - 카드 정렬하기 아이디어 고르는 순서가 결과에 영향을 미치는 요인이 된다. 우선순위 큐를 사용한다. 가장 적은 카드 두 묶음을 꺼내서 합한 다음 다시 우선순위 큐에 삽입한다. 위 과정을 우선순위 큐에 카드 묶음이 하나 남을 때까지 반복한다.

백준 1202번 - 보석 도둑매순간, 현재 가방에 넣을 수 있는 보석 중 가장 가치가 높은 보석을 더하는 그리디 알고리즘을 적용하여 해결한다.가방을 오름차순, 보석을 무게 기준으로 오름차순 정렬한다.각 가방에 대해 넣을 수 있는 보석의 가치를 우선순위 큐에 넣는다. 이

백준 1744번 - 수 묶기숫자를 양수와 0을 포함한 음수로 각각 저장한다.양수는 최대한 큰 수끼리 묶어야 하고, 음수는 최대한 작은 수끼리 묶어야 한다.양수를 묶을 때 주의해야 할 것은 1이다. 어떤 수에 1을 곱한 값보다 1을 더한 값이 더 크다.음수를 묶을 때 특

백준 11000번 - 강의실 배정강의를 시작 시간 순, 시작 시간이 같으면 종료 시간 순으로 정렬한다.우선순위 큐를 사용해 강의의 끝나는 시간을 저장한다.강의들을 순회하면서 강의의 시작 시간이 가장 빨리 끝나는 강의의 종료 시간보다 크기가 같으면 큐에서 제거한다.큐에는

백준 2437번 - 저울추 무게를 정렬하여 가벼운 무게부터 탐색할 수 있도록 한다.추의 최소 무게 1을 시작으로 오름차순 정렬된 추의 무게들을 하나씩 더해간다. 이 값을 min이라 한다.현재 추의 무게가 min 값보다 작거나 같다면 이 추를 추가하여 측정할 수 있는 무

백준 12904번 - A와 B현재 상황에 따라 최적의 선택지를 고르는 그리디 알고리즘으로 해결한다.T에서 S로 갈 수 있는지 확인한다.T의 마지막이 "A"면 마지막 문자를 제거한다.T의 마지막이 "B"면 마지막 문자를 제거하고, 뒤집는다.S와 T의 길이가 같아질 때까지

백준 2812번 - 크게 만들기순서를 유지하면서 큰 수가 최대한 앞에 위치하도록 해야한다.스택을 사용하여 스택에 한 자리씩 push 한다.현재 스택에 넣어야 할 숫자가 스택에 마지막에 넣은 숫자보다 크다면 k번 동안 스택에서 pop 한다.이후 스택에 남아 있는 숫자

백준 2212번 - 센서센서의 간격이 최대한 좁은 간격끼리 기지국을 설치하고, 간격이 넓은 구간은 건너뛰는 것이 유리하다.우선 센서를 정렬하여 순서대로 위치하고 하고, diff 배열을 만들어 센서 간의 간격을 구한다.이 diff 배열을 정렬하여 좁은 간격이 앞에 오게

백준 1700번 - 멀티탭 스케줄링(백준 1700번 - 멀티탭 스케줄링)멀티탭에 플러그를 하나씩 꽂으면서 더 이상 멀티탭 구멍이 남지 않은 상태에서 새로운 플러그를 꽂아야 할 때는 곧 다시 사용할 플러그는 남기고, 최대한 나중에 다시 쓰이는 플러그를 제거하는 것이 유리

백준 10775번 - 공항비행기가 도킹할 수 있는 게이트는 제한되어 있다. 1번 비행기는 1번 게이트만, 2번 게이트는 1~2번 게이트만, 3번 게이트는 1~3번 게이트만 된다.그리고 각 게이트는 하나의 비행기만 도킹될 수 있다.가장 많이 도킹이 되려면 해당 게이트가

백준 1041번 - 주사위바닥이 보이지 않는 N^3 크기의 정육면체는 주사위 한면, 두면 최대 세면이 보이는 주사위의 개수가 정해져있다.이를 구하는 과정이 복잡했는데 어쨌든 다음과 같았다.한면이 보이는 경우 \- (N-2)^2(윗부분) + 4(N-2)(N-1)(옆부분

백준 1052번 - 물병예제 입력 2 N=13, k=2로 일단 문제 그대로 따라해봤다.초기 상태1번 재분배 후2번 재분배 후3번 재분배 후이제 재분배 할 수 없다.남은 숫자들이 뭔가 익숙하다. 1101, 즉 13을 이진수로 표현한 값이다.여기서 물병을 하나 추가하면 다

문제 백준 1339번 - 단어 수학 아이디어 현재 선택이 가장 최선의 선택이라고 보는 그리디 관점에서 생각해본다. 각 알파벳의 가중치, 즉 자릿수가 높을수록 높은 숫자를 받는 것이 유리하다. 각 단어의 각 알파벳별로 자릿수의 합을 구한 다음, 높은 자릿수부터 높은

백준 13904번 - 과제우선 점수를 최대한 많이 받기 위해 점수를 기준으로 내림차순 정렬한다.그 다음 가장 많이 받을 수 있는 점수부터 마감일을 넘지 않고 최대한 마감일에 가깝게 해당 과제를 처리한다.예제 입력을 기준으로 위 과정은 다음과 같다.점수 내림차순 정렬점수

백준 1461번 - 도서관걸음 수가 최소가 되기 위해서는 가장 먼 거리를 마지막으로 가서 다시 돌아오는 거리를 줄이는 것이 유리하다.책 위치 좌표를 정렬하여 0에서 가장 먼 거리의 위치를 구한다.위치를 음수와 양수로 나누어서 계산한다. 그리고 책을 최대 M권 들 수 있

백준 2109번 - 순회강연돈을 가장 많이 벌기 위해서는 하루에 한 곳만 강연이 가능하므로 동일한 날에는 강연료가 더 많은 강연을 하는 것이 유리하다.N개의 강연을 일수 오름차순, 일수가 같으면 강연료 내림차순으로 정렬한다.우선순위큐를 준비한다. 우선순위큐의 사이즈가

백준 3019번 - 빵집갈 수 있는 방향이 오른쪽, 오른쪽 위, 오른쪽 아래로 정해져 있고 겹칠 수 없을 때 최대한 많은 파이프라인이 설치되기 위해서는 오른쪽 위, 오른쪽, 오른쪽 아래 순으로 위부터 탐색하는 것이 유리하다.이는 재귀 형태로 구현할 수 있고, 마지막 열

백준 1781번 - 컵라면백준 2109번 - 순회강연 문제와 거의 같은 문제다.동일한 데드라인끼리는 최대한 많은 컵라면을 받아야 한다.데드라인 오름차순, 컵라면 개수 내림차순으로 정렬한다.적은 데드라인부터 우선순위큐에 컵라면을 넣는다.그러다가 우선순위큐의 사이즈가 데드

백준 13164번 - 행복 유치원최소 비용이 되기 위해서는 최대한 키가 비슷한 원생끼리 조를 이루는 것이 유리하다.입력으로 받는 원생들의 키를 순서대로 바로 뒤 원생의 키와 차이를 구한다.(원생들의 키는 정렬되어 입력됨)키 차이 배열을 정렬한다.이 정렬된 키 차이 배열

백준 2138번 - 전구와 스위치처음에는 BFS로 각 전구를 켜고 끄고 모든 경우의 수를 확인해보는 방법을 생각했는데 이 경우 모든 전구에 대해 두 가지 경우의 수를 살펴봐야 해서 최악의 경우 O(2^N)이 된다.따라서 O(N)의 방법이 필요한데, 그리디 알고리즘을 적

백준 2457번 - 공주님의 정원꽃이 피는 날짜를 기준으로 오름차순 정렬한다. 이때 날짜는 계산을 편하게 하기 위해 MMDD 형식으로 저장한다.301(3월 1일)을 시작으로, 해당 날짜 이전에 피기 시작한 꽃들 중 가장 늦게 지는 꽃을 찾아 그 꽃이 지는 날짜를 새로운

백준 13975번 - 파일 합치기3백준 11066번 - 파일 합치기 문제와 같은데 K의 단위가 매우 커져 N^2의 DP 방식으로는 해결할 수 없다.최소비용이 되기 위해서는 가장 적은 비용 두 장씩 합쳐나가는 것이 유리할 것이므로 그리디로 해결할 수 있다.K개의 수를 우

백준 8980번 - 택배박스를 받는 마을번호를 기준으로 오름차순 정렬한다. 왜냐하면 최대한 빨리 트럭에 실었던 박스를 배송해야 최대 박스 수를 구하기 유리하기 때문이다.위와 같이 정렬하면 이동 경로가 뒤죽박죽이 될 수 있기 때문에 각 마을에서 박스를 얼마나 내리는지,

백준 21758번 - 꿀 따기각 장소의 꿀의 양은 모두 정수이므로 벌통과 벌과의 거리를 최대한 길게 하는 것이 최댓값을 구하기에 가장 유리하다.벌통이 끝쪽에 위치하거나, 벌이 양쪽 끝에 있는 경우가 있을 것이다.벌통이 끝쪽에 위치하는 경우 벌1을 반대편 끝쪽에 고정시키

백준 1911번 - 흙길 보수하기앞에서부터 차례대로 덮기 위해 시작 위치를 기준으로 오름차순 정렬한다. 겹치는 웅덩이는 없기 때문에 특별한 조건 없이 정렬하면 된다.최소한의 널빤지를 사용하기 위해서는 길이가 정해진 널빤지로 웅덩이를 덮고 나서 남은 널빤지의 길이를 최대

백준 9576번 - 책 나눠주기책을 최대로 주기 위해서는 선택 범위가 좁은 학생들을 먼저 나눠주고, 선택 범위가 넓은 학생들은 범위가 좁은 학생들이 먼저 받게 한 다음 자신의 넓은 범위를 활용하는 것이 유리할 것이다.m개의 a, b를 입력받아 b를 기준으로 정렬한다.

백준 1092번 - 배그리디하게 무거운 무게를 들 수 있는 크레인이 무거운 박스부터 옮길 수 있도록 한다.크레인 무게 제한과 박스의 무게를 정렬한다. 만약 가장 무거운 박스의 무게가 가장 무거운 무게를 들 수 있는 크레인의 무게 제한보다 무거우면 절대 모든 박스를 옮길

백준 1374번 - 강의실강의실을 최대한 적게 사용하기 위해서는 강의 시간이 겹치는 것을 최소화 해야 유리하다.N개의 강의 정보를 입력받고 시작 시간 순으로 정렬한다. 정렬하는 이유는 끝나는 시간만을 고려하기 위해서다.우선순위큐를 준비해 시작 시간 순으로 정렬된 강의의

문제 백준 1083번 - 소트 아이디어

백준 1931번 - 회의실 배정회의가 최대한 겹치지 않도록 해야 회의의 최대 개수를 구하는데 유리할 것이다.회의를 종료 시간 순으로 정렬한다. 종료 시간이 같으면 시작 시간 순으로 정렬한다. 왜냐하면 회의의 시작시간과 끝나는 시간이 같을 수도 있다라는 조건이 있는데 예

문제 백준 1541번 - 잃어버린 괄호 아이디어

문제 백준 1826번 - 연료 채우기 아이디어

문제 백준 2141번 - 우체국 아이디어

문제 백준 1285번 - 동전 뒤집기 아이디어 > 재귀 호출 무작정 브루트포스로 탐색하면 시간 초과가 발생한다. 모든 행과 열에 대해서 뒤집거나 안 뒤집거나를 따지면 2^40이다. 따라서 행에 대해서만 브루트포스 탐색하고, 열에 대한 확인은 그리디하게 탐색한다.

문제 백준 3687번 - 성냥개비 아이디어 > 가장 작은 수는 DP로 구하고, 가장 큰 수는 그리디 관점에서 구한다. 예상 시간 복잡도 예상 시간 복잡도 : 코드 구현 - 자바 코드 구현 - 파이썬