반응형 백준알고리즘/그리디 알고리즘30 (Python/🥇5)백준알고리즘 2212번 : 센서 문제 바로가기 문제:한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다. 각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다. 편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 .. 2024. 9. 25. (Python/🥇2)백준알고리즘 1587 번: 이분매칭 문제 바로가기 문제:그래프의 최대 매칭 (Maximum Matching)은 두 간선이 같은 정점을 공유하지 않는 간선의 최대 집합을 말한다. 이분 그래프 (Bipartited Graph)는 그래프의 모든 정점을 두 집합 A와 B로 나눌 수 있는 그래프이다. 모든 간선의 끝 점은 A에 하나, B에 하나 있어야 한다. 이분 그래프에서 최대 매칭을 구하는 문제는 Maximum Flow 알고리즘을 이용해서 풀 수 있다. 거의 이분 그래프는 모든 정점이 집합 A = {A1, A2, …, AnA}와 B = {B1, B2, …, BnB}로 나누어져 있고, 모든 간선의 끝 점은 A에 하나, B에 하나있는 그래프이다. 여기까지는 이분 그래프와 동일한 모양을 갖는다. 거의 이분 그래프는 이분 그래프와 다르게 nA-1 + .. 2024. 9. 5. (Python/플3)백준 알고리즘 19073번: Subsequence Sums 문제 바로가기 이 문제는 어떤 수열의 총 길이와 총 합이 주어진다.예를들어 n = 2 m = 3 이면 길이가 2짜리 수열이며 그 수열의 총 합이 3이다 [1,2] 그 예가 될 수 있다. 그리고 B 수열이 주어지는데 B수열은 위에 있는 A 수열의 모든 부분합의 갯수이다 위에 예시로 해보면 n =2 , m = 3 이고 B = 1 1 1 1 이면 빈거, 1, 2, 1+2 이렇게 해서 4개가 나오는데 이것들의 각각의 합과 갯수로 분류하면 1 1 1 1 이렇게 나오는거다문제에서는 가장 작은 수열을 구하라고 하였다. 즉 가장 작은 수부터 찾아가면 되는데 시작값인 0 은 빼준다 모든수에 들어가기 때문에그러면 일단 시작값인 0 은 무조건 들어가니깐 빼주고 처음 들어오는 B 배열을 Counter 함수로 그 숫자가 될.. 2024. 9. 4. (Python/🥈1)백준리즘알고리즘 1080번: 행렬 문제 바로가기 문제:0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오. 행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0)입력:첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.출력:첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다. 풀이 : import syssys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')n, m.. 2024. 6. 15. (Python/🥈5)백준리즘알고 1417번: 국회의원 선거 문제 바로가기 문제:농부 상근이는 마당에 심기 위한 나무 묘목 n개를 구입했다. 묘목 하나를 심는데 걸리는 시간은 1일이고, 상근이는 각 묘목이 다 자라는데 며칠이 걸리는지 정확하게 알고 있다. 상근이는 마을 이장님을 초대해 자신이 심은 나무를 자랑하려고 한다. 이장님을 실망시키면 안되기 때문에, 모든 나무가 완전히 자란 이후에 이장님을 초대하려고 한다. 즉, 마지막 나무가 다 자란 다음날 이장님을 초대할 것이다. 상근이는 나무를 심는 순서를 신중하게 골라 이장님을 최대한 빨리 초대하려고 한다. 이장님을 며칠에 초대할 수 있을까?입력:입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가.. 2024. 5. 18. (Python/🥈5)백준리즘알고 11256번: 사탕 문제 바로가기 문제: 당신은 사탕 공장의 주인이다. 날마다, 당신은 J개의 사탕을 가게에 보내기 위해 상자에 포장해야 한다. 당신은 크기가 다른 상자 N개를 가지고 있다. 당신은 편리를 위해 상자를 최소한으로 쓰려고 한다. (박스를 다 채울 필요는 없다. 일부분만 채워도 된다.) 당신이 공장에서 나오는 사탕의 개수와 각 상자의 크기를 입력받고, 상자를 최소한으로 쓸 때의 사용되는 상자 개수를 출력하는 프로그램을 작성하라. 사탕들을 포장할 공간은 충분하다는 것이 보장된다. 입력: 첫 번째 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각각의 테스트 케이스는 아래 형식을 따른다. 테스트 케이스의 첫 번째 줄에는 사탕의 개수 J와 상자의 개수 N이 주어진다. (1 ≤ J, N ≤ 1,00.. 2024. 3. 4. 이전 1 2 3 4 5 다음 반응형
