그리디14 [그리디 #21] BOJ 7570 - 줄 세우기 https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 1차 시도 처음에 이걸 그리디로 해결하기 위해서 다음과 같이 생각했다. 1. 앞으로 옮겼을 때, 뒤쪽에 자신보다 큰 수들이 많이 위치하는 것을 골라야한다. 2. 뒤로 옮겼을 때, 앞쪽에 자신보다 큰 수들이 많이 위치하는 것을 골라야 한다. 그러나 이것은 금방 틀리다는 것을 알 수 있다. 가령 1,2번이 맞다고 하더라도 순서대로 이어져있지 않으면 문제가 된다. 따라서, 순서를 집중해서 공략하는게 좋겠다고 .. 2024. 2. 27. [그리디 #20] BOJ 2212 - 센서 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 접근방법 저번에 풀었던 행복유치원과 같은 문제이다. 예제 2번을 보면서 한번 살펴보자. 10 5 10 5 20 3 14 6 7 8 18 10 12 15 해당 센서를 오름차순으로 정렬하면 다음과 같다. 3 6 7 8 10 12 14 15 18 20 이 세선들을 몇 개씩 묶어서 총 K개의 묶음으로 만들면 된다. 이때, 문제의 핵심은 센서 사이의 거리가 짧은 것을 위주로 선택해.. 2024. 2. 25. [그리디 #19] BOJ 2812 - 크게 만들기 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 접근 방법 심플하면서 어려운 문제이다. n자리 수에서 m개의 수를 제거하여 가장 큰 수를 만드는 문제이다. 예제 3번에 이 문제에 힌트가 있다. 4 1 7 7 2 5 2 8 4 1 에서 4개를 제거하여 775841 를 만들어야 한다. 핵심은 4와 1을 제거하여 7을 가장 높은 자릿수로 만들어야 한다는 것! 예전에 스택을 이용하여 괄호가 포함된 중위 표기법을 후위 표기법으로 고치던게 생각이 났다. 스택에 숫자들을 넣고, 현재 숫자보다 작은 숫자들은 제거하는 방식으로 진행하여 .. 2024. 2. 23. [그리디 #18] BOJ 11000 - 강의실 배정 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 접근 방법 저번에 풀었던 최소 회의실 개수와 같은 문제이다. https://parvegoongame.tistory.com/126 [그리디 #16] BOJ 19598 - 최소 회의실 개수 https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 2개 회의실로 3개 회의를 모두 진행할 수 있다. 예를 들어, 첫번째 회의실에서 첫번째 회의를 진행하고 두번째 회의실에서 두번째 회의와 meteorfish.blo.. 2024. 2. 22. [그리디 #17] BOJ 21314 - 민겸 수 https://www.acmicpc.net/problem/21314 21314번: 민겸 수 민겸 수 하나가 주어진다. 민겸 수는 대문자 M과 K로만 이루어진 문자열이며, 길이는 3,000을 넘지 않는다. www.acmicpc.net 접근 방법 두를 최종적으로 계산하는 경우는 두가지 이다. 1. K가 왔을때 2. string이 끝날때 이 두 가지 경우는 최소와 최대 공통적으로 적용된다. 이제 세부적으로 최대와 최소를 구하는 알고리즘을 생각해보자. i) 최대 MKKMMK 의 경우, MK + K + MMK = 50 5 500 이다. K는 50을 곱해버리므로 무조건 M과 붙어야한다. 따라서, 알고리즘은 다음과 같다. 1. M이 왔을 경우, mCnt를 +1 한다. 2. K일 경우, mCnt를 이용하여 수를 계산 .. 2024. 2. 22. [그리디 #16] BOJ 19598 - 최소 회의실 개수 https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 2개 회의실로 3개 회의를 모두 진행할 수 있다. 예를 들어, 첫번째 회의실에서 첫번째 회의를 진행하고 두번째 회의실에서 두번째 회의와 세번째 회의를 진행하면 된다. 1개 회의실로 3개 회의 www.acmicpc.net 계속된 실패.. 비슷한 문제인 회의실 배정 문제에선 끝나는 시간을 기준으로 정렬하여 진행하였다. 이와는 다른 방법을 생각해보다 회의 시간이 짧은 것을 기준으로 해보면 어떨까라고 생각했다. 이를 이용해 어떻게든 해보려고 했는데 실패하고, 안되는 이유를 찾아보았다. 아무리 끝나는 회의 시간이 짧더라도 끝나는 시간이 짧을 수록 이득을 볼 수 있기 때문에 이는 틀린 아이디어이다. 접근 방법 회의가.. 2024. 2. 19. 이전 1 2 3 다음
