컴퓨터하는 kimmessi

탐욕 알고리즘이란? 작은 사례로 나누지 않고 탐욕스러운 선택을 sequence로 계속하면 답에 가까워진다. 선택과정(selection procedure) : 집합에 추가할 다음 원소를 고른다. 그 당시 최적을 선택하는 탐욕 기준에 따라 선택한다. 적절성검사(feasibility check) : 새로운 집합이 해답이 되기 적절한지 검사한다. 해답점검(solution check) : 새로운 집합이 문제의 해답인지 결정한다. 이 과정이 동시다발적으로 진행된다. 거스름돈을 고르는 탐욕 알고리즘 예를 들어 돈이 50원, 25원, 10원, 5원, 1원이 있고 31원을 거슬러 주어야 할 때, (이때, 거슬러 주는 각각의 동전들은 여러개이다.) 1. 50원을 집었다가 내려놓는다. 2. 25원을 집는다. 3. 25원을 ..

https://www.acmicpc.net/problem/1461 1461번: 도서관 첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N은 10,000보다 작거나 같은 자연수이고, M은 10,000보다 작거나 같다. 책의 위치 www.acmicpc.net 문제 해결 알고리즘 1. 0을 포함한 숫자들을 모두 입력 받고 정렬한다. 2. 0의 위치를 pivot이라고하자, 이때 0부터 pivot까지 M칸 간격마다 숫자를 2곱해준 걸 result에 더한다. 마찬가지로 N부터 pivot까지도 똑같이 해준다. 3.배열 제일 처음부분과 마지막부분 중 가장 큰 숫자를 빼준다. 소스 코드 #include using namespace std; int ..

www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 해결 알고리즘 1. 회의가 끝나는 시간을 기준으로 정렬을 한 후, 만약 같다면 시작하는 순서대로 정렬을 해준다. 2. 그 다음 회의가 가장 빠르게 끝나는 회의 시간(pivot)를 시작으로 다음 회의 시작 시간과 비교한다. 3. 만약 다음 회의 시작시간이 더 크다면 횟수(cnt)를 하나 더해주고 피봇을 다음 회의 시작하는 시간으로 바꿔준다. 그걸 계속 반복해준다. 4. 횟수(cnt)를 출력한다. 소스 코드 #include using namespace std; bool cmp(pair a, pair b){ if(a.second..