5_binary_search_greedy.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "toc_visible": true,
      "authorship_tag": "ABX9TyPA1db0LR/CeDr9VjWAjvn2",
      "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/jungseungoh/Inflearn_Python/blob/main/5_binary_search_greedy.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# 이분탐색 (결정알고리즘)"
      ],
      "metadata": {
        "id": "GqpuTD-qaIvE"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Q. 이분탐색이란?  \n",
        "- 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법\n",
        "- left(start), mid, right(end)의 3가지 변수를 사용하여 원하는 데이터를 찾는다\n",
        "- O(logN)의 시간복잡도를 가진다"
      ],
      "metadata": {
        "id": "VAk8rL5QvpGu"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "[TIP]  \n",
        "- 답이 될 수 있는 조건을 먼저 파악하자!  \n",
        "(숫자 그룹의 수가 target보다 작아야한다)  \n",
        "- mid값 증가 또는 감소에 따라 cnt값이 어떻게 되는지 파악하자!"
      ],
      "metadata": {
        "id": "gNHUVZKGwDfE"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 1. 이분 검색"
      ],
      "metadata": {
        "id": "PTZ6EWUaaRvb"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "N개의 수를 오름차순 정렬한 다음 N개 중 한 개인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하시오.  \n",
        "(중복값 존재 X)"
      ],
      "metadata": {
        "id": "J7OX6DF1aT8T"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "단순 코딩을 수행해도 되지만 이분탐색을 이용한다면 수행하는 횟수가 절반씩 줄어든다.\n",
        "예를 들어, 1024개의 데이터에서 찾는거라면 1번 수행시, 512개, 256개, ... 이렇게 줄어서 데이터가 커져도 금방 찾을 수 있다."
      ],
      "metadata": {
        "id": "aIBUo2j6dQhS"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "n, m = map(int, input().split())\n",
        "a = list(map(int, input().split()))\n",
        "a.sort()\n",
        "for i in range(n):\n",
        "    if m == a[i]:\n",
        "        print(i+1)\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "h3JfO6vVbUk0",
        "outputId": "ace05fce-6396-4cb4-896a-a629c4895270"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "8 32\n",
            "23 87 65 12 57 32 99 81\n",
            "3\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "n, m = map(int, input().split())\n",
        "a = list(map(int, input().split()))\n",
        "a.sort()\n",
        "lt = 0\n",
        "rt = n-1\n",
        "while lt <= rt:\n",
        "    mid = (lt+rt)//2\n",
        "    if a[mid] == m:\n",
        "        print(mid+1)\n",
        "        break\n",
        "    elif a[mid] > m:\n",
        "        rt = mid-1\n",
        "    else:\n",
        "        lt = mid+1"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "YmqQQD-DdpB_",
        "outputId": "4010707b-ba1f-49cd-8841-353c75df3fb0"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "8 32\n",
            "23 87 65 12 57 32 99 81\n",
            "3\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 2. 랜선 자르기 (결정알고리즘)"
      ],
      "metadata": {
        "id": "9DzlZX8EzhZw"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "K개의 랜선을 모두 N개의 같은 길이의 랜선으로 잘라서 만들기\n",
        "\n",
        "ex) 300cm 랜선에서 140cm 랜선을 두개 짜르면 20cm 버려야 한다.\n",
        "\n",
        "만들 수 있는 최대 랜선의 길이를 구하기"
      ],
      "metadata": {
        "id": "PpclC0YRzm5u"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Line 리스트에서 각 랜선을 길이 len으로 잘랐을 때 몇 개가 나오는지 계산\n",
        "def Count(len):\n",
        "    cnt = 0\n",
        "    for x in Line:\n",
        "        cnt += (x // len)\n",
        "    return cnt\n",
        "\n",
        "k, n = map(int, input().split())  # k : 랜선의 개수  n : 필요한 랜선의 개수\n",
        "\n",
        "Line = []\n",
        "res = 0\n",
        "largest = 0\n",
        "\n",
        "for i in range(k):\n",
        "    tmp = int(input())\n",
        "    Line.append(tmp)\n",
        "    largest = max(largest, tmp)  # 가장 긴 랜선으로 갱신\n",
        "\n",
        "lt = 1  # 랜선의 최소 길이\n",
        "rt = largest  # 랜선의 최대 길이\n",
        "\n",
        "# 이진 탐색 과정\n",
        "while lt <= rt:\n",
        "    mid = (lt + rt) // 2\n",
        "    if Count(mid) >= n:\n",
        "        res = mid  # n개 이상 자를 수 있다면, 결과(res)에 mid 값을 저장\n",
        "        lt = mid + 1  # 더 긴 랜선 길이를 시도해보기 위해 lt를 오른쪽으로 이동\n",
        "    else:\n",
        "        rt = mid - 1  # n개 미만이라면, 더 짧은 랜선 길이를 시도하기 위해 rt를 왼쪽으로 이동\n",
        "\n",
        "print(res)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "H2oYJAXNz5da",
        "outputId": "6d1d1fd6-7ff4-4c49-de65-513c74a9a594"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "4 11\n",
            "802\n",
            "743\n",
            "457\n",
            "539\n",
            "200\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 3. 뮤직비디오 (결정알고리즘)"
      ],
      "metadata": {
        "id": "2inuNg6n6Z91"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def Count(capacity):\n",
        "    cnt = 1  # 필요한 DVD의 개수를 세기 위한 변수\n",
        "    sum = 0  # 현재 DVD에 담고 있는 음악 파일들의 합\n",
        "\n",
        "    for x in Music:\n",
        "        # 현재 음악 파일을 추가했을 때 용량이 초과하면\n",
        "        if sum + x > capacity:\n",
        "            cnt += 1  # 새로운 DVD가 필요하므로 cnt를 1 증가.\n",
        "            sum = x   # 새로운 DVD에 현재 음악 파일을 담는다.\n",
        "        else:\n",
        "            sum += x  # 초과하지 않으면 현재 DVD에 계속 담는다.\n",
        "\n",
        "    return cnt\n",
        "\n",
        "n, m = map(int, input().split())  # n: 음악 파일의 개수  m: DVD의 개수\n",
        "Music = list(map(int, input().split()))\n",
        "maxx=max(Music)\n",
        "lt = 1\n",
        "rt = sum(Music)\n",
        "res = 0\n",
        "\n",
        "# 이진 탐색 시작\n",
        "while lt <= rt:\n",
        "    mid = (lt + rt) // 2  #현재 DVD의 용량 후보\n",
        "    if mid>=maxx and Count(mid) <= m:\n",
        "        res = mid\n",
        "        rt = mid - 1\n",
        "    else:\n",
        "        lt = mid + 1\n",
        "\n",
        "print(res)"
      ],
      "metadata": {
        "id": "9jswdao265cr",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "75341516-76e7-407c-aff5-f4d9816d35c6"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "9 3\n",
            "1 2 3 4 5 6 7 8 9\n",
            "17\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 4. 마구간 정하기 (결정알고리즘)"
      ],
      "metadata": {
        "id": "9WX_c1AUBwv7"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되도록.\n",
        "\n",
        "C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 값 출력하시오."
      ],
      "metadata": {
        "id": "m4LQvmk_Eew1"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def Count(len):\n",
        "    cnt=1\n",
        "    ep=horse[0]  #endpoint\n",
        "    for i in range(1, n):\n",
        "        if horse[i]-ep >= len:\n",
        "            cnt+=1\n",
        "            ep=horse[i]\n",
        "    return cnt\n",
        "\n",
        "n, c = map(int, input().split())\n",
        "horse = []\n",
        "for _ in range(n):\n",
        "    a = int(input())\n",
        "    horse.append(a)\n",
        "horse.sort()\n",
        "lt=1\n",
        "rt=horse[n-1]\n",
        "res=0\n",
        "while lt<=rt:\n",
        "    mid=(lt+rt)//2\n",
        "    if Count(mid)>=c: #mid : 가장 가까운 두 말의 거리\n",
        "        res=mid\n",
        "        lt=mid+1\n",
        "    else:\n",
        "        rt=mid-1\n",
        "print(res)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "MkHtIdl_Eoch",
        "outputId": "6eea46c8-4af8-4b5e-881c-89bd15425abd"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5 3\n",
            "1\n",
            "2\n",
            "8\n",
            "4\n",
            "9\n",
            "[1, 2, 4, 8, 9]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# 탐욕 (그리디알고리즘)"
      ],
      "metadata": {
        "id": "tZoAuU3BIvp8"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "그리디 알고리즘이란?  \n",
        "현재 상황에서 가장 좋은 것을 고르는 알고리즘.  \n",
        "\n",
        "[탐욕스러운 선택 조건]\n",
        "- 항상 안전하다는 것이 보장되어야 한다! \"안전하다\"라는 것은 이 선택으로 인해 전체 문제의 최적해를 반드시 도출할 수 있어야 한다는 것."
      ],
      "metadata": {
        "id": "FljKkiFQwbFN"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 5. 회의실 배정 (그리디 알고리즘)"
      ],
      "metadata": {
        "id": "Yz8A5kWmIxth"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "각 회의에 대해 시작시간과 끝나는 시간이 주어지고, 회의가 겹치지 않으면서 사용할 수 있는 최대 수의 회의를 찾으시오.  \n",
        "(단, 한번 시작하면 중간에 중단 X, 회의가 끝나야 다음 회의 시작 가능)\n"
      ],
      "metadata": {
        "id": "DIvXcxe2p4xO"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "-> 회의가 끝나는 시간을 기준으로 정렬하자!  \n",
        "2 3  \n",
        "1 4  \n",
        "3 5  \n",
        "4 6  \n",
        "5 7"
      ],
      "metadata": {
        "id": "INEdwPQyqv6K"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "n = int(input())\n",
        "meeting = []\n",
        "for i in range(n):\n",
        "    s,e = map(int, input().split())\n",
        "    meeting.append((s,e))\n",
        "meeting.sort(key=lambda x : (x[1], x[0]))   #람다식을 이용한 정렬법! 끝나는 시간을 고려해서 정렬.\n",
        "et=0 #endtime\n",
        "cnt=0\n",
        "for s,e in meeting:\n",
        "    if s>=et:\n",
        "        et=e\n",
        "        cnt+=1\n",
        "print(cnt)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "zaSxK53uqNNj",
        "outputId": "d02c7c82-f691-4a43-a35f-c664959d5408"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5\n",
            "1 4\n",
            "2 3\n",
            "3 5\n",
            "4 6\n",
            "5 7\n",
            "3\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 6. 씨름 선수 (그리디 알고리즘)"
      ],
      "metadata": {
        "id": "jcL3J6nDpjYY"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "다른 모든 지원자와 일대일 비교하여 키와 몸무게 중 적어도 하나는 크거나, 무거운 지원자만 뽑기.  \n",
        "(만약 A라는 지원자보다 키,몸무게 둘 다 큰 지원자가 존재한다면 A지원자는 탈락)"
      ],
      "metadata": {
        "id": "EGBtVmbtt3Fw"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "키를 기준으로 내림차순을 하면, 키가 작은 지원자들은 나보다 키가 큰 지원자의 몸무게를 이겨야 한다.  \n",
        "(즉, 몸무게를 이길 때마다 갱신시키고 cnt하면 정답)\n"
      ],
      "metadata": {
        "id": "hm9Ju3NhwzP5"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# 키, 몸무게 둘 중 하나는 다른 지원자보다 뛰어나야 탈락이 안된다.\n",
        "n = int(input())\n",
        "body = []\n",
        "for i in range(n):\n",
        "    h, w = map(int, input().split())\n",
        "    body.append((h,w))\n",
        "body.sort(reverse=True) #내림차순\n",
        "\n",
        "largest=0\n",
        "cnt=0\n",
        "for x,y in body:\n",
        "    if y > largest:\n",
        "        largest=y\n",
        "        cnt+=1\n",
        "print(cnt)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "5tsxwH3eusxv",
        "outputId": "39a274a5-4d89-40d0-ae9d-eff613a41006"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5\n",
            "172  67\n",
            "183 65\n",
            "180 70\n",
            "170 72\n",
            "181 60\n",
            "3\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 7. 창고 정리 (그리디 알고리즘)"
      ],
      "metadata": {
        "id": "lE5v8hnYpsaN"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "창고 높이 조정 : 가장 높은 곳에 있는 상자를 가장 낮은 곳으로 이동. (여러개가 가장 높거나 낮으면 아무거나 선택하면 된다)  \n",
        "창고의 가로 길이와 각 열의 상자 높이가 주어지는데, m회의 높이 조정을 한 후 가장 높은 곳과 가장 낮은 곳의 차이를 출력하시오."
      ],
      "metadata": {
        "id": "9HpPMVhcxqBD"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "list에 있는 값 중에서 가장 큰 값을 계속 작은 값에게 +1씩 준다. (cnt +1)  \n",
        "이때, 가장 큰 값이 바뀐다면 바꿔주기"
      ],
      "metadata": {
        "id": "g81l3mJ2zKMe"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "L = int(input())\n",
        "a = list(map(int, input().split()))\n",
        "m = int(input())\n",
        "a.sort()\n",
        "for _ in range(m):\n",
        "    a[0]+=1\n",
        "    a[-1]-=1\n",
        "    a.sort()\n",
        "print(a[-1] - a[0])"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "VqXNS1obxjOi",
        "outputId": "deedf2de-f6b2-4c42-beca-b71f1d81568d"
      },
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "10\n",
            "69 42 68 76 40 87 14 65 76 81\n",
            "50\n",
            "20\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 8. 침몰하는 타이타닉 (그리디 알고리즘)"
      ],
      "metadata": {
        "id": "wasoq53upvQ3"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "구명보트 2명 이하로만 탈 수 있으며, 보트 한 개에 탈 수 있는 총 무게도 Mkg 이하로 제한.  \n",
        "N명의 승객 몸무게 주어졌을 때, 탈출 위한 구명보트 최소 개수 출력"
      ],
      "metadata": {
        "id": "pyHrBOQp0hwX"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "n, m = map(int, input().split())\n",
        "p = list(map(int, input().split()))\n",
        "p.sort()  # 50, 60, 70, 90, 100\n",
        "cnt = 0\n",
        "\n",
        "# 승객 리스트가 빌 때까지 반복\n",
        "while p:\n",
        "    # 승객이 한 명만 남았을 경우, 혼자서 보트를 타야 하므로\n",
        "    if len(p) == 1:\n",
        "        cnt += 1\n",
        "        break\n",
        "\n",
        "    # 가장 가벼운 사람과 가장 무거운 사람의 무게가 m보다 큰 경우\n",
        "    if p[0] + p[-1] > m:\n",
        "        p.pop()   # 가장 무거운 사람만 태우고 리스트에서 제거\n",
        "        cnt += 1\n",
        "    else:\n",
        "        # 가장 가벼운 사람과 가장 무거운 사람이 함께 탈 수 있는 경우\n",
        "        p.pop(0)\n",
        "        p.pop()\n",
        "        cnt += 1\n",
        "\n",
        "print(cnt)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "60dLU-xn1E30",
        "outputId": "73a9f572-ac18-4cc8-a17d-568534c13eeb"
      },
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5 140\n",
            "90 50 70 100 60\n",
            "3\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 9. 증가 수열 만들기 (그리디 알고리즘)"
      ],
      "metadata": {
        "id": "dqkSW2rupyGv"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "n = int(input())\n",
        "a = list(map(int, input().split()))\n",
        "\n",
        "lt = 0\n",
        "rt = n - 1\n",
        "last = 0\n",
        "res = \"\"\n",
        "tmp = []\n",
        "\n",
        "# lt와 rt가 교차할 때까지 반복\n",
        "while lt <= rt:\n",
        "    if a[lt] > last:\n",
        "        tmp.append((a[lt], 'L'))\n",
        "\n",
        "    if a[rt] > last:\n",
        "        tmp.append((a[rt], 'R'))\n",
        "\n",
        "    # tmp 리스트를 정렬하여 가장 작은 값을 선택하기 쉽게 만듦\n",
        "    tmp.sort()\n",
        "\n",
        "    # 더 이상 선택할 수 있는 숫자가 없다면 반복문을 종료\n",
        "    if len(tmp) == 0:\n",
        "        break\n",
        "\n",
        "    else:\n",
        "        res = res + tmp[0][1]\n",
        "\n",
        "        # last를 tmp의 첫 번째 요소의 숫자로 업데이트 (선택된 숫자를 last로 기록)\n",
        "        last = tmp[0][0]\n",
        "\n",
        "        # tmp의 첫 번째 요소의 방향에 따라 lt 또는 rt를 이동\n",
        "        if tmp[0][1] == 'L':\n",
        "            lt += 1\n",
        "        else:\n",
        "            rt -= 1\n",
        "\n",
        "    tmp.clear()\n",
        "\n",
        "print(len(res))\n",
        "print(res)"
      ],
      "metadata": {
        "id": "4ZhpxETt6zyB",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "35e147a6-dd37-48da-8b96-2e47fbe460ec"
      },
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5\n",
            "2 4 5 1 3\n",
            "4\n",
            "LRLL\n"
          ]
        }
      ]
    }
  ]
}