반응형 백준알고리즘/그리디 알고리즘33 (Python/🥇4)백준알고리즘 30805번: 사전 순 최대 공통 부분수열 문제 바로가기 문제:어떤 수열이 다른 수열의 부분 수열이라는 것은 다음을 의미합니다.해당 수열의 원소들이 다른 수열 내에서 순서대로 등장합니다.예를 들어, {1,1,5}$\{1,1,5\}$는 {3,1―,4,1―,5―,9}$\{3,\underline{\color{blue} 1} ,4,\underline{\color{blue} 1} ,\underline{\color{blue} 5} ,9\}$의 부분 수열이지만, {1,5,1}$\{1,5,1\}$의 부분 수열은 아닙니다.또한, 어떤 수열이 다른 수열보다 사전 순으로 나중이라는 것은 다음을 의미합니다.두 수열 중 첫 번째 수가 큰 쪽은 사전 순으로 나중입니다.두 수열의 첫 번째 수가 같다면, 첫 번째 수를 빼고 두 수열을 다시 비교했을 때 사전 순으로 나중인 .. 2024. 11. 15. (Python/다이아4)백준알고리즘 14186번: 라면 사기(Large) 문제 바로가기 문제:라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i ≤ N).교준이는 아래의 세 가지 방법으로 라면을 구매할 수 있다.i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 B원이 든다.i번 공장과 (i+1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-1). 이 경우 비용은 (B+C)원이 든다.i번 공장과 (i+1)번 공장, (i+2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-2). 이 경우 비용은 (B+2C)원이 든다.최소의 비용으로 라면을 구매하고자 할 때, 교준이가 필요한 금액을 출력하는 프.. 2024. 10. 18. (Python/다이아5)백준알고리즘 18185번 : 라면 사기 (small) 문제 바로가기 문제:라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i ≤ N).교준이는 아래의 세 가지 방법으로 라면을 구매할 수 있다.i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 3원이 든다.i번 공장과 (i+1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-1). 이 경우 비용은 5원이 든다.i번 공장과 (i+1)번 공장, (i+2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-2). 이 경우 비용은 7원이 든다.최소의 비용으로 라면을 구매하고자 할 때, 교준이가 필요한 금액을 출력하는 프로그램을 작성하시.. 2024. 10. 17. (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. 이전 1 2 3 4 ··· 6 다음 반응형
