그리디
-
[백준 BOJ/C++] 11497 통나무 건너뛰기알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 9. 17. 23:16
11497번: 통나무 건너뛰기 정렬을 이용해서 그리디(Greedy)한 방법으로 풀 수 있는 전형적인 유형의 문제다. 그리디 알고리즘을 이용해야하는 문제들이 아이디어를 떠올리기만 하면 풀이가 간단해지는데 이 문제 역시 마찬가지다. 하지만 실버1 난이도의 문제인 만큼 핵심 아이디어를 찾기 까다롭지는 않은 편이다. 그림과 같이 통나무들을 원형으로 배치해 하나씩 건너 뛸 수 있게 한다는 컨셉이다. 문제에서 요구하는 것은 통나무들의 순서를 조정해서 바로 인접한 통나무의 높이 차이가 최소가 되어 뛰어다니기 쉽게 만드는 것이다. 각 통나무들의 높이가 주어졌을 때 인접한 통나무들의 높이차이 중 가장 큰 차이를 최소로 만들어 그 값을 출력하면 된다. 단 통나무들은 일직선으로 펼쳐진 것이 아니라 원형으로 양 끝이 연결된 ..
-
[백준 BOJ/C++] 1781 컵라면알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 15. 23:56
1781번: 컵라면 주어진 문제 리스트에서 각 시간당 가장 많은 보상을 얻을 수 있도록 최선의 선택을 해야하는 문제다. 문제 설명이 자세하진 않은 편이라 완전히 이해는데 시간이 좀 걸렸다. 풀고 나면 간단하고 구현도 쉽지만 그리디 문제 답게 접근하는 방법이나 아이디어를 떠올리기가 만만치는 않은 문제다. 한 시간에 한 문제씩 풀 수 있는데 각 문제에는 데드라인이 있어서 해당 시간 내에 풀어야 한다. 즉 반드시 그 시간에 푸는 것이 아니라 데드라인 시간 이전 어느 시간이든 풀 수 있다. 또한 데드라인은 얼마든지 중복될 수 있어서 매 시간마다 어떤 문제를 선택하는지에 따라 총 보상 수가 달라진다. 마치 각 조합을 모두 탐색해 최적해를 찾는 문제처럼 보이기도 하지만 문제의 수 N이 200,000으로 커서 모든 ..
-
[백준 BOJ/C++] 1461 도서관알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 15. 23:28
1461번: 도서관 전형적인 그리디 알고리즘 문제이며 단순하다면 단순한 편이지만 처음 접했을 때 문제를 정확히 이해하지 못했었다. 쉬운 편의 문제라고 할 수 있겠지만 문제 설명이 자세하고 친절하지는 않은 편이라 헤맬 수 있는 문제다. 1차원 수평선 위 0에서 시작해 음수와 양수 구간을 효율적으로 이동시키도록 하는 문제다. 한번에 옮길 수 있는 책 수의 제한이 있어서 다시 시작점인 0으로 돌아오는 것을 고려해야 하는데 마지막에는 돌아오지 않아도 된다. 최소 몇 회 만에 옮길 수 있는지 찾아야 한다. 문제의 포인트 한번에 이동시킬 수 있는 책의 수 돌아오는 구간과 마지막 구간 선택 음수 구간과 양수 구간의 표현 한번에 이동시킬 수 있는 책의 수 수평선에서 좌,우로의 이동을 이용하는 문제이므로 우선 그림과 같..