그리디 알고리즘 (2) 썸네일형 리스트형 [BOJ 16953번/C++] A → B 미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요! https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net A → B 풀이 이 문제는 탐욕법으로 풀 수 있었다. 문제에서 가능하다고 한 연산을 반대로 생각해서 풀었더니 곧바로 답이 돌출됐다. 1. A에서 2를 곱한다. → B에서 2를 나눈다. 2. A의 가장 오른쪽에 1을 추가한다. → B에서 가장 오른쪽에 있는 1을 빼준다. 1의 연산을 할 수 없을 때, 2의 연산도 할 수 없다면.. [알고리즘] 그리디 알고리즘 (Greedy Algorithm) 그리디 알고리즘 (Greedy Algorithm) 눈앞의 이익만 좇는 선택을 반복하는 알고리즘이다. 그리디 알고리즘은 당장의 경우에는 최적의 경우일지라도, 결과는 대부분 최적이 아니다. 그렇지만 드물게 최적의 답을 보장해주는 경우가 있다. 해가 만들어 질 때 까지 가장 좋아 보이는 선택을 하는 것을 반복한다. 그리디 알고리즘은 이미 앞에서 사용되었다. 바로, 최소 신장 트리를 구할 때 사용한 프림 알고리즘과 크루스칼 알고리즘이다. 또한, 프림 알고리즘과 크루스칼 알고리즘은 최적해가 보장되는 예들 중 하나이기도 하다. 그러나 이 둘이 특별한 경우이고 대부분의 경우에는 최적의 해를 보장하지 못한다. 아래와 같은 예시를 보자. 1. 이진 트리의 그리디 탐색 이진 트리에서 리프 노드를 만날 때 까지 방문한 노드.. 이전 1 다음