📝 Greedy(일반)
❌ 11509번 : 풍선 맞추기 (골드5)
- 문제 유형 : greedy
- 시간 복잡도 : O(n)
- 풀이 방식 :
- 높이별 존재하는 풍선의 개수를 저장하는 dp 배열 이용
- 풍선의 위치를 순서대로 입력받을 때 현재 위치보다 앞선 풍선 중에 높이가 1 높은 풍선이 존재하면 다트가 날아오면서 현재 풍선은 자연스럽게 터지게 되기 때문에 선행 높이의 풍선 수를 줄이고 현재 높이의 풍선 수를 1 증가시킴
- 높이가 1 높은 선행 풍선이 존재하지 않으면 다트를 무조건 하나 더 던저야 현재 풍선이 터지기 때문에 총 다트 수를 증가시킴
❌ 2879번 : 코딩은 예쁘게 (골드2)
- 문제 유형 : greedy
- 시간 복잡도 : O(n)
- 풀이 방식 :
- 첫 풀이법에서 너무 복잡하게 생각하여 3중 for문 코드를 생각했는데 심지어 답도 틀림
- 첫 번째 배열 값에서 두 번째 배열 값을 빼내어 새로운 배열에 저장
- 직전 값과 비교해야하기 때문에 0번째 값을 prev로 두고 1번째 인덱스부터 시작 (결과값에 0번째 값의 절대값을 미리 더함)
- *prev와 현재 값을 곱했을때 0보다 작을 경우 탭의 변화 방향이 반대인 것이기 때문에 현재 값을 결과값에 바로 더함
- *0보다 작지 않을 경우 현재값이 prev 값보다 클 경우 그 차이만큼 결과값에 더하고, 반대의 경우 직전값과 그룹화되어 탭이 적용되기 때문에 고려하지 않아도 됨 (연속된 줄들을 그룹화 할 수 있기 때문에 prev 값과만 비교해도 됨)
⭕️ 3109번 : 빵집 (골드2)
- 문제 유형 : greedy, graph, dfs
- 시간 복잡도 : O(V+E)
- 풀이 방식 :
- 맨 왼쪽 열의 한 노드부터 맨 오른쪽 열의 한 노드까지 서로 겹치지 않고 이어지는 경로의 최대 개수를 구하는 문제이기 때문에 dfs 사용
- 어느 한 노드에서 바로 오른쪽 열의 노드로 갈 수 있는 경우의 수는 오른쪽 대각선 위, 오른쪽, 오른쪽 대각선 아래 3가지
- 맨 위쪽 행부터 시작하여(stack에 넣는 순서도 반대로하면 반대여도 무관) 경로를 찾을 경우 최대한 위쪽에 치우친 경로를 만들어야 이후 경로에 영향을 끼칠 확률이 줄어들기 때문에 오른쪽 대각선 아래, 오른쪽, 오른쪽 대각선 위 순으로 stack에 add(stack은 후입선출 방식이기 때문)
- stack에 push할때 visit을 true로 체크 할 경우 이후 다른 경로를 택 해야할 경우 사용하지 않는 노드 또한 방문한 것이 되기 때문에 stakc에서 pop한 후 다음 경로가 존재하는 경우에만 visit을 true로 체크
- stack에서 pop한 노드의 위치가 맨 오른쪽 열일 경우 조건에 만족하는 경로가 이어진 것이기 때문에 경로 개수를 증가
⭕️ 1931번 : 회의실 배정 (실버1)
- 문제 유형 : greedy, sort
- 시간 복잡도 : O(n)
- 풀이 방식 :
- 회의 배열을 종료 시점을 기준으로 오름차순 정렬
- 오름차순 된 배열의 첫 번째 값(가장 먼저 끝나는 회의)를 기준으로 이후 회의들과 비교하여 기준 회의의 종료 시점보다 비교 회의의 시작 시점이 빠르다면 무시하고, 시작 시점이 늦는다면 기준 회의를 비교 회의로 변경하고 사용가능한 회의 개수를 증가시켜 최대값을 구함
⭕️ 2195번 : 문자열 복사 (골드5)
- 문제 유형 : greedy, string
- 시간 복잡도 : O(n)
- 풀이 방식 :
- 두 번째 문자열을 한 글자씩 첫 번째 문자열 전체와 비교
- 비교 중 현재 글자와 동일한 글자를 찾았으면 해당 위치부터 두 문자열이 연속적으로 동일한 문자를 가지는 개수를 카운팅
- 동일한 문자열의 길이 중 가장 긴 길이만큼 두 번째 문자열의 글자 인덱스를 건너뜀
- 부분 문자열의 개수(복사 횟수)를 출력
⭕️ 13164번 : 행복 유치원 (골드5)
- 문제 유형 : greedy, sort
- 시간 복잡도 : O(n)
- 풀이 방식 :
- n명의 사람으로 k개의 그룹을 만들기 위해선 n-k번 합쳐야 함
- 각 그룹의 최대 키와 최소 키의 차는 키가 인접한 어린이들의 키 차이를 모두 더한 것과 같음
- 따라서 어린이들의 키 차이를 배열에 저장하고 오름차순으로 정렬하여 가장 작은 키 차이 n-k개를 선택하면, 가장 큰 어린이와 가장 작은 어린이의 키 차이의 총 합이 가장 작은 그룹 k개를 만드는 것과 같게 됨
⭕️ 1092번 : 배 (골드5)
- 문제 유형 : greedy, sort
- 시간 복잡도 : O(nmlogm)
- 풀이 방식 :
- 크레인 정보와 박스 무게 정보를 입력 받아 각각 리스트에 저장
- 두 리스트을 무게를 기준으로 내림차순 정렬
- 가장 무거운 무게를 들 수 있는 크레인에 가장 무거운 박스를 들어야 최소 시간안에 모든 박스를 옮김
- 모든 박스를 옮길 때까지 크레인마다 박스 배열을 순회하며 들 수 있는 가장 무거운 박스를 remove (순회시 직전 크레인이 옮긴 박스 다음부터 시작)
- 한 사이클마다 시간을 늘려 구해지는 최종 시간 출력
⭕️ 1461번 : 도서관 (골드5)
- 문제 유형 : greedy
- 시간 복잡도 : O(nlogn)
- 풀이 방식 :
- 최대한 먼 곳부터 옮길 수 있는 책 개수에 맞춰 책을 옮겨야 이동거리를 최소화 시킬 수 있음 (왕복하기 때문에)
- 오른쪽으로 옮겨야되는 책(양수 좌표), 왼쪽으로 옮겨야되는 책(음수 좌표)을 두 개의 배열에 따로 저장하여 오름차순 정렬
- 가장 멀리 옮겨야되는 위치부터(배열의 끝) 거리의 두 배를 총 이동거리에 더하고, 옮길 수 있는 책 개수만큼 인덱스를 줄임
- 위 과정을 두 배열에서 시행하고, 가장 멀리 떨어진 위치는 왕복 할 필요가 없기 때문에 총 이동거리에서 뺌
⭕️ 2212번 : 센서 (골드5)
- 문제 유형 : greedy, sort
- 시간 복잡도 : O(n)
- 풀이 방식 :
- 13164번 행복 유치원과 동일한 풀이 방법
⭕️ 2513번 : 통학버스 (골드3)
- 문제 유형 : greedy, sort
- 시간 복잡도 : O(nlogn)
- 풀이 방식 :
- 버스의 이동거리를 최소화 하기 위해선 가장 멀리 떨어진 아파트 단지로 최대한 적게 이동해야 함
- 즉, 현재 시점에서 가장 멀리 떨어진 아파트 단지에 갈 때 버스를 가득 채워 학생들을 옮겨야 하므로 멀리 떨어진 아파트 단지부터 학생들을 옮김
- 학교를 기준으로 왼쪽에 있는 단지, 오른쪽에 있는 단지를 나누어 학교로부터 떨어진 거리를 기준으로 내림차순 정렬하는 두 개의 우선순위 큐에 각각 넣음
- 가장 먼 학교에서 학생들을 최대한 버스에 태웠음에도 자리가 남아있다면 그 다음으로 먼 학교에서 학생들을 남은 자리에 태워 오고 떨어진 거리 2배 값을 총 이동거리에 더함 (경로 상에 있는 학교에 들리는 건 이동거리에 영향이 없음)
- 위 과정을 왼쪽 오른쪽 각각 진행하여 구해진 총 이동거리를
⭕️ 8980번 : 택배 (골드2)
- 문제 유형 : greedy, sort
- 시간 복잡도 : O(nm)
- 풀이 방식 :
- 택배 박스 정보를 저장하는 배열과 각 마을을 지나갈 때 트럭에 담겨있는 택배의 최대 박스 수를 저장하는 배열을 이용
- 택배 박스 배열을 받는 마을번호 기준으로 오름차순 정렬
- 정렬한 순서대로 각 택배의 시작마을부터 도착마을 직전까지 트럭에 담겨있는 최대 택배 박스 수를 찾음
- 택배를 실을 경우 택배 박스 수와 최대 박스 수를 합친 수가 트럭 용량이 넘치면 용량에 맞게 일부 택배를, 넘치지 않으면 모든 택배 박수 수를 경로 상의 최대 박스 수 배열에다가 각각 더하고 배송 가능한 박스 수에도 카운팅함
⭕️ 2457번 : 공주님의 정원 (골드3)
- 문제 유형 : greedy
- 시간 복잡도 : O(nlogn)
- 풀이 방식 :
- 피는 날짜를 기준으로 꽃을 오름차순 정렬하는 우선순위 큐 이용
- 3월 1일을 시작으로 현재 꽃이 피어있는 마지막 날짜(한계 날짜)를 3월 1일으로 설정하고 시작하여, 우선순위 큐에서 피는 날짜가 꽃의 한계 날짜보다 앞서는 모든 꽃을 빼내며 비교하여 가장 늦게 지는 꽃을 찾은 후 한계 날짜를 찾은 꽃의 지는 날짜로 바꿈
- 한계 날짜가 이전과 같으면 더 이상 11월 30일까지 이을 수 있는 꽃이 없는 것이기 때문에 0 출력
- 위의 과정을 한계 날짜가 12월 달이 될 때까지 반복하고 사용된 꽃의 개수를 출력
❌ 1700번 : 멀티탭 스케줄링 (골드1)
- 문제 유형 : greedy
- 시간 복잡도 : O(n^2)
- 풀이 방식 :
- 첫 번째 시도에서 입력과 동시에 멀티탭을 채우는 방법을 사용했는데 멀티탭에 빈 자리가 있을 때 이미 사용중인 전기용품인지를 체크하지 않고 채워넣어 실패 (멀티탭이 꽉 차 있을때만 체크하는 실수)
- 멀티탭이 가득 찰 때까지 전기용품을 채워넣으며 boolean 배열을 이용해서 꽂혀있는 전기용품을 체크
- 멀티탭이 가득 찬 상태라면 꽂혀있는 전기용품 중 이후 다신 사용하지 않는 기기가 1순위, 이후 사용 순서가 가장 나중인 기기가 2순위로 멀티탭에서 뽑은 뒤 다음 전기용품을 멀티탭에 꽂음
- 리스트 배열을 이용해서 각 기기별로 이후 사용 순서를 저장하여 뽑을 기기를 선택할 때 만약 해당 기기의 리스트가 비어있으면 이후 사용할 일이 없음을 뜻하고, 비어있는 기기가 없다면 각 리스트의 첫 번째 값을 비교하여 가장 큰 값(가장 나중에 사용)을 가진 기기를 찾음
- 이미 꽂혀있는 기기면 넘어감
- 위 과정을 전기용품 사용 스케줄을 모두 완료할 때까지 반복하며 멀티탭에서 전기용품을 뽑는 횟수를 증가시킴