문제 링크 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 요새 취업 시장에서 그리디 문제가 많이 나온다기에 열심히 관련 문제들을 풀고 있습니다! 👨💻 그리디 문제들을 풀다 보면 정렬을 사용하는 그리디와 정렬을 사용하지 않는 그리디가 있고, 여러 자료 구조 중 하나를 선택하여 푸는 그리디가 있는데, 그 중 대표적인 것이 우선순위 큐였습니다. 우선순위 큐를 이용하는 그리디 문제 중에 좋은 문제가 있어서, 하나 포스팅을 해보려고 합니다. 😊 풀이 정렬과 우선순위..
그리디
문제 링크 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 그리디 문제집의 문제들을 살펴보다가, 재밌어 보이는 문제가 있어서 풀어보게 됐습니다. 처음에는 BFS로 풀면 되겠지하고 BFS로 풀어봤는데 모든 경우의 수를 탐색하는 것은 아니어서 틀렸습니다. 질문 게시판을 참고하니 DFS로 풀었다는 글이 다수여서 DFS로 풀었더니 시간초과가 발생했고, vst 배열로 오른쪽 끝까지 갈 수 없는 길을 다시 가지 않도록 최적화했더니 겨우 통과가 되었습니다. 배낭문제같은 그리디 문제만 접하다가 이런 DFS를 활용한 그리디 문제를 접하게 되..
문제 링크 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 제가 요즘 자신없어하는 알고리즘 종류가 그리디 문제입니다. 그래서 그리디 문제를 여러개 풀며 공부하던 도중, 재밌는 문제를 하나 발견해서 풀이를 올려보겠습니다! 풀이 모노톤 스택을 이용해서 그리디로 풀면 됩니다. 모노톤 스택을 한마디로 말하자면, 스택 원소들을 오름차순 또는 내림차순으로 유지시키는 스택입니다. 이 성질을 이용해서, 다음과 같은 과정으로 문제를 풀이했습니다. true면 결과값에 포함하지 않을 chk 배열을 선언합니다. 예를 들면, [1, 2, 3, 4] 이라는 배열이 있고, chk 배열이 [true, true, f..
