그리디(Greedy) 알고리즘

제108회3교시SW공학/프로젝트관리신규

정보관리기술사 제108회 3교시 20번 문항으로, 과목은 SW공학/프로젝트관리입니다. ‘그리디 알고리즘’ 키워드는 정보관리기술사 기출 2문항에 나왔습니다.

원문 문제

정보관리기술사 제108회 20번. 그리디(Greedy) 알고리즘

  1. 가. 지폐 1000원을 받고 동전으로 770원을 돌려 줄 때 최소 동전수를 찾는 그리디 알고리즘을 설명하시오. (단, 동전의 액면은 500원, 100원, 50원, 10원임)
  2. 나. 위 알고리즘을 C 또는 Java 언어로 구현하시오.

핵심 키워드

  • 그리디 알고리즘
  • 최소 동전 문제
  • 최적 부분 구조
  • 선택 기준
  • 알고리즘 구현

고득점 가이드 — 1. 개요

그리디 알고리즘은 각 단계에서 현재 시점의 최적해를 선택하고 이전 선택을 번복하지 않는 단순한 의사 결정 전략으로, 최적 부분 구조와 그리디 선택 속성이 성립할 때 전역 최적을 보장한다. 동적 계획법보다 상태 공간 탐색 비용이 작아 구현이 단순하고 시간 복잡도가 낮지만 모든 문제에 적용 가능하지는 않다. 거스름돈 문제는 동전 액면이 배수 관계 (500·100·50·10) 를 이루는 한국 화폐 체계에서 큰 액면 우선 선택이 항상 최소 동전 수를 보장하므로 그리디 적용에 적합한 대표 사례다. 770원 반환 절차는 [표 1] 참조.

로그인하면 하루 1편은 무료로 전문을 볼 수 있어요

  • 변형 문제
  • 답안 골격
  • 고득점 가이드 전문
로그인하고 하루 1편 무료로 보기

출제 이력

  • 그리디 알고리즘기출 2문항
  • 최소 동전 문제기출 1문항
  • 최적 부분 구조기출 1문항
  • 선택 기준기출 1문항
  • 알고리즘 구현기출 1문항

같은 과목 문항

SW공학/프로젝트관리 기출 전체 보기 →

AI 생성 골격 · 미검수