반응형 탐욕 알고리즘11 [C/C++] 백준 #2529 부등호(탐욕 알고리즘) 이번 문제는 백트래킹(back tracking) 기법을 사용하면 편하게 풀 수 있는 문제입니다. 큰 수의 경우에는 9부터 원하는 개수만큼, 작은 수의 경우에는 0부터 원하는 개수만큼 선택해서 그것으로 백트래킹을 하면 됩니다. 저는 조금 다른 식으로 풀어보았습니다. https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 바로 탐욕 알고리즘을 이용해서 큰 수가 들어가야할 위치를 찾는 것이죠. 예를 들어서 (1) (4) ... 형.. 2023. 6. 24. [C/C++] 백준 #2468 안전 영역(탐욕 알고리즘) #2468 문제는 그래프 이론, 부르트포스 방법 등으로 풀 수 있겠지만, 전 정렬을 이용한 탐욕 알고리즘을 이용해서 풀었습니다. 어쩌다 보니, 푼 사람 내에서 상위권에 있다보니 제 소스 참조횟수가 많은 문제가 되었네요. https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 제가 생각한 것은 단순합니다. 일단 지대가 높은 것부터 낮은 순으로 정렬을 합니다. 지대가 가장 높은 곳은 비가 가장 많이 왔을 때에도 안전지대가 되겠죠. 그리고 그 영역의 개수는 상호 .. 2023. 5. 16. [Python] 백준 #2457 공주님의 정원(탐욕 알고리즘) #2457 문제는 탐욕 알고리즘을 이용해서 풀 수 있습니다. 탐욕 알고리즘은 정렬을 하고, 조건에 맞는 경우에는 우선 선택 과정을 하게 됩니다. https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 문제는 공주님의 정원에 늘 꽃이 한종류 이상 피어있게 하면서, 최소의 꽃을 정원에 두는 것입니다. 최소의 꽃의 개수를 구하는 것이 목표입니다. 이 문제를 풀기 위해서는 (꽃 피는 날짜, 꽃이 지는 날짜) 쌍을 적절하게 유지해야 합니다... 2023. 5. 8. [C/C++] 백준 #2437 저울(탐욕 알고리즘) 이번 문제는 탐욕 알고리즘을 이용하여 풀면 됩니다. https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 우리에게는 천칭저울로 알려진 무게를 재는 도구입니다. 한쪽에는 무게를 알고지 하는 물체를 다른 한쪽에는 추를 놓음으로써 평형을 이루는 지점을 찾아서 물체의 무게를 알 수 있습니다. 저울추가 N 종류 주어지면, 우리는 이 저울추 N개를 가지고 만들 수 있는 숫자들을 생각하면 됩니다. 어떻게 보면 코인 문제와 비슷한데, 코인 문제는 경우의 수를 따지지만, 여기.. 2023. 5. 2. [C/C++] 백준 #2217 로프(탐욕 알고리즘) #2217 문제는 정렬을 사용한 탐욕 알고리즘으로 풀 수 있는 문제입니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net n개의 로프가 있는데, 여러줄을 사용하면, 들어올리고자 하는 물건의 무게를 똑같이 분담하면서 물건을 올릴 수가 있습니다. 로프마다 견딜 수 있는 하중이 따로 있어서, 현재 가지고 있는 로프로 가능한 무거운 물건을 올리고자 할 때, 그 무게가 얼마인가입니다. 예를 들어서 무게를 3, 7, 6, 4.. 2023. 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 문제는 수직선상에 있는 N개의 점들을 K개의 그룹으로 나누었을 때, 각각의 그룹의 길이의 합을 최소로 하는 문제입니다. 가장 쉬운 것은 두점사이의 거리가 가장 먼 것들에 대해서 K-1개 선택해서 나누면 됩니다. 문제의 예제처럼 1 6 9 3 6 7 위치들의 점이 있다고 한다면, 이것을 순서대로 정렬하면, 1 3 6 6.. 2023. 4. 17. 이전 1 2 다음 728x90
