greedy4 [코드트리/C++] 저것도 먹을거란 말이야 (Greedy / Math) 문제https://www.codetree.ai/problems/i-want-to-eat-more/description 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 구상간단히 문제를 보면 내용이 은근 많아서 꽤나 복잡한 문제라고 생각하기 쉽지만,, 본질을 꿰뚫어보면 사실 정말 간단한 문제이다. 나도 헤맨 부분인데, 사실 한 음식에 대해 개수가 다양하게 주어지는데, n일 동안 최대 3번을 먹을 수 있기에 최대 3개로 저장하면 된다. 그렇게 되면, 어제 먹은 맛과는 다른 맛만 먹으면서 n일을 버티면 다이어트 성공!이 된다. 그리고.. 정말 놀라운 점은 해당.. 2024. 9. 9. [백준/C++] #24229 모두싸인 출근길 (Greedy) 문제https://www.acmicpc.net/problem/24229 구상문제를 읽고나서 DP나 greedy 종류의 문제인 것 같았다. 이전에 이동한 곳을 벡터든 변수든 큐든 저장을 해놓고 다음 위치로 이동할 수 있는지 없는지 확인 한 후 이동시키는 거였으니까. 문제는 한 장소에서 이동할 수 있는 유효 거리 안에 판자 여러개가 있을 수 있고, 무조건 가까운 판자를 고르거나 먼 판자를 고르는 것이 정답이 아니라는 점이었다. 그래서 우선순위 큐(max heap)를 사용하여 현재 위치(R)에서 이동할 수 있는 모든 판자를 구하면서 큐에 해당 판자의 R을 넣었다. 그렇게 큐에 원소가 없을 때까지 최종 도달 위치를 가장 먼 곳으로 갱신하다 보면 답이 도출된다. 문제 자체는 쉬웠는데 구현이 좀 빡셌다. 자잘자잘.. 2024. 8. 26. [백준/C++] #1202 보석 도둑 (Greedy) 문제https://www.acmicpc.net/problem/1202 구상k개의 가방을 가지고 있고, 각 가방에 최대 무게 c만큼의 보석 1개를 넣을 수 있는 문제였다. 이때, 가방에 넣어서 훔칠 보석의 최대 가격을 구하는 문제였는데, c무게보다 같거나 가벼운 보석중에 가장 가치가 큰 보석을 하나씩 골라 가방을 하나씩 채워나가면 된다. 그러기 위해서는 우선, 보석 무게와 가방 무게를 오름차순으로 정렬해야 했다. 이후, 가방을 하나씩 돌면서, 가방 무게보다 작은 무게의 보석들을 보면서 가치 하나하나를 max_heap에 넣은뒤, 가방 무게를 초과하기 직전 상태에서 max_heap의 top 가치를 total_value에 넣어야 한다. 중복되는 보석을 max_heap에 넣으면 안되기에 넣을 보석의 인덱스를 .. 2024. 7. 15. [백준/C++] #11000 강의실 배정 (Greedy) 문제https://www.acmicpc.net/problem/11000 구상가장 처음에 왼쪽 그림처럼 2차원 배열을 만들어서 1번 강의실부터 시간들 채워나가며 몇번 강의실까지 사용하는지 알고자 했는데, S와 T의 범위가 10^9로 굉장히 커서 시간 복잡도에서 문제가 생겼다. 그래서 오른쪽 그림과 같은 구상을 했는데, 먼저, 주어진 S와 T를 배열에 넣고, S(시작 시간)기준으로 정렬한다. 그리고, 끝시간은 최소힙에 하나씩 넣고 시작시간과 비교해 시작시간이 최소힙에 있는 끝시간보다 같거나 크면 힙의 top값을 pop하고, 현재 강의 시간의 끝 시간을 최소힙에 넣는다. 남아있는 강의들 중에서 시작 시간이 가장 빠른 강의가 이미 배정된 강의 중에서 가장 끝시간이 빠른 강의 뒤에 올 수 있는지 판단하는 것이.. 2024. 7. 15. 이전 1 다음
