ch3_그리디.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "ch3_그리디.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyMzIAp3fRQGZC5TeJqS+079",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/babeebird/ThisCodingTest/blob/main/ch3_%EA%B7%B8%EB%A6%AC%EB%94%94.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "- 한 문장으로 말하자면   \n",
        "  - 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.\n",
        "- 좀 더 자세히 말하자면  \n",
        "  - 사전에 외우고 있지 않아도 풀 수 있다. 이는 알고리즘 사용법을 정확히 알아야 하는 정렬, 최단경로 등의 알고리즘 유형과 다르다!\n",
        "  - 기준에 따라 가~장 좋은 것을 선택하므로 ‘가장 큰(작은) 순서대로’ 와 같은 기준이 제시된다. 따라서 그리디 알고리즘은 대체로 정렬 알고리즘과 짝꿍이다!\n",
        "  - 탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식이다.\n"
      ],
      "metadata": {
        "id": "tv34ZXmy0IJx"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#- 예제 3-1 거스름돈 \n",
        "'''\n",
        "- 문제 정리\n",
        "1. 나(점원)은 500원, 100원, 50원, 10원 짜리 거스름돈은 아~주 많이(무한히) 가지고 있다.\n",
        "2. 나(점원)은 손님에게 N원을 거슬러 주어야 한다. 이때 N은 항상 10의 배수이다.\n",
        "3. N원을 거슬러 줄 때 어떻게 하면 동전 개수를 제일 적게해서 (최소로) 거슬러 줄까 ?\n",
        "\n",
        "- 자연어 알고리즘 \n",
        "1. N원을 거슬러 줄 때, 가장 큰 500원 짜리 a개로 거슬러 준다. \n",
        "2. 거슬러주어야 하는 남은 돈을 100원 짜리 b개로 거슬러 준다.\n",
        "3. 거슬러주어야 하는 남은 돈을 50원 짜리 c개로 거슬러 준다.\n",
        "4. 마지막으로 거슬러주어야 하는 남은 돈을 10원 짜리 d개로 거슬러 준다.\n",
        "'''\n",
        "\n",
        "def change_min_coin(N): #- 최소한의 동전으로 거슬러라! <= 함수명 제안 받습니다\n",
        "  '''\n",
        "  Args:\n",
        "    N: i거슬러주어야 하는 금액 (10의 배수)\n",
        "  Returns:\n",
        "    count: 500원, 100원, 50원, 10원을 사용하여 N을 거슬러줄때 사용한 최소한의 동전 개수!\n",
        "\n",
        "  '''\n",
        "  count = 0 #- count를 초기화한다.\n",
        "\n",
        "  coin_types = [500, 100, 50, 10] #- 거슬러 줄 큰 단위의 동전부터 차례대로 리스트에 넣는다.\n",
        "\n",
        "  for coin in coin_types:\n",
        "    count += N // coin #- 해당 화폐(coin)으로 거슬러 줄 수 있는 동전의 개수(몫)를 세서 count에 더한다. \n",
        "    N %= coin #- N을 해당 화폐로 거슬러 준 뒤 남은 돈(나머지)을 N에 재할당한다. \n",
        "\n",
        "  return count\n",
        "\n",
        "count = change_min_coin(3500)\n",
        "count"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "OgBGvGEixJp9",
        "outputId": "50a6b5b4-1f77-4402-b13b-9b606480d96c"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "7"
            ]
          },
          "metadata": {},
          "execution_count": 1
        }
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "l4G9bLARd-3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 87
        },
        "outputId": "e3583a12-d127-41d4-9d97-980d46c370cd"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5 8 3\n",
            "2 4 5 4 6\n",
            "46\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'\\n5 8 3\\n2 4 5 4 6\\n146\\n'"
            ],
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            }
          },
          "metadata": {},
          "execution_count": 3
        }
      ],
      "source": [
        "#- 실전 2. 큰수의 법칙\n",
        "'''\n",
        "- 문제 정리\n",
        "1. 가장 큰 수를 만들려면 첫번째 큰 수를 최대한 K만큼 더하고 두번째 큰 수는 1번만 써야 가장 큰 수를 만들 수 있다\n",
        "2. (첫번째 * K번 + 두번째)가 한세트로 반복 될껀데 이걸 M 횟수만큼 해야 함 \n",
        "3. 이 세트의 숫자 갯수는 K + 1이 됨\n",
        "4. M / (K+1)을 하면 세트의 반복 횟수를 구할 수 있고,  딱 떨어지지 않았을 경우의 수도 고려해야 함\n",
        "\n",
        "- 자연어 알고리즘\n",
        "1. 배열의 크기 N, 더하는 횟수 M, 연속하여 합할 수 있는 횟수 K를 공백기준으로 입력받은 뒤, 순서대로 변수 n, m, k에 할당한다. \n",
        "2. 배열의 요소를 공백 기준으로 입력받아 리스트 타입으로 변환한 뒤, 변수 data에 할당한다. \n",
        "3. data를 오름차순 정렬을 한다. (뒤로 갈수록 숫자가 커지니까 내가 필요한 건 뒤에 숫자가 필요함)\n",
        "4. data에서 제일 큰 첫번째 숫자를 first변수에 저장한다(인덱스 사용)\n",
        "5. data에서 두번째로 큰 숫자를 second 변수에 저장한다(인덱스 사용)\n",
        "\n",
        "'''\n",
        "\n",
        "# 공백으로 구분하여 입력 받은 값(str)을 공백 기준으로 나누고 \n",
        "# 정수형으로 변환 후 각 변수 n, m, k에 넣는다 \n",
        "n, m, k = map(int, input().split())\n",
        "# N개의 수를 공백으로 구분하여 입력받은 값을 위와 같은 형식이고 리스트로 만든다\n",
        "data = list(map(int, input().split())) \n",
        "\n",
        "data.sort() # 리스트에 담겨 있는 숫자 정렬하고(오름차순)\n",
        "first = data[n-1]  # 가장 큰 수, 인덱스 0부터 시작이므로 -1 해줘야 마지막번째임\n",
        "second = data[n-2] # 두번째로 큰 수\n",
        "\n",
        "# 가장 큰 수 더해지는 횟수 계산\n",
        "count = int(m/(k+1)) * k  # 몫에 k를 곱하면 반복 횟수가 나옴\n",
        "count += m % (k+1)        # 나머지가 0이 아니면 그 나머지만큼 가장 큰수를 더해야 함\n",
        "\n",
        "result = 0   # 최종 합산 넣을 변수 만들고 \n",
        "result += (count) * first   # 가장 큰 수를 횟수만큼 곱하고\n",
        "result += (m - count) * second  # 남아있는 횟수만큼 두번째 큰 수로 더한다\n",
        "\n",
        "print(result) # 하면 가장 큰 수가 만들어진다. \n",
        "\n",
        "'''\n",
        "5 8 3\n",
        "2 4 5 4 6\n",
        "46\n",
        "'''"
      ]
    }
  ]
}