• 티스토리 홈
  • 프로필사진
    Song hyun
  • 방명록
  • 공지사항
  • 태그
  • 블로그 관리
  • 글 작성
Song hyun
  • 프로필사진
    Song hyun
    • 분류 전체보기 (780)
      • 백준 (0)
      • 영어 (2)
        • Diary (0)
        • Toast Masters (2)
      • 메모 (13)
      • 설치 메뉴얼 (30)
      • Java (178)
      • MySQL (60)
      • JSP (67)
      • Springboot (46)
      • HTML,CSS, JS (71)
        • HTML (8)
        • CSS (12)
        • JavaScript (37)
        • HTML&CSS 스터디 (13)
      • C++ (7)
      • Linux (7)
      • JPA (34)
      • Kotlin (2)
      • Flutter (42)
      • Error Note (39)
      • 디자인 패턴 (12)
      • 디지털논리회로 (4)
      • 데이터베이스 시스템 (8)
      • 알고리즘 (7)
      • 운영체제 (3)
      • 이산수학 (3)
      • 인공지능 (1)
      • 자료 구조 (14)
        • 기본 개념 (14)
        • 자료구조 스터디 (0)
      • 💡My project (76)
        • 팩맨 : Java Swing 게임 제작 프로젝트 (6)
        • 네이트톡 : Java 소켓 통신 프로젝트 (4)
        • 포켓옥션 : HikariCP&JDBC CRUD 프.. (3)
        • 이지 부산 : BDIA-Devton 2024 프로.. (20)
        • 그린 유니버시티 : JSP를 사용한 학사관리 프로.. (1)
        • 애드 포커 : 웹 소켓과 Spring을 사용한 카.. (1)
        • 셸위 : 게임 친구 매칭 사이트 (21)
        • 다모아 : 개발자 중개 플랫폼 (20)
      • 📗스터디 (13)
        • CNN : 웹개발 스터디 (10)
        • Node&React로 유튜브 사이트 만들기 (3)
      • 📙독서 및 강연 기록 (36)
        • 강연 (14)
        • 독서 (22)
  • 방문자 수
    • 전체:
    • 오늘:
    • 어제:
  • 최근 댓글
      등록된 댓글이 없습니다.
    • 최근 공지
        등록된 공지가 없습니다.
      # Home
      # 공지사항
      #
      # 태그
      # 검색결과
      # 방명록
      • [알고리즘] 욕심쟁이 방법
        2025년 03월 14일
        • Song hyun
        • 작성자
        • 2025.03.14.:50
        728x90
        반응형

        [알고리즘] 욕심쟁이 방법

         

        -알고리즘의 대표적인 설계 기법으로는 욕심쟁이 방법, 분할정복 방법, 동적 프로그래밍 방법이 있다.

         

        1. 욕심쟁이 방법(Greedy Algorithm)
        -탐욕 알고리즘, 그리디 알고리즘이라고도 불린다.

        -욕심쟁이 방법이란 일련의 선택 과정을 통해 해를 찾는데, 전후 단계의 선택과정과 관계 없이 각 단계마다 정해진기준에 따라 가장 최선이라고 여겨지는 국부적인 최적해를 찾아나가면 결과적으로 전체적인 최적해를 구할 수 있다는 전략을 취하는 방식이다.

        -어떤 문제에 욕심쟁이 방법을 적용할 수 있다면, 최적해를 보장하는 효율적인 알고리즘을 가장 간단히 만들 수 있는 방식이다.

        -가능한 여러 해 중 최솟값/최대값을 찾는 최적해 문제에 주로 사용된다.

        -ex: 거스름돈 문제, 배당 문제와 같은 비교적 간단한 문제들

         

         

        2. 거스름돈 문제

        (1) 일반적인 경우

        -거스름돈이 780원일 때, 고객에게 돌려줄 동전의 최소 개수를 구해보자. 이 때 사용가능한 동전의 갯수는 500/100/50/10원 총 네 종류가 있다.

        -> 욕심쟁이 방법을 적용한다면, 액면가가 큰 동전부터 '욕심을 부려서' 최대한 뽑아 거스름돈을 만드는 것이다.

        -> 500x1, 100x2, 50x1, 10x3 -> 총 7개의 동전을 거슬러 줄 수 있다.

         

        (2) 120원의 동전이 존재할 때

        -거스름돈이 650원일 때, 고객에게 돌려줄 동전의 최소 개수를 구해보자. 이 때 사용가능한 동전의 갯수는 500/120/100/50/10원 총 네 종류가 있다.

        -> 욕심쟁이 방법을 적용한다면 500원 1개, 120원 1개, 10원 3개라는 결론이 나온다. 하지만 이는 최적해가 아니다.

        -> 500원 1개, 100원 1개, 50원 1개를 사용하면 동전을 3개만 사용하고로 거스름돈을 줄 수 있다.

        -> 이와 같이 거스름돈 문제라고 해도, 동전의 액면가가 일반적인 경우에는 욕심쟁이 방법을 사용할 수 없음!

         

         

        728x90
        반응형

        '알고리즘' 카테고리의 다른 글

        [알고리즘] 알고리즘 분석  (0) 2025.03.16
        [알고리즘] 동적 프로그래밍 방법  (0) 2025.03.15
        [알고리즘] 분할정복 방법  (0) 2025.03.15
        [알고리즘] 알고리즘 설계  (0) 2025.03.13
        [알고리즘] 알고리즘의 개념  (0) 2025.03.12
        다음글
        다음 글이 없습니다.
        이전글
        이전 글이 없습니다.
        댓글
      조회된 결과가 없습니다.
      스킨 업데이트 안내
      현재 이용하고 계신 스킨의 버전보다 더 높은 최신 버전이 감지 되었습니다. 최신버전 스킨 파일을 다운로드 받을 수 있는 페이지로 이동하시겠습니까?
      ("아니오" 를 선택할 시 30일 동안 최신 버전이 감지되어도 모달 창이 표시되지 않습니다.)
      목차
      표시할 목차가 없습니다.
        • 안녕하세요
        • 감사해요
        • 잘있어요

        티스토리툴바