그리디알고리즘5 [백준문제풀이] 2812 크게 만들기 풀이일시 : 2020-09-10 문제 : N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 입력 : 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000) 둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다. ex) 4 2 1924 출력 : 입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다. ex) 94 풀이 : 그리디알고리즘 숫자의 자리를 바꾸면 안된다. 단순히 앞에서부터 숫자를 읽어가면서 스택에 넣으면 된다. 다만 새롭게 등장한 뒤에있는 숫자보다 작은 숫자들을 모두 스택에서 빼는 과정을 거쳐 스택에는 오직 큰 숫자들만 넣어주면 된다. 스택에 다 넣은 뒤에도 지워.. 2020. 12. 31. [백준문제풀이] 1783 병든나이트 풀이일시 : 2020-09-10 문제 : 병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다. 1. 2칸 위로, 1칸 오른쪽 2. 1칸 위로, 2칸 오른쪽 3. 1칸 아래로, 2칸 오른쪽 4. 2칸 아래로, 1칸 오른쪽 병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다. 체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자. 입력: 첫.. 2020. 12. 31. [백준문제풀이] 1946 신입사원 풀이일시 : 2020-09-02 문제 : 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다. 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다. 이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하.. 2020. 12. 31. [백준문제풀이] 10610 30 풀이일시 : 2020-09-02 문제 : 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 입력: N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. ex) 30 출력: 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라. ex) 30 풀이: 각 자리 수 합을 확인하고 예외없이 모두 추가하므로 그리디 알고리즘의 분류 정수론의 기초개념 : 각 자리 수의 합이 3의 배수라면 전체 숫자는 .. 2020. 12. 31. [기본문제풀이] greedy 알고리즘 풀이 일시 : 2020-08-29 그리디알고리즘 : 당장 눈앞에의 최적의 상황만 쫓는 알고리즘이다. 대표적인 알고리즘으로는 가장 짧은 간선부터 연결하는 크루스칼 알고리즘이 있다. 문제 : 총 몇개의 동전을 거슬러줘야되는가? => 최소값을 구하라 풀이 : 가장 큰 단위부터 거슬러줄 수 있다면 거슬러 주는 것이 동전을 가장 적게 사용하는 방법일 것이다. #include using namespace std; //총 몇개의 동전을 거슬러 줘야되는가 int main() { int n, result = 0; cin >> n; result += n / 500; n %= 500; //나머지 연산을 해서 다음 레이어로 간다. result += n / 100; n %= 100; result += n / 50; .. 2020. 12. 29. 이전 1 다음 반응형