그리디

https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net 문제 풀이 학생들이 각자 받고싶은 책의 범위들에서 적절하게 분배 해 줘야하는데 만약 1번 학생이 1,2,3 의 책 번호를 골랐고 2번 학생이 2,3 책 번호를 골랐다고 하면 2번 학생은 1번책을 받지 못하기때문에 1번 학생에게 우선 1번책을 주고 그다음 2번학생에게 2번 or 3번의 책을 줘야한다. 다른예시로 1번학생이 1,2의 책 번호를 골랐고 2번학생이 2,3의 책 번호를 3번 학생이 2,3을 골..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 풀이 처음엔 한 가방에 하나의 보석밖에 못넣는다고 적힌것 못 보고 Knapsack 문제 + 가방이 여러개 ..? 라고 접근할 뻔 했다가 산으로 갈 뻔 했다.. 접근방법 용량이 작은 가방과 무게가 작은 보석 순으로 천천히 순차적으로 보고 , 조건에 맞으면 그 가방에 보석을 넣는 방식으로 하면 된다. => 그리디 접근 가령 , 예제 2..

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 문제 풀이 그냥 완전 그리디 노가다.. 1보다 큰 수들 => 높은 수 순으로 2개씩 묶음 , 나머지들은(1이 있거나 하나 남았거나) 그냥 합산 0보다 작은 수들 => 2개씩 묶으면 양수가 되기때문에 제일 작은 수 순으로 2개씩 묶음. 하나 남은 음수는 0 이 있으면 그냥 패스 하거나 0이 없으면 그냥 더해주면 끝 1보다 큰수 , 0 , 0보다 작은수를 list 3개 만들어서 각각 따로 넣어주고 ..

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 풀이 카드뭉치가 여러개 있고 한 뭉치씩 차례대로 합칠 때 카드의 갯수가 적은 순서로 합치면 된다. 카드 갯수가 적은 뭉치 2개를 하나로 만들고 , 만들어진 하나의 뭉치를 또 비교대상으로 쓰면 된다는 것 예를들어 30 40 50 60 이 있다고 가정하면 30+40 = 70 이 되고 , 70장의 하나의 뭉치를 50장짜리 뭉치랑 합치는 것이아닌 50 60 70 중에 갯수가 적은 순의..

https://www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 문제 풀이 첫번째. 1면, 2면, 3면 인 경우의 최소합을 각각 구하기 두번째. N개 일때 1,2,3 면이 각각 몇개 나오는지 구하기 1. 3면이 나와야 하는 경우 - 맨 윗면 꼭지점 부분 4군데 : 4 2. 2면이 나와야 하는 경우 - 전체 모서리 수에서 육면체 꼭지점 부분을 뺀 값 + 맨 아래 꼭지점부분 4 : 8(N-2)+4 3. 1면이 나와야 하는 경우 - 각 면마다..

https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 풀이 그리디 문제이다.. 처음엔 lis 알고리즘으로 풀 수 있을줄 알았다 ..왜냐 .. 서류와 면접 성적이 둘다 낮아야한다 => 평행하다 => 증가하는수열 => LIS 알고리즘 하지만 반례가 있었고 , LIS로 풀 수 없다는 것을 깨달았다 .. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27..