ch7_이진탐색.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "ch7_이진탐색",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyPcqFNOVQX5j4ycy5De2Nez",
      "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/ch7_%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# 순차탐색 Sequential Search\n",
        "- 한 마디로 말하자면\n",
        "  - 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 \n",
        "- 좀 더 자세히 말하자면\n",
        "  - 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용\n",
        "  - 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있음\n",
        "  - 정~말 많이 사용됨. 리스트에서 특정 값의 원소가 있는지 체크/ 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드 이용\n",
        "\n"
      ],
      "metadata": {
        "id": "Me9xoAyU8mXO"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 159
        },
        "id": "63sJEcC08hlz",
        "outputId": "0f5f3d1e-17c3-4738-bb9a-7c14f7061b7e"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.\n",
            "7 ES\n",
            "앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.\n",
            "JY JH DH WJ YJ GM ES\n",
            "7\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'\\n생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.\\n7 ES\\n앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.\\nJY JH DH WJ YJ GM ES\\n7\\n'"
            ],
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            }
          },
          "metadata": {},
          "execution_count": 1
        }
      ],
      "source": [
        "#- 예제 7-1. 순차 탐색\n",
        "\n",
        "def sequential_search(n, target, array):\n",
        "  '''\n",
        "  Args:\n",
        "    n: 배열의 크기 (원소 수) \n",
        "    target: 배열에서 찾고자 하는 원소 \n",
        "    array: 탐색 대상 배열 \n",
        "\n",
        "  Returns:\n",
        "    index\n",
        "  '''\n",
        "\n",
        "  # 각 원소를 하나씩 확인하며\n",
        "  for i in range(n):\n",
        "      # 현재의 원소가 찾고자 하는 원소와 동일한 경우\n",
        "      if array[i] == target:\n",
        "          return i + 1 # 현재의 위치 반환 (인덱스는 0부터 시작하므로 1 더하기)\n",
        "  return -1 # 원소를 찾지 못한 경우 -1 반환\n",
        "\n",
        "print(\"생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.\")\n",
        "input_data = input().split() #- ['6', 'ES']\n",
        "n = int(input_data[0]) # 원소의 개수, 6\n",
        "target = input_data[1] # 찾고자 하는 문자열, 'ES'\n",
        "\n",
        "print(\"앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.\")  \n",
        "array = input().split()\n",
        "\n",
        "# 순차 탐색 수행 결과 출력\n",
        "print(sequential_search(n, target, array))\n",
        "\n",
        "'''\n",
        "생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.\n",
        "7 ES\n",
        "앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.\n",
        "JY JH DH WJ YJ GM ES\n",
        "7\n",
        "'''"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "\n",
        "# 이진탐색 Binary Search\n",
        "\n",
        "- 한 마디로 말하자면\n",
        "  - 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘\n",
        "- 좀 더 자세히 말하자면\n",
        "  - 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.\n",
        "  - 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있음. \n",
        "  - 위치를 나타내는 변수 3개를 사용하는데, 시작점, 끝점, 중간점이다. \n",
        "  - 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색 과정이다. "
      ],
      "metadata": {
        "id": "seIUc6if_Zvc"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#- 예제 7-2\n",
        "# 이진 탐색 소스코드 구현 (재귀 함수)\n",
        "def binary_search(array, target, start, end):\n",
        "    '''\n",
        "    Args:\n",
        "      array: 배열 \n",
        "      target: 찾고자 하는 원소\n",
        "      start: 시작점(인덱스)\n",
        "      end: 끝점(인덱스)\n",
        "    Reutrns:\n",
        "      타겟 원소의 인덱스\n",
        "    '''\n",
        "    if start > end: \n",
        "        return None\n",
        "    mid = (start + end) // 2 #- // 은 몫 반환\n",
        "    #- mid는 중간점의 인덱스 \n",
        "    \n",
        "    # 찾은 경우 중간점 인덱스 반환\n",
        "    if array[mid] == target: #- 중간점과 타겟 요소가 동일하면, \n",
        "        return mid #- 중간점과 타겟 요소가 동일하면 중간점의 인덱스를 반환 \n",
        "\n",
        "    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인\n",
        "    elif array[mid] > target:  \n",
        "        return binary_search(array, target, start, mid - 1) #- 재귀문 실행\n",
        "\n",
        "\n",
        "    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인\n",
        "    else:\n",
        "        return binary_search(array, target, mid + 1, end) #- 재귀문 실행 \n",
        "\n",
        "# n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기(띄어쓰기 단위)\n",
        "n, target = list(map(int, input().split()))\n",
        "# 전체 원소 입력 받기\n",
        "array = list(map(int, input().split()))\n",
        "\n",
        "# 이진 탐색 수행 결과 출력\n",
        "result = binary_search(array, target, 0, n - 1)\n",
        "if result == None:\n",
        "    print(\"원소가 존재하지 않습니다.\")\n",
        "else:\n",
        "    print(result + 1)\n",
        "'''\n",
        "10 7\n",
        "1 3 5 7 9 11 13 15 17 19\n",
        "4\n",
        "'''"
      ],
      "metadata": {
        "id": "f1nBvRUAAcSJ",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "2ccbf29c-f009-465c-f4ad-2c99ad85f06c"
      },
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "10 7\n",
            "1 3 5 7 9 11 13 15 17 19\n",
            "4\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def binary_search(array, target, start, end):\n",
        "    \n",
        "    '''\n",
        "      Args:\n",
        "        array: 배열 \n",
        "        target: 찾고자 하는 원소\n",
        "        start: 시작점(인덱스)\n",
        "        end: 끝점(인덱스)\n",
        "      Reutrns:\n",
        "        타겟 원소의 인덱스\n",
        "    '''\n",
        "    if start > end: \n",
        "        return None\n",
        "    mid = (start + end) // 2 #- // 은 몫 반환\n",
        "    #- mid는 중간점의 인덱스 \n",
        "    \n",
        "    # 찾은 경우 중간점 인덱스 반환\n",
        "    if array[mid] == target: #- 중간점과 타겟 요소가 동일하면, \n",
        "        return mid #- 중간점과 타겟 요소가 동일하면 중간점의 인덱스를 반환 \n",
        "    \n",
        "    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인\n",
        "    elif array[mid] > target:  \n",
        "        return binary_search(array, target, start, mid - 1) #- 재귀문 실행\n",
        "    \n",
        "    \n",
        "    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인\n",
        "    else:\n",
        "        return binary_search(array, target, mid + 1, end) #- 재귀문 실행 \n",
        "\n",
        "# n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기\n",
        "n, target = list(map(int, input().split()))\n",
        "# 전체 원소 입력 받기\n",
        "array = list(map(int, input().split()))\n",
        "\n",
        "# sort\n",
        "array.sort()\n",
        "# sorted(array)\n",
        "\n",
        "# 이진 탐색 수행 결과 출력\n",
        "result = binary_search(array, target, 0, n - 1)\n",
        "if result == None:\n",
        "    print(\"원소가 존재하지 않습니다.\")\n",
        "else:\n",
        "    print(result + 1)\n"
      ],
      "metadata": {
        "id": "g6L0DTYqjCdR",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "45f49c03-5b2a-4fa7-9ac6-fd8708f97f9c"
      },
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "10 7\n",
            "1 3 5 7 9 11 13 15 17 19\n",
            "4\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#- 예제 7-3\n",
        "# 이진 탐색 소스코드 구현 (반복문)\n",
        "def binary_search(array, target, start, end):\n",
        "    while start <= end:\n",
        "        mid = (start + end) // 2\n",
        "        # 찾은 경우 중간점 인덱스 반환\n",
        "        if array[mid] == target:\n",
        "            return mid\n",
        "        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인\n",
        "        elif array[mid] > target:\n",
        "            end = mid - 1\n",
        "        # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인\n",
        "        else:\n",
        "            start = mid + 1\n",
        "    return None\n",
        "\n",
        "# n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기\n",
        "n, target = list(map(int, input().split()))\n",
        "# 전체 원소 입력 받기\n",
        "array = list(map(int, input().split()))\n",
        "\n",
        "# 이진 탐색 수행 결과 출력\n",
        "result = binary_search(array, target, 0, n - 1)\n",
        "if result == None:\n",
        "    print(\"원소가 존재하지 않습니다.\")\n",
        "else:\n",
        "    print(result + 1)\n",
        "'''\n",
        "10 7 \n",
        "1 3 5 7 9 11 13 15 17 19\n",
        "4\n",
        "'''"
      ],
      "metadata": {
        "id": "v1K0MVm-GSsU",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 88
        },
        "outputId": "14b5c17a-b788-440f-fdc5-c61d5ef3244c"
      },
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "10 7 \n",
            "1 3 5 7 9 11 13 15 17 19\n",
            "4\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'\\n7 57\\n57 8 24 9 10 2 678\\n6\\n'"
            ],
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            }
          },
          "metadata": {},
          "execution_count": 8
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## 트리 자료구조 \n",
        "\n",
        "- 데이터 베이스는 내부적으로 대용량 데이터 처리에 적합한 트리 자료구조를 이용해 항상 데이터 구조가 정렬되어 있음. \n",
        "- 따라서 데이터베이스에서의 탐색은 이진 탐색과 조금 다르지만, 이와 유사한 방법을 이용해 탐색을 항상 빠르게 수행하도록 설계되어 있어 데이터가 많아도 탐색 속도가 빠름\n",
        "- 트리구조의 주요특징\n",
        "  - 트리는 부모 노드와 자식 노드의 관계로 표현됨\n",
        "  - 트리의 최상단 노드를 루트 노드라 함\n",
        "  - 트리의 최하단 노드를 단말 노드라 함\n",
        "  - 트리에서 일부를 떼어내도 트리구조이며, 이를 서브 트리라고 함\n",
        "  - 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합함.\n",
        "\n",
        "## 이진 탐색 트리 \n",
        "- 트리 자료구조 중에서 가장 간단한 형태 \n",
        "- 이진 탐색 트리의 특징\n",
        "  - 부모 노드보다 왼쪽 자식 노드가 작다\n",
        "  - 부모 노드보다 오른쪽 자식 노드가 크다\n",
        "  - 왼쪽 자식 < 부모 노드 < 오른쪽 자식 \n",
        "- 이진 탐색 트리에 데이터를 넣고 빼는 방법은 알고리즘 보다는 자료구조임. \n",
        "- 이진 탐색 트리 자료구조를 구현하는 문제는 출제 빈도가 낮음 => 여기서는 데이터 조회 방법만 보자\n",
        "\n",
        "- 이진 탐색 문제는 입력 데이터가 많거나, 탐색 범위가 매우 넓은 편\n",
        "- 데이터의 개수가 1000만개를 넘거나, 탐색 범위의 크기가 1000억 이상일 때\n",
        "- 데이터의 개수가 많은 문제에 input() 함수를 이용하면, 동작 속도가 느려서 시간초과로 오답 판정을 받을 수 있음. => sys 라이브러리에 readline() 함수 이용 \n",
        "\n"
      ],
      "metadata": {
        "id": "vwcZm4G3GSNW"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#- 예제 7-4\n",
        "import sys #- 왜 안됨~~? \n",
        "\n",
        "# 하나의 문자열 데이터 입력 받기\n",
        "input_data = sys.stdin.readline().rstrip() \n",
        "#- readline() 은 입력 후 엔터가 줄바꿈 기호로 입력되기 때문에 rstrip() 사용\n",
        "\n",
        "# 입력 받은 문자열 그대로 출력하기\n",
        "print(input_data)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "krNP_xNoIsna",
        "outputId": "25fb74e6-96e8-49fe-ae32-64672a515261"
      },
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%%time\n",
        "#- 실전문제 2. 부품 찾기\n",
        "#- 7-5.이진탐색 \n",
        "'''\n",
        "- 문제 정리\n",
        "- 매장의 N개 부품이 있다. 각 부품은 정수 형태의 고유번호가 있다. \n",
        "- 손님이 M개 종류의 부품을 대량 구매하고 싶다.\n",
        "- 원하는 부품이 있으면 yes, 없으면 no 출력. 구분은 공백\n",
        "\n",
        "- 자연어 알고리즘\n",
        "1. 부품의 개수를 정수형으로 변수 n에 저장 \n",
        "2. 부품 번호를 공백으로 구분해서 입력받고, 정수형으로 변환한 리스트를 변수 array에 넣는다.\n",
        "3. 이진 탐색을 할것이므로, array를 정렬한다. \n",
        "4. 손님이 요청한 부품의 개수를 변수 m에 저장 \n",
        "5. 손님이 요청한 부품의 번호를 공백으로 구분해서 입력받고, 정수형으로 변환한 리스트를 변수 x에 넣는다.\n",
        "6. for 반복문 - x의 요소를 변수 i에 할당 \n",
        "    - target 인 변수 i가 array에 존재하는지 이진탐색 \n",
        "7. 조건문 - 타겟이 배열에 존재하면 ( != None)\n",
        "    - yes 출력\n",
        "  - 아니면\n",
        "    - no 출력 \n",
        "\n",
        "'''\n",
        "# 이진 탐색 소스코드 구현 (반복문)\n",
        "def binary_search(array, target, start, end):\n",
        "    while start <= end:\n",
        "        mid = (start + end) // 2\n",
        "        # 찾은 경우 중간점 인덱스 반환\n",
        "        if array[mid] == target:\n",
        "            return mid\n",
        "        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인\n",
        "        elif array[mid] > target:\n",
        "            end = mid - 1\n",
        "        # 중간점의 값보다 찾고자 하는 값이 작은 경우 오른쪽 확인\n",
        "        else:\n",
        "            start = mid + 1\n",
        "    return None\n",
        "\n",
        "# N(가게의 부품 개수) 입력\n",
        "n = int(input())\n",
        "# 가게에 있는 전체 부품 번호를 공백을 기준으로 구분하여 입력\n",
        "array = list(map(int, input().split()))\n",
        "array.sort() # 이진 탐색을 수행하기 위해 사전에 정렬 수행\n",
        "# M(손님이 확인 요청한 부품 개수) 입력\n",
        "m = int(input())\n",
        "# 손님이 확인 요청한 전체 부품 번호를 공백을 기준으로 구분하여 입력\n",
        "x = list(map(int, input().split()))\n",
        "\n",
        "# 손님이 확인 요청한 부품 번호를 하나씩 확인\n",
        "for i in x:\n",
        "    # 해당 부품이 존재하는지 확인\n",
        "    result = binary_search(array, i, 0, n - 1)\n",
        "    if result != None:\n",
        "        print('yes', end=' ')\n",
        "    else:\n",
        "        print('no', end=' ')\n",
        "'''\n",
        "5\n",
        "4 100 600 200 1000000\n",
        "2\n",
        "201 1000000\n",
        "no yes CPU times: user 104 ms, sys: 11.8 ms, total: 115 ms\n",
        "Wall time: 17.8 s\n",
        "'''"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "rBciKIXqKjqn",
        "outputId": "51f6786b-8213-46eb-8716-5954b3650309"
      },
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5\n",
            "4 100 600 200 1000000\n",
            "2\n",
            "201 1000000\n",
            "no yes CPU times: user 51.4 ms, sys: 9.48 ms, total: 60.9 ms\n",
            "Wall time: 11 s\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%%time\n",
        "#- 7-6.계수 정렬 \n",
        "# N(가게의 부품 개수) 입력\n",
        "n = int(input()) \n",
        "array = [0] * 1000001\n",
        "\n",
        "\n",
        "# 가게에 있는 전체 부품 번호를 입력 받아서 기록\n",
        "for i in input().split():\n",
        "    array[int(i)] = 1\n",
        "\n",
        "# M(손님이 확인 요청한 부품 개수) 입력\n",
        "m = int(input())\n",
        "# 손님이 확인 요청한 전체 부품 번호를 공백을 기준으로 구분하여 입력\n",
        "x = list(map(int, input().split()))\n",
        "\n",
        "# 손님이 확인 요청한 부품 번호를 하나씩 확인\n",
        "for i in x:\n",
        "    # 해당 부품이 존재하는지 확인\n",
        "    if array[i] == 1:\n",
        "        print('yes', end=' ')\n",
        "    else:\n",
        "        print('no', end=' ')\n",
        "'''\n",
        "5\n",
        "4 100 600 200 1000000\n",
        "2\n",
        "201 1000000\n",
        "no yes CPU times: user 465 ms, sys: 60.6 ms, total: 525 ms\n",
        "Wall time: 1min 30s\n",
        "'''"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "poiEyJ4CKuD_",
        "outputId": "14240fe6-f547-4ffd-cc33-ff7e08d96b5e"
      },
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5\n",
            "4 100 600 200 1000000\n",
            "2\n",
            "201 1000000\n",
            "no yes CPU times: user 50.4 ms, sys: 10.9 ms, total: 61.3 ms\n",
            "Wall time: 9.57 s\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%%time\n",
        "#- 7-7. 집합자료형 \n",
        "\n",
        "# N(가게의 부품 개수) 입력\n",
        "n = int(input())\n",
        "# 가게에 있는 전체 부품 번호를 입력 받아서 집합(Set) 자료형에 기록\n",
        "array = set(map(int, input().split()))\n",
        "\n",
        "# M(손님이 확인 요청한 부품 개수) 입력\n",
        "m = int(input())\n",
        "# 손님이 확인 요청한 전체 부품 번호를 공백을 기준으로 구분하여 입력\n",
        "x = list(map(int, input().split()))\n",
        "\n",
        "# 손님이 확인 요청한 부품 번호를 하나씩 확인\n",
        "for i in x:\n",
        "    # 해당 부품이 존재하는지 확인\n",
        "    if i in array:\n",
        "        print('yes', end=' ')\n",
        "    else:\n",
        "        print('no', end=' ')\n",
        "\n",
        "'''\n",
        "5\n",
        "4 100 600 200 1000000\n",
        "2\n",
        "201 1000000\n",
        "no yes CPU times: user 465 ms, sys: 60.6 ms, total: 525 ms\n",
        "Wall time: 1min 30s\n",
        "'''"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "DcE4-BlxKuxQ",
        "outputId": "49b9e79f-943e-4bf8-a58d-9b73e459aba2"
      },
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5\n",
            "4 100 600 200 1000000\n",
            "2\n",
            "201 1000000\n",
            "no yes CPU times: user 76.1 ms, sys: 8.18 ms, total: 84.2 ms\n",
            "Wall time: 14.8 s\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#- 실전문제 3.떡볶이 떡 만들기 \n",
        "#- 7-8. 파라메트릭 서치 (parametric search)\n",
        "\n",
        "# 떡의 개수(N)와 요청한 떡의 길이(M)을 입력\n",
        "n, m = list(map(int, input().split(' ')))\n",
        "# 각 떡의 개별 높이 정보를 입력\n",
        "array = list(map(int, input().split()))\n",
        "\n",
        "# 이진 탐색을 위한 시작점과 끝점 설정\n",
        "start = 0\n",
        "end = max(array)\n",
        "\n",
        "# 이진 탐색 수행 (반복적)\n",
        "result = 0\n",
        "while(start <= end):\n",
        "    total = 0\n",
        "    mid = (start + end) // 2\n",
        "    for x in array:\n",
        "        # 잘랐을 때의 떡볶이 양 계산\n",
        "        if x > mid:\n",
        "            total += x - mid\n",
        "    # 떡볶이 양이 부족한 경우 더 많이 자르기 (오른쪽 부분 탐색)\n",
        "    if total < m:\n",
        "        end = mid - 1\n",
        "    # 떡볶이 양이 충분한 경우 덜 자르기 (왼쪽 부분 탐색)\n",
        "    else:\n",
        "        result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록\n",
        "        start = mid + 1\n",
        "\n",
        "# 정답 출력\n",
        "print(result)\n",
        "'''\n",
        "5 5\n",
        "30 1 15 4 7\n",
        "25\n",
        "'''"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 88
        },
        "id": "O9e2aXt_K0Ok",
        "outputId": "ad56c220-3464-41f0-d0dd-0686a7123734"
      },
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5 5\n",
            "30 1 15 4 7\n",
            "25\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'\\n5 5\\n30 1 15 4 7\\n25\\n'"
            ],
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            }
          },
          "metadata": {},
          "execution_count": 13
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#- 동휘님 코드! \n",
        "def binary_search(start, end, target, array):\n",
        "  while start <= end:\n",
        "    height_sum = 0\n",
        "    mid = (start + end) // 2\n",
        "    for i in array:\n",
        "      if i - mid < 0:\n",
        "        continue\n",
        "      else: \n",
        "        height_sum += (i - mid) \n",
        "    if height_sum >= target:\n",
        "      start = mid + 1\n",
        "    else:\n",
        "      end = mid - 1\n",
        "  return end \n",
        "\n",
        "N, M = map(int,input().split())\n",
        "H_list = list(map(int,input().split()))\n",
        "end = max(H_list) \n",
        "print(binary_search(0, end, M, H_list))\n",
        "'''\n",
        "5 10\n",
        "30 1 15 4 7\n",
        "20\n",
        "'''"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 88
        },
        "id": "rAP_iCU_x7-e",
        "outputId": "938d0839-d117-45ce-9586-e949d6f8b1d0"
      },
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5 10\n",
            "30 1 15 4 7\n",
            "20\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'\\n5 10\\n30 1 15 4 7\\n20\\n'"
            ],
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            }
          },
          "metadata": {},
          "execution_count": 15
        }
      ]
    }
  ]
}