그리디 알고리즘
-
백준 13458번 시험 감독 :: 마이구미알고리즘 풀이/그리디 2017. 11. 5. 23:03
이 글은 백준 알고리즘 13458번 "시험 감독" 을 풀이한다.삼성 SW 역량 테스트의 기출 문제이다.문제는 그리디(Greedy)하게 접근할 수 있다.정답 비율과 삼성 기출 문제를 보면 쉽지 않게 느껴지지 않지만, 굉장히 쉬운 문제가 된다.문제 링크 - https://www.acmicpc.net/problem/13458그리디 알고리즘 - http://mygumi.tistory.com/121 총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다.감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 방에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 방에서 감시할 수 있는 응시자의 수가 C명이다.각각의 시험장에 총감독관은 오직 1명만..
-
백준 1744번 수 묶기 :: 마이구미알고리즘 풀이/그리디 2017. 9. 18. 20:59
이 글은 백준 알고리즘 문제 1744번 "수 묶기" 를 풀이한다.문제의 접근 방법은 그리디 알고리즘으로써, 어떠한 자료구조를 요구하지는 않는다.하지만 정답 비율이 낮은 문제로써, 까다로울 수 있다.1744번 "수 묶기" - https://www.acmicpc.net/problem/1744그리디 알고리즘 - http://mygumi.tistory.com/121 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 어떤 인접한 원소끼리를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구..
-
백준 2875번 대회 or 인턴 [Greedy] :: 마이구미알고리즘 풀이/그리디 2017. 2. 11. 17:59
이번 글은 백준 알고리즘 2875번 "대회 or 인턴" 을 다뤄본다.이 문제는 그리디 알고리즘으로 문제를 접근할 수 있다.그리디 알고리즘 - http://mygumi.tistory.com/1212875번 대회 or 인턴 - https://www.acmicpc.net/problem/2875 백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.)백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다.그런데 올해에는 대회에 참여하려는 학생들 중 K명을 반드시 인턴쉽 프로그램에 참여하라는 학교의 방침이 생기게 되었다.백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것..
-
그리디(Greedy) 알고리즘 :: 마이구미알고리즘 2017. 2. 8. 22:07
이번 글은 그리디(Greedy) 알고리즘에 대해 다뤄본다.그리디 알고리즘은 탐욕 알고리즘, 욕심쟁이 알고리즘으로도 불린다. 그리디 알고리즘은 간단히 정의하자면 아래와 같이 표현할 수 있다. 경우의 수가 존재할 경우, 경우를 선택해야할 때 최선이라고 생각하는 경우를 선택하는 알고리즘이다. 여기서 최선이라고 생각하는 경우가 무엇인가?그것을 이해하면 그리디 알고리즘을 이해할 수 있다.쉽게 말하면, 전체를 고려하지 않고, 그 순간에서의 최선을 말한다.즉, 그때그때 더 좋아보이는 쪽을 선택하는 것이다.그렇기에 최종적으로는 그 선택이 최적이라고 확신할 수 없다. (문제에 따라 최적이라고 확신할 수도 있다.) 예를 들어, 지금은 초코파이를 먹을 수 있지만, 10분 후면 랍스타를 먹을 수 있다.그리디 알고리즘의 경우에..
-
백준 1946번 신입사원 [Greedy] :: 마이구미알고리즘 풀이/그리디 2017. 2. 8. 21:14
이번 글은 백준 알고리즘 1946번 "신입사원" 을 다뤄본다.문제 해결법은 그리디 알고리즘이다.그리디 알고리즘 - http://mygumi.tistory.com/121 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않..