본문 바로가기

Greedy10

[Leetcode]984. String Without AAA or BBB 문제 요약알고리즘 분류: 그리디, 정렬난이도: Medium문제내용:.두 정수 a와 b가 주어질 때, 다음 조건을 만족하는 문자열 s를 반환하세요:s의 길이는 a + b이고, 정확히 a개의 'a' 문자와 정확히 b개의 'b' 문자를 포함합니다.부분 문자열 'aaa'는 s에 나타나지 않습니다.부분 문자열 'bbb'는 s에 나타나지 않습니다.사이트 주소:https://leetcode.com/problems/string-without-aaa-or-bbb/description/문제풀이 이번문제는 완전탐색아닌 그리디로 최적의 해로 시간복잡도가 최소화를 할 후 있다.그리디 관련 내용은 아래글로 참고 하면된다.https://jih3508.tistory.com/70 [알고리즘 이론] 그리디(Greedy)이론 그리디 알.. 2025. 4. 14.
[Leetcode]452. Minimum Number of Arrows to Burst Balloons 문제 요약알고리즘 분류:  그리디, 정렬난이도: Medium문제내용:.벽에 붙어있는 풍선들은 [xstart, xend] 형태로 주어지며, x축에서 수직으로 화살을 쏴 터뜨릴 수 있습니다.한 번 발사된 화살은 무한히 위로 이동하며 경로 내 모든 풍선을 터뜨립니다. 모든 풍선을 터뜨리는 데 필요한 최소 화살 개수를 구하세요.사이트 주소: https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/description/문제풀이이번 문제는 완전탐색으로 풀면 O(N^2)나오지만 그러면 시간 초과가 나서 O(N^2)안되는 방법으로 끝내야 한다. 그래서 그리디로 간단하게 풀것이다. 그리디 관련 내용은 아래글로 참고 하면된다.https://jih3.. 2025. 3. 15.
[Leetcode]948. Bag of Tokens 문제 요약알고리즘 분류:  그리디, 투 포인터난이도: Medium문제내용:초기 에너지(initial power)와 초기 점수(initial score) 0을 가지고 게임을 시작한다.수 배열 tokens가 주어지며, 이 배열의 tokens[i]는 각 토큰의 에너지 값을 나타낸다.각 토큰은 한 번만 사용할 수 있으며, 다음 두 가지 방법 중 하나로 사용할 수 있습니다앞면: 현재 에너지가 tokens[i] 이상인 경우, 토큰 tokens[i]를 사용하여 에너지를 tokens[i]만큼 잃고 점수를 1 증가시킬 수 있습니다.뒷면: 현재 점수가 1 이상인 경우, 토큰 tokens[i]를 사용하여 점수를 1 잃고 에너지를 tokens[i]만큼 얻을 수 있습니다.최대 점수를 반환 하여라사이트 주소: https://le.. 2024. 12. 1.
[BAEKJOON]14916 거스름돈 문제 요약알고리즘 분류: 그리디난이도:  Silver5문제내용:2원, 5원 동전으로 거스름 돈을 줄수 있다.거스름돈이 N일때 최소 동전 개수를 구하여라(안되면 -1로 출력하여)사이트: https://www.acmicpc.net/problem/14916  문제풀이 이번 문제는 전체 경우의 수를 탐색하기에는 최대 거스름돈이 10만이라서 모든 경우의 수를 구하면 시간 초과가 나서 O(N) 탐색으로 푸는 방법을 찾아야 될것이다. 그래서 이번 문제는 그리디로 풀것이다. 그리디에 대한 설명은아래글로 확인 해보면 된다.https://jih3508.tistory.com/70 [알고리즘 이론] 그리디(Greedy)이론 그리디 알고리즘은 탐욕 알고리즘이라고 부르기도 한다. 즉, 매 순간 선택할때 가장 좋은것을 선택하는 알.. 2024. 11. 10.
[Leetcode]3111. Minimum Rectangles to Cover Points 문제 요약알고리즘 분류: 그리디난이도: Medium문제내용:2차원 배열 points, points[i] = [xi, yi] 와 정수 w가 주어진다. w는 사각형 가로 길이이다.사각형의 범위가 (x`, 0) , (x` + w, 0), (x`, y`), (x` + 2, y`)로 이루어 진게 몇개가 있습니다.각 points 사각형안에 포함이 되어 있습니다. 모든 점이 사각형 안에 포함 될때 최소 몇 개 사형이 필요한지 반환 하세요.사이트 주소: https://leetcode.com/problems/minimum-rectangles-to-cover-points/description/문제풀이  이번 문제는 모든 경우의 수로 구하면 시간초과가 날것이다. 그래서 최적의 시간내로 풀수 있는 그리디로 풀어야 통과가 되는.. 2024. 6. 26.
[Leetcode] 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers 문제 요약 알고리즘 분류: 그리디, 수학 난이도: Medium 문제내용: 각 자리수는 0과 1만 올수 있다. 숫자 N을 주어 줬을때 0, 1만 오는10진수 조합된 숫자로 최소 몇번 더하면 되는지 구하여라. 사이트 주소: https://leetcode.com/problems/partitioning-into-minimum-number-of-deci-binary-numbers/description/ 문제풀이 이번 문제에는 그리디 문제이다. 그리디 관련 자세한 내용은 아래 글에서 참고 하면된다. https://jih3508.tistory.com/70 [알고리즘 이론] 그리디(Greedy) 이론 그리디 알고리즘은 탐욕 알고리즘이라고 부르기도 한다. 즉, 매 순간 선택할때 가장 좋은것을 선택하는 알고리즘이다. 이 .. 2024. 3. 21.