본문 바로가기

그리디7

[Python] 백준 3806 S를 T로 문제 링크 :https://www.acmicpc.net/problem/3806 3806번: S를 T로 첫째 줄에 테스트 케이스의 개수 C (C ≤ 200)가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 첫째 줄에는 '0', '1', '?'로 이루어진 S, 둘째 줄에는 '0', '1'로 이루어진 T가 주어진다. 두 문자 www.acmicpc.net 1. 접근 방법 접은 방법을 조금 고민했는데, 가능한 조건이 많지는 않지만, BFS나 DP로는 적합하지 않을 것 같아 그리디한 방식을 탐색했다. 2. 풀이 코드 🖥python 코드 링크 :https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/3000/3806.py GitHub - mintropy/PS.. 2022. 4. 17.
[Python] 2212 센서 문제 링크 : https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 1. 접근 방법 각 값이 아니라, 각 값의 차이 중 최솟값을 뽑아내는 그리디 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/2000/2200/2212.py GitHub - mintropy/baekjoon_py: BOJ를 Python으로 해결한 코드의 저장소입니다. BO.. 2022. 3. 25.
[Python] 백준 11000 강의실 배정 문제 링크 : https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 1. 접근 방법 시작 끝 시간을 기반으로 간단한 그리디라 생각했는데, 문제를 다시 읽고 보니 전체 강의 실수를 확인하는 조금 번거로울 수 있는 문제였다. 이를 해결하기 위해 heap을 활용하여 가장 빨리 끝나는 시간 기준으로 고민했다. 2. 풀이 코드 🖥python 코드 링크: https://github.com/mintropy/baekjoon_py/blob/master/11000/11000.py 📕코드 해설 시작 시간 기준으로 오.. 2022. 2. 27.
[Python] 백준 13164 행복 유치원 문제 링크 : https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net 1. 접근 방법 정렬을 우선적으로 했고, 그 이후 어떻게 짝을 지어갈지 결정해야 하는데 그 방법에서 조금 고민을 했다 2. 풀이 코드 🖥python 코드 링크: https://github.com/mintropy/baekjoon_py/blob/master/13000/13164.py GitHub - mintropy/baekjoon_py: BOJ를 Python으로 해결한 코드의 저장.. 2022. 2. 27.
[Python] 백준 22965 k개의 부분 배열 문제 링크 : https://www.acmicpc.net/problem/22965 22965번: k개의 부분 배열 4 5 6 / 1 2 3으로 나눈 뒤, 1 2 3 / 4 5 6으로 재배열하면 된다. www.acmicpc.net 1. 접근 방법 간단한 정렬 구조를 묻는 문제라 생각했다. 만약 횟수 제한 또는 한 번에 하려면 몇 조각으로 나누어야 하냐는 문제라면 조금 더 까다로울 수도 있었지만, 제한 없이 반복할 수 있어서 3조각으로 나눌 수 있으면 무조건 가능하다. 3조각으로 나누면 한 개씩 잘라내서 원하는 자리에 넣는 작업만 반복해도 된다. 또한 정렬되어 있으면 1이 되는것은 주어진 예제에서도 알 수 있다. 문제는 언제 2번만 가능한지를 구현하는 것이다. 2. 풀이 코드 🖥python 코드 링크 : h.. 2021. 11. 7.
[Python] 백준 1461 도서관 문제 링크 : https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 1. 접근 방법 마지막 책을 옮긴 후 다시 원점으로 돌아올 필요가 없어서 가장 멀리 있는 위치를 마지막에 가는 것은 어렵기 않게 생각했는데, 세부적 구현에서 많이 고민했다. 최적의 위치를 잘 찾는것이 이 문제의 가장 중요한 부분이라 생각한다. 2. 풀이 코드 🖥python 코드 import sys input = sys.stdin.readline MIIS = lambda: map(int, .. 2021. 10. 27.
[Python] 백준 1398 동전 문제 문제 링크 : https://www.acmicpc.net/problem/1398 1398번: 동전 문제 김형택이 세운 나라의 화폐 체계는 단순하다. 이곳은 동전만 사용하고, 동전은 다음과 같이 다른 값을 가진다. 1, 10, 25, 100, 1000, 2500, 10000, 100000, ... 식으로 나타내면 0보다 크거나 같은 모든 K에 www.acmicpc.net 1. 접근 방법 기본적인 접근은 거스름돈 문제처럼, 해당 금액을 가장 큰 금액으로 채우는 것으로 시작했다. 그런데, 10과 25가 약수 / 배수 관계가 아니라서 일반적인 방법으로 해결하지 못한다. (30일 때, 10 + 10 + 10이 최소이지만, 큰 값 부터하면 25 + 1 + 1+ 1+ 1+ 1으로 최소가 아니게 됨) 그래서 전반적인 .. 2021. 10. 8.

티스토리툴바