본문 바로가기

알고리즘 별 문제 정리/그리디

 (4)
[C++] 백준 2212: 센서 문제 이해- 도로에 센서와 그것을 관리할 집중국을 설치할 예정이다.- 센서는 적어도 하나의 집중국과 통신이 가능해야 한다.- 각 집중국은 수신 가능 영역을 조절할 수 있다. - N: 센서의 개수 (1 ~ 10,000, 10^4)- K: 집중국의 개수(1 ~ 1,000, 10^3) - 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 구하여라.  문제 풀이문제에서 원하는 것은N개의 센서가 있을 때, 이들을 K개의 영역(집중국의 영역)으로 나누는 것이다.그럼 수신 가능 영역의 길이의 합이 최소가 되도록 K개의 영역으로 어떻게 나눌까?  센서들을 K개의 영역으로 나누면 K-1개의 영역 사이의 구간이 생긴다.센서들끼리의 거리를 먼저 구한 뒤, 거리가 먼 k-1개의 구간을 영역 사이의 구간으로 하면 되..
[C++] 백준 1781: 컵라면 문제 이해- 각 문제는 데드라인과 보상이 별개로 존재한다.- 데드라인은 N 이하의 자연수이다.- 각 문제에 대한 보상과 총 보상은 2^31보다 작은 자연수이다. - 시간 제한: 2초- 메모리 제한: 256MB - N: 숙제의 개수 (1 ~ 200,000, 10^5)- (데드라인, 풀면 받는 컵라면 수) - 동호가 받을 수 있는 최대 컵라면 수를 구하라.  문제 풀이처음에 접근한 방식은 하루에 풀 수 있는 문제는 1개이므로 데드라인과 보상을 pair형으로 묶은 뒤,첫 번째 인자를 데드라인으로 올림차순으로 정렬같다면 두 번째 인자인 보상을 내림차순으로 정렬하여 진행하였다.정렬을 통해 그리디가 구현되었다고 생각하고슬라이딩 윈도우로 하루마다 선택해주는 방식으로 진행했는데,41 502 303 603 70위와 같은..
[C++] 백준 3109: 빵집 문제 이해- 첫째 열: 근처 빵집의 가스관- 마지막 열: 원웅이의 빵집- 파이프는 그러므로 첫째 열에서 시작하여 마지막 열에서 끝나야 함- 파이프의 방향은 우측 위, 우측, 우측 아래만 가능- 각 칸을 지나는 파이프는 1개만 존재할 수 있다. - 시간 제한: 1초- 메모리 제한: 256MB - R: 행의 개수 (1 ~ 10,000, 10^4)- C: 열의 개수 (5 ~ 500, 10^2) - 원웅이가 설치할 수 있는 가스관과 빵집을 연결하는 파이프라인의 최대 개수 문제 풀이DFS를 써야함은 문제를 보면 알 수 있다.근처 빵집에서 시작해서 원웅이의 빵집까지 연결해야 하니 말이다.  그런데 파이프의 최대 개수를 어떻게 구할 수 있을까???답은 바로 그리디 알고리즘의 적용이다.  그렇다면 그리디 알고리즘은 어..
[C++] 백준 17420: 깊콘이 넘쳐흘러 문제 이해- 기프티콘이 N개 있으며 사용 가능 기한이 존재한다.- 기한은 연장이 가능한데 한 번 연장하면 30일이 늘어난다.- 기한 연장은 최소한으로 하려 한다.- 기프티콘 중 기한이 가장 적게 남은 기프티콘만 사용 가능하다.- 기한이 같은 게 여러 개면 아무거나 사용할 수 있다.- 하루에 여러 개를 사용하거나 연장하는 것 모두 가능하다. - 시간 제한: 1초- 메모리 제한: 512MB - N: 기프티콘의 수 (1 ~ 100,000, 10^5)- Ai: 기프티콘의 남은 기한(1 ~ 1,000,000,000, 10^9)- Bi: i번째 기프티콘의 경우 Bi일 뒤에 사용할 계획이다.(1 ~ 1,000,000,000, 10^9) - 기한 연장을 해야 하는 최소 횟수를 출력하라.※ 32비트 정수를 넘을 수 있다..

티스토리툴바