본문 바로가기

그리디11

[Java] 알고리즘 투포인터, 그리디, 분할정복 [Java] 알고리즘 투포인터, 그리디, 분할정복 투포인터 투포인터는 주로 배열에서 두 개의 포인트를 만들어서 포인트에 대한 정보를 가지고 데이터를 찾아내는 것이다 투포인터는 양 옆에서 안쪽으로 들어오는 형태로 순회가 가능하다 또한 같은 지점에서 탐색을 할 수 있도록 할 수 있다 기본적으로 문제에 따라 적절하게 사용을 하면 될 것 같다 // ======= 양쪽에서 안 쪽으로 들어오는 방식 ========= // 2개의 숫자를 가지고, target을 만드는 것 private static boolean isPairSum(int[] array, int target) { int left = 0; int right = array.length - 1; while (left < right) { if (array[le.. 2023. 7. 5.
그리디 알고리즘, 원인과 결과 찾기 🧑‍💻 그리디 알고리즘, 원인과 결과 찾기 멀티잇 코딩테스트 러닝클래스'Python 5월반 거스름돈 1, 5, 10, 20, 40 원이라는 동전이 있다 N원을 거슬러 주기 위한 최소의 동전의 개수를 구하는 것 기본적으로 40부터 시작해서, 남은 나머지를 계산해주면 된다 N = int(input()) coin = [40, 20, 10, 5, 1] count = 0 for c in coin: if c temp_end: count += 1 temp_end = end print(count) 2023. 5. 23.
[Python] 백준 25418 정수 a를 k로 만들기 🧑‍💻 [Python] 백준 25418 정수 a를 k로 만들기 Silver 3 - 그리디 A에서 K를 찾는 것이 아닌, K에서 A를 찾는 것이 제일 쉽다 제일 큰 수에서, 짝수이면 2를 나누고, 홀수이면 1을 빼준다 단 짝수에서 2를 나눴을 때에 항상 A보다 커야 한다 문제풀이 K를 A로 만들어야 하고, 2로 최대한 많이 나누어야지, 최소로 연산을 할 수 있다 while 문을 통해 K가 A가 될때까지 순회를 한다 K가 짝수이거나, 2로 나누었을 때 A보다 커야지만 2로 나눌 수 있다 그게 아니고, 홀수이거나 K를 2로 나누었는데, A보다 작으면 계속 1로 빼준 코드 end, start = map(int, input().split()) count = 0 while start != end: if start .. 2023. 2. 10.
[Python] 백준 1083 소트 🧑‍💻 [Python] 백준 1083 소트 Gold 5 - 그리디 문제풀이 최대한 제일 큰 숫자가 앞으로 와야 한다 숫자의 움직임에 제한이 있다 일단 swap만큼의 숫자들을 슬라이스를 통해 슬라이스 안에 제일 큰 숫자를 가지고 온다 그리고 i까지, 뒤로 그 큰 숫자를 앞으로 가지고 온다 이것을 swap이 0이 될때까지 반복을 한다 코드 N = int(input()) array = list(map(int, input().split())) swap = int(input()) for i in range(N): max_num = max(array[i : i + swap + 1]) max_num_index = array.index(max_num) for j in range(max_num_index, i, -1):.. 2023. 2. 1.
[Python] 백준 12931 두 배 더하기 🧑‍💻 [Python] 백준 12931 두 배 더하기 Gold 5 - 그리디 제일 중요하게 생각해야 하는 것은 B에서 배열 A를 만드는 것이다 즉 B에 있는 원소들을 다 0으로 만들어야 하는 것 즉 B에서 값 하나씩 1을 빼는 것 그리고 B에서 모든 값을 2로 나눠서 0을 만드는 것으로 반대로 생각하면 된다 문제풀이 최소를 구하는 것이니깐 모든 값을 2로 나누는 것을 먼저 생각한다 for문을 통해, 모든 숫자가 숫자 % 2 == 0 로 떨어지면, count에 1을 더한다 그리고 for문을 순회할 때에, 각 숫자들을 2로 나눈 것을 temp 리스트에 넣는다 그리고 만약에 for문을 아무 문제 없이 순회를 했다면, temp리스트를 B로 업데이트 한다 반대로 위에서 for문을 통해 순회를 했는데, 홀수를 구한.. 2023. 2. 1.
[Python] 백준 1783 병든 나이트 🧑‍💻 [Python] 백준 1783 병든 나이트 Silver 3 - 그리디 나이트는 무조건 오른쪽으로 움직이는 것을 핵심적으로 생각하면 된다 즉 if문에는 1번부터 4번까지 한번씩 사용을 못 하는 경우들을 넣는다 문제풀이 위의 내용을 if문을 통해 해결을 하면 된다 코드 import math N, M = map(int, input().split()) if N == 1: print(1) elif N == 2: print(min(4, int(math.ceil(M/2)))) elif M 2023. 1. 29.
[Python] 백준 1026 보물 🧑‍💻 [Python] 백준 1026 보물 Silver 4 - 그리디 A는 재배열이 가능하고, B는 재배열을 하면 안 된다고 하지만, 둘 다 정렬을 해야 한다 A는 오름차 순으로, B는 내림차 순으로 정렬을 해야 한다 문제풀이 A는 오름차순으로 B는 내림차순으로 정렬을 한다 즉 나중에 같은 인덱스끼리 곱할 때, A의 작은 수는 B의 큰 수와 곱한다 그리고 그것을 나중에 다 더하면 최소 값이 된다 코드 N = int(input()) A = list(map(int, input().split())) B = list(map(int, input().split())) A.sort() B.sort(key=lambda x: -x) answer = 0 for i in range(N): answer += A[i] * B[.. 2023. 1. 27.
[Python] 백준 1339 단어 수학 🧑‍💻 [Python] 백준 1339 단어 수학 Gold 4 - 그리디 문자열들이 주어진다 문자열들의 알파벳에 숫자를 배정해서, 더해서 최대 수를 만드는 것이다 A에 9를 배정했으면, 모든 문자열에 A가 들어가 있으면, 그 A들은 9이다 문제풀이 문자열을 어떻게 딕셔너리에 넣어서, 어떻게 숫자를 배정할지 많이 고민을 했다 알파벳들이 십의 몇번째 자리인지 찾고, 그 자리에 따라서 내림차순으로 9부터 배정하는 것이다 각 단어들의 알파벳들을 딕셔너리에 넣는다 여기서 10 ** (times - 1)을 하여서, 해당 알파벳이 몇 번째 자리인지 value로 넣는다 그리고 다 구했으면 딕셔너리의 값들을 리스트로 변환해서, 내림차순으로 정렬을 한다 정렬한 리스트를 순회하면서 9부터 내려가면서 곱해주고, result에 .. 2023. 1. 26.
[Python] 백준 1439 뒤집기 🧑‍💻 [Python] 백준 1439 뒤집기 Gold 5 - 그리디 문자열은 0과 1 밖에 없다 연속된 숫자들을 뒤집는 것이고, 최소한으로 뒤집는 것이 목표 즉 0000011111000001100 은 01010 과 똑같다 문제풀이 (처음 풀이, 틀림) one , zero라는 변수를 만들어 0으로 초기화 시켰다 문자열을 순회하며, 문자열이 바뀔 때 마다, 1이면 one에 1을 더하고, 0이면 zero에 1을 더했다 경우의 수 one이 0이고, zero가 0일 때에, 숫자를 뒤집지 않아도 되서 0을 출력 one만 0이면 zero 값인 1을 출력 zero만 0이면, one 값인 1을 출력 zero와 one이 0이 아니면, 둘 중에 작은 것을 출력 문제풀이 (두번째) 000001110000110110 은 010.. 2023. 1. 25.

티스토리툴바