728x90 그리디7 [그리디] 전구와 스위치(Python) 문제링크 https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 1. 핵심 좌우 상태 반전 그리디 유형 같은 곳을 2번 선택하면 선택하지 않는 것과 동일하므로 같은 곳을 2번 선택하지는 않는다. 순차적으로 진행하면서 눌러야하는 위치 판단하는게 유리 첫번째 위치가 선택되는지 안되는지 경우를 나누어서 생각 순차적으로 파악한 후에 마지막 원소가 동일한지 동일하지 않은지 판단한다. 마지막 원소가 같다면 잘 변경된 것이고 마지막 원.. 2024. 2. 18. [그리디] Greedy Algorithm / 자연수 M/2개의 쌍 문제링크 https://www.codetree.ai/missions/8/problems/m2-pairs-of-natural-numbers?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 합들 중 최댓값이 최소가 되도록 하려면 가장 작은 수와 가장 큰 수를 순서대로 매칭하면 된다. 방법1(메모리초과 + 시간초과) 각 값들을 max_heap, min_heap에 넣어서 m // 2만큼 max_q + min_q의 조합하고 조합한 것 중 최대값을 고른다. 문제는 m이 10억이므로 최.. 2024. 2. 16. [그리디] Parametric Search / 폭탄 떨구기 문제링크 https://www.codetree.ai/missions/8/problems/drop-the-bomb?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 이분탐색의 대상이 되는 값 → R R로 결정할 수 있는 것은 바로 주어진 범위를 덮는 폭탄의 개수를 결정한다. 덮어야하는 포인트의 첫 시작은 반드시 폭탄의 범위에 들어가야 하므로 이를 폭탄의 시작점으로 생각한다. 폭탄의 범위에 대한 생각 (R ~ 폭탄 ~ R) 로 생각할수도 있지만 (폭탄 ~ 2 * R)로 생각할 수.. 2024. 2. 15. [그리디] Greedy Algorithm / 폭탄 해체 작업 문제링크 https://www.codetree.ai/missions/8/problems/the-bomb-dismantling?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 핵심: 시간제한이 감소하는 순으로 보며 해당 시간에 선택할 수 있는 폭탄 중 점수가 가장 높은 폭탄을 선택하는 것이 최선이다! 예시 시간제한이 가장 긴 것부터 선택했을 때 가장 최대 이익을 얻을 수 있다. 만약 time 1 때 9를 선택하면 다른 폭탄 8과 2는 선택할 수 없기 때문에 이익이 작아진다. .. 2024. 2. 15. [그리디] Greedy Algorithm / 높은 숫자의 카드가 이기는 게임 문제링크 https://www.codetree.ai/missions/8/problems/a-high-number-of-cards-wins?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 내(A)가 상대편(B)의 카드를 알고 있는 상황. 이 상황에서 내가 상대편(B)를 최대한 이길려면 어떻게 해야하는가? B를 이기려면 B가 가진 카드보다 큰값을 제시해야한다. 우선 정렬은 하는게 훨씬 낫다. 정렬이 정답 유무에 미치지 않기 때문이다. 핵심!! B의 각 카드보다 크면서 내가 가진.. 2024. 2. 13. [그리디] Greedy Algorithm / 자동차 단일 거래 이익 최대화하기 2 [문제그림] 문제링크 https://www.codetree.ai/missions/8/problems/max-profit-of-single-car-2?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 정렬은 불가능하다. 왜냐하면 파는 시점과 사는 시점이 섞일 수는 없기 때문이다. 자동차를 파는 시점 기준(r)으로 그 전(0 ~ r - 1)에 언제 자동차를 사야했는가? 이익을 최대화하기 위해서는 사는 가격을 최소화해야한다. 즉, 파는 시점 기준 첫 날부터 팔기 전 날까지의 가격 .. 2024. 2. 13. 이전 1 2 다음 728x90 반응형