Greedy
[백준] 13164. 행복 유치원 - Python
[Gold V] https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net 풀이 [백준] 2212. 센서 - Python 와 거의 동일한, 간단한 Greedy 문제. 모든 원생의 키를 오름차순으로 정렬 후, 옆 사람과의 키 차이를 저장하고, 키 차이를 다시 오름차순으로 정렬 후, 맨 뒤에서부터 (K-1)개를 빼고 모두 더하면 된다. K개의 조로 나눈다는 것은, 중간에 키 차이를 무시하고 넘어갈 수 있는 횟수가 K-1번이라는 뜻이라고 생각할 수 있다...
[백준] 1911. 흙길 보수하기 - Python
[Gold V] https://www.acmicpc.net/problem/1911 1911번: 흙길 보수하기 어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N(1 ≤ N ≤ 10,000)개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이가 L(1 ≤ L ≤ 1,000 www.acmicpc.net 풀이 간단한 그리디 문제. 입력된 물웅덩이를 좌표 순으로 정렬한 이후, 모든 물웅덩이를 순회하며, 널빤지를 설치해야 할 경우에 설치한다. 각 순회마다 널빤지의 시작, 끝 좌표를 받고, (line 12) 시작 좌표에 널빤지가 설치되어 있지 않다면, 우선 하나 설치한다. (line 13~15) 그리고, 마지막 좌표를 덮을 때 까지 널빤지를 추가로 설치한다. (..
[백준] 12904. A와 B - Python
[Gold V] https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 풀이 우선 두 가지 연산을 했을 때 어떤 일이 발생하는 지 생각하자. 문자열의 뒤에 A를 추가한다. 이 연산은 단순하게 맨 뒤에 A를 추가할 뿐이다. 문자열을 뒤집고 뒤에 B를 추가한다. 이 연산은 맨 앞에 B를 추가하고 뒤집는 것과 동일한 연산이다. -> (이 때, 문자열을 뒤집는 것을 다르게 생각하면, 문자열은 그대로 두고 뒤에서부터 센다고..
[백준] 3109. 빵집 - C++
[Gold II] https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 풀이 우선, 찬찬히 살펴보면, 첫 번째 열의 모든 칸에서부터, 최대한 많이 마지막 열의 칸으로 연결해야 한다. 이 때, Greedy하게 첫째 열의 맨 위(첫 번째) 칸에서부터 시작해도 되며, 오른쪽 위 / 오른쪽 / 오른쪽 아래 3개의 선택지 중, 오른쪽 위를 선택하는 것이 이후 파이프 연결에서 가장 유리하므로, 또한 Greedy하게 오른쪽 위 - 오른쪽 - 오른쪽 아래 순으로, 가능한 선택지를..
[백준] 2812. 크게 만들기 - 파이썬
[Gold III] https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 한 달여만에 다시 잡은 알고리즘... BFS 풀다 때려치고 Greedy로 도망침. 모든 숫자를 받아놓고.. 앞에서부터 하나씩, Stack에 넣어 가며, K가 남아있는 한 앞에 있는 더 작은 숫자를 greedy하게 모두 pop하는 식으로 진행하면 complete. from collections import deque N, K = map(int, input().split()) num = deque(list(input())) res = deque() fo..
[백준] 1744. 수 묶기 - C++
[Gold IV] https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 풀이 발상 자체는 어렵지 않은 Greedy 문제. 그러나 자잘한 case들을 모두 처리해 줘야 해서 실수할 수 있는 부분이 많았다. #include #include #include #define init cin.tie(0)->ios_base::sync_with_stdio(0); using namespace std; typedef long long ll; int main() { ..
[백준] 1339. 단어 수학 - 파이썬
[Gold IV] https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 딱 봐도 파이썬으로 풀면 편하겠다 싶어서 파이썬으로 조진(?) 문제. 단어를 받아오고, 자릿수에 따른 가중치(?)를 계산 후 내림차순으로 정렬하여 Greedy하게 숫자를 배정해 주었다. AC. N = int(input()) A = dict() words = [] for _ in range(N): word = list(input()) words.append(word) w..
[프로그래머스] 두 큐 합 같게 만들기 - 파이썬
2022 KAKAO TECH INTERNSHIP - 118667. 두 큐 합 같게 만들기 [Lv. 2] https://school.programmers.co.kr/learn/courses/30/lessons/118667 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 deque를 이용해 greedy하게 풀이하면 되었던 문제. 주의할 점은, 반복문 안에서 sum() 을 이용하면, TLE가 날 수 있다는 것! from collections import deque def solution(queue1, queue2): queue1 = deque(queue1)..