그리디알고리즘
-
[백준] 18004 From A to B with PythonPS 2022. 5. 15. 02:03
📌 BOJ 18004 From A to B 💡 조건 두 개의 정수인 a와 b가 입력된다. 일련의 작업을 수행하여 a를 b로 만들려고 한다. 다음의 두가지 작업만 할 수 있다. 짝수인 경우에만 2로 나누기. 1 더하기 (1 ≤ a , b ≤ 10 9 ) a 를 b 로 변환하는 데 필요한 주어진 연산의 최소 횟수를 출력하는 문제 수학, 그리디 알고리즘, BFS 유형의 문제 🖥 소스 코드 from collections import deque from sys import stdin a, b = map(int, stdin.readline().split()) def solve(): q = deque() if a b: if now % 2 == 0: q.append((cost + 1, now // 2)) else: q..
-
[백준] 12970 AB with PythonPS 2022. 5. 9. 20:52
📌 BOJ 12970 AB 💡 조건 문자열의 길이 n 0 ≤ i < j < N 이면서 s[i] == 'A' && s[j] == 'B'를 만족하는 (i, j) 쌍의 개수 K 개가 있다. N과 K가 주어진다. (2 ≤ N ≤ 50, 0 ≤ K ≤ N(N-1)/2) 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. S가 존재하지 않는 경우에는 -1을 출력한다. 수학, 그리디 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin n, k = map(int, stdin.readline().split()) def solve(n, k): s = list('B' * n) acnt, curk, lidx = 0, ..
-
[백준] 2012 등수 매기기 with PythonPS 2022. 3. 31. 04:13
📌 BOJ 2012 등수 매기기 💡 조건 2007년 KOI에 N명의 학생들이 참가하였다. 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다. 1등부터 N등까지 동석차 없이 등수를 매겨야한다. 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다. 자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 (|A - B|)로 수치화할 수 있다. 당신은 N명의 사람들의 불만도의 총 합을 최소로 하면서, 학생들의 등수를 매기려고 한다. 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. 그리디알고리즘,..
-
[백준] 1343 폴리오미노 with PythonPS 2022. 3. 29. 17:04
📌 BOJ 1343 폴리오미노 💡 조건 AAAA와 BB 폴리오미노 2개를 무한개만큼 가지고 있다. '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. '.'는 폴리오미노로 덮으면 안 된다. 폴리오미노로 모두 덮은 보드판을 출력하는 문제 보드판의 크기는 최대 50이다. 문자열 유형의 문제 🖥 소스 코드 from sys import stdin p = stdin.readline().rstrip() p = p.replace('XXXX', 'AAAA') p = p.replace('XX', 'BB') if 'X' in p: pri..
-
[백준] 2697 다음수 구하기 with PythonPS 2022. 3. 1. 22:59
📌 BOJ 2697 다음수 구하기 💡 조건 A의 다음수는 A와 구성이 같으면서, A보다 큰 수 중에서 가장 작은 수. A와 B의 구성이 같다는 말은 A를 이루고 있는 각 자리수의 등장 횟수가, B를 이루는 각 자리수의 등장 횟수와 같을 때. 첫째 줄에 테스트 케이스의 개수 T(1 data[idx]: a.append(b.pop(i)) a.extend(b) break print(''.join(map(str, a)))🔖 예제 및 실행결과 예제 3 123 279134399742 987실행결과 132 279134423799 BIGGEST⌨️ 문제 풀이 입력받은 숫자를 역순으로 탐색합니다. 왼쪽에 있는 값이 오른쪽보다 작아질 경우, idx에 해당 인덱스 값을 넣어줍니다. 숫자를 a 와 b 로 나누는데..
-
[백준] 11501 주식 with PythonPS 2022. 2. 24. 18:26
📌 BOJ 11501 주식 💡 조건 홍준이는 요즘 주식에 빠져있다. 아래 세가지 중 하나의 행동을 한다. 주식 하나를 산다. 원하는 만큼 가지고 있는 주식을 판다. 아무것도 안한다. 테스트케이스 수를 나타내는 자연수 T. 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다. 날 별 주가는 10,000이하다. 최대 이익이 얼마나 되는지 계산을 해 출력하는 문제. 그리디 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin for tc in range(int(stdin.readline())): n = int(stdin.readline()) day..