그리디7 [백준] 19598 : 최소 회의실 개수 (JAVA) 난이도 🥇 5 링크 https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 문제 풀이과정 해당 문제는 그리디를 사용하는 문제이다. 예전에 풀었던 비슷한 문제에서는 종료 시점을 기준으로 정렬했기 때문에 이를 토대로 문제를 풀어보려고 했는데 잘 되지 않았다. 그래서 왜 안되지라고 생각하면서 반례를 찾아보니 안되는 반례를 찾았다! 만약 4개의 회의가 있고 각각의 시작 시간과 종료 시간이 다음과 같을 때 0 2 1 4 2 6 4 5 종료 시간을 기준으로 .. 2024. 1. 20. [백준] 1034 : 램프 (JAVA) 난이도 🥇 4 링크 https://www.acmicpc.net/problem/1034 1034번: 램프 첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져 www.acmicpc.net 문제 풀이과정 해당 문제는 부르트포스를 사용한다고 적혀있지만 그리디를 사용하는 문제이다. 그 이유는? 부르트포스를 사용하게 되면 행과 열이 50이하인데 모든 과정을 돌아보려면 2^열 인 2^50 가지의 경우의 수가 되어 시간초과가 뜬다.. 그래서 그리디를 사용해서 규칙을 찾는 것이 중요하다! 처음에 문제가 이해가 안돼서 한참 찾아보면서 문제를 이해해보았다. (근데 문제를.. 2024. 1. 15. [백준] 13975 : 파일 합치기 3 (JAVA) 난이도 🥇 4 링크 https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net 문제 풀이과정 해당 문제는 그리디를 사용하는 문제이다. 생각해보면 굉장히 쉽게 풀 수 있는 문제여서 문제 설명에 쓰여진 예시를 보지 않는게 더 도움이 될 거 같다.. 예시 설명에서는 [40 30 30 50] 이라는 값이 있을 때 1) 먼저 40 + 30 = 70 2) 30 + 50 = 80 3) 70 + 80 = 150 이러한 과정으로 결과값을 출력하도록 설명하였는데 이렇게.. 2024. 1. 14. [백준] 1026 : 보물 (JAVA) 난이도 🥈 4 링크 https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 문제 풀이과정 해당 문제는 그리디 알고리즘을 사용해서 푸는 문제였다. 사실 다른 그리디 문제들과는 달리 A의 수를 재배열하고, B에 있는 수를 재배열하지 말라고 했지만, 그저 'S의 최솟값'을 출력하기만 하면 되기에 둘 다 정렬하여 결과값을 구했다 :) 1) 각각 입력받은 값들을 A와 B 배열에 저장한다. 2) A 배열은 오름차순으로, B 배열은 내림차순으로 정렬한다. .. 2024. 1. 13. [백준] 11501 : 주식 (JAVA) 난이도 🥈 2 링크 https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 문제 풀이과정 해당 문제는 그리디 알고리즘을 사용해서 푸는 문제이다. 그리디 알고리즘에 대한 설명은 아래 글을 참고하면 좋을 거 같다! https://amepistheo.tistory.com/7 [백준] 1449 : 수리공 항승 (JAVA) 난이도 🥈 3 링크 https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이.. 2024. 1. 9. [백준] 1946 : 신입 사원 (JAVA) 난이도 🥈 1 링크 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 풀이과정 해당 문제도 그리디 알고리즘을 사용해서 푸는 문제였다. 그리디 알고리즘에 대한 설명은 아래 글에 작성해두었으니 참고하면 좋을 것 같다! https://amepistheo.tistory.com/7 [백준] 1449 : 수리공 항승 (JAVA) 난이도 🥈 3 링크 https://www.acmicpc.net/problem/1449 1449번: 수리.. 2024. 1. 8. 이전 1 2 다음
