그리디18 [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]670. Maximum Swaps 문제 요약알고리즘 분류: 구현, 브루드 포스, 그리디난이도: Medium문제내용:숫자 num이 주어지고 두개 숫자 변경 해서 최대 값을 구하여라사이트 주소: https://leetcode.com/problems/maximum-swap/문제풀이이번 문제는 숫자 2개만 바꿔서 그 중 최대 값만 반환 하기 때문에 어렵지 않다고 생각하낟. 그래서 아래 처럼 구현만 된다.숫자를 배열 또는 리스트로 만든다. 그리고 num값을 최대값으로 지정 한다.이중 for문 돌려서 i는 0 ~ 배열 크기 -1, j는 i + 1 ~ 배열 크기 만큼 돌린다.i, j 바꾸고난뒤 숫자로 변환 한뒤 이전 최대 값과 비교하여 그중 큰 값으로 저장 한다. 위 처럼 구현하면 시간 복잡도는 num의 자리수를 N이라고 볼면 O(N^2)만큼 나온.. 2025. 3. 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. [BAEKJOON]27961 고양이는 많을수록 좋다 문제 요약알고리즘 분류: 그리디난이도: Broze1문제내용:다음중 2가지 마법만 사용 할수있다.생성 마법: 고양이 1$1$마리를 마도카의 집에 생성한다.복제 마법: 현재 k개 있으면 k마리 이하만 복제 가능하다.사이트: https://www.acmicpc.net/problem/27961문제풀이 이번 문제는 전체 경우의 수를 탐색하기에는 10^12승 숫자 만큼 탐색하면 시간 초과가 나서 안될것이다. 그래서 O(logN)만큼 나오도록 구현 해야 한다. 그래서 이 문제는 그리디로 접근해야 한다. 그리디에 관련 내용은 아래글에서 확인해보면된다.https://jih3508.tistory.com/70 [알고리즘 이론] 그리디(Greedy)이론 그리디 알고리즘은 탐욕 알고리즘이라고 부르기도 한다. 즉, 매 순간 선택.. 2024. 11. 10. [Leetcode]1007. Minimum Domino Rotations For Equal Row 문제 요약알고리즘 분류: Greedy난이도: Medium문제내용:tops, bottoms 같은 길이 주사위 배열을 준다.tops[i], bottoms[i] 같은 index위치끼리 바꿀수 있다.top과 bottom을 바꾸면서 top이나 bottom중에서 같은 주사위 숫자가 같게 만들수 있을때 최소 몇번 바꾸면되는지 반환 하여라 만약 안될 경우 -1로 반환 하여라사이트 주소: https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/description/문제풀이모든 경우의 수로 답은 나오지 브루드포스로 풀경우에는 시간 초과가 나올것이다. 그래서 이번문제는 그리디로 풀어야 한다. 그리디 관련 설명은 아래글을 확인 해보면된다.https://ji.. 2024. 9. 23. [Leetcode]807. Max Increase to Keep City Skyline 문제 요약알고리즘 분류: 배열, 그리디난이도: Medium문제내용:가로, 세로 같은 크기 2차원 배열을 준다.각 배열 건물 높이 크기 값을 준다.동, 서, 남, 북으로 봤을때 스카이라인기준으로 건물 높이 올리라고한다.도시의 스카이라인을 변경하지 않고 건물 높이의 합계를 최대로 증가 시킬 수 있는 값을 반환 하여라사이트 주소: https://leetcode.com/problems/minimum-number-of-operations-to-make-word-k-periodic/description/문제풀이 이번 문제는 그리디 활용 하는 문제다 그리디 관련 내용은 아래 글을 확인 하면 된다.https://jih3508.tistory.com/70 [알고리즘 이론] 그리디(Greedy)이론 그리디 알고리즘은 탐욕.. 2024. 8. 1. 이전 1 2 3 다음
