notes/Codingtest_Binarysearch.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4225462f",
   "metadata": {},
   "source": [
    "# 이진 탐색"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "d1506157",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "value in left.\n",
      "value in left.\n",
      "value in left.\n",
      "value in left.\n",
      "value on right.\n",
      "value in left.\n",
      "value in left.\n",
      "value in left.\n",
      "value on right.\n",
      "value in left.\n",
      "value on right.\n",
      "value on right.\n",
      "value in left.\n",
      "value in left.\n",
      "value in left.\n",
      "find!\n",
      "find: 3511\n",
      "3511\n"
     ]
    }
   ],
   "source": [
    "# 재귀를 이용한 구현\n",
    "array = [i for i in range(1,103501)]\n",
    "\n",
    "def binary_search(array, value, start, end):\n",
    "    if start > end:\n",
    "        return None\n",
    "    else:\n",
    "        # 중간점 찾기\n",
    "        mid = (start + end) // 2\n",
    "        \n",
    "        # 탐색해서 있으면 반환\n",
    "        if array[mid] == value:\n",
    "            print('find!')\n",
    "            print('find:', mid)\n",
    "            return mid\n",
    "            \n",
    "        # 중간값보다 작으면 왼쪽 탐색\n",
    "        elif value < array[mid]:\n",
    "            print('value in left.')\n",
    "            return binary_search(array, value, start, mid-1)\n",
    "            \n",
    "        # 중간값보다 크면 오른쪽 탐색\n",
    "        else:\n",
    "            print('value on right.')\n",
    "            return binary_search(array, value, mid+1, end)\n",
    "            \n",
    "print(binary_search(array, 3512, 0, len(array)-1))\n",
    "\n",
    "        \n",
    "        \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "5d893e9b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "go left\n",
      "go left\n",
      "go left\n",
      "go left\n",
      "go right\n",
      "go left\n",
      "go left\n",
      "go left\n",
      "go right\n",
      "go left\n",
      "go right\n",
      "go right\n",
      "go left\n",
      "go left\n",
      "go left\n",
      "Value found!\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3511"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 반복문을 이용한 구현\n",
    "array = [i for i in range(1, 103501)]\n",
    "\n",
    "def binary_search_loop(array, value, start, end):\n",
    "    while start <= end:\n",
    "        mid = (start + end) // 2\n",
    "        if array[mid] == value:\n",
    "            print('Value found!')\n",
    "            return mid\n",
    "        \n",
    "        elif value < array[mid]:\n",
    "            print('go left')\n",
    "            end = mid-1\n",
    "            continue\n",
    "        \n",
    "        else:\n",
    "            print('go right')\n",
    "            start = mid+1\n",
    "            continue\n",
    "    \n",
    "    return None\n",
    "        \n",
    "binary_search_loop(array, 3512, 0, len(array)-1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cbb58e9a",
   "metadata": {},
   "source": [
    "## 빠르게 입력받기\n",
    "sys.stdin.readline() 을 이용한다"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "715bd79a",
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "input_data = sys.stdin.readline().rstrip()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8e3fc85",
   "metadata": {},
   "source": [
    "## 실전문제 - 부품 찾기"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ccabd4d6",
   "metadata": {},
   "outputs": [],
   "source": [
    "N = 5\n",
    "[8, 3, 7, 9, 2]\n",
    "\n",
    "M = 3\n",
    "[5, 7, 9]\n",
    "순서대로 부품 확인. 있으면 yes, 없으면 no 출력"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "8a7280ee",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 no 7 yes 9 yes CPU times: user 247 µs, sys: 109 µs, total: 356 µs\n",
      "Wall time: 297 µs\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "# N = int(input())\n",
    "# store = [int(i) for i in input().split(' ')]\n",
    "# M = int(input())\n",
    "# call = [int(j) for j in input().split(' ')]\n",
    "\n",
    "# 이진탐색\n",
    "def binary_search(array, value, start, end):\n",
    "    array = sorted(array)\n",
    "    if start > end:\n",
    "        return False\n",
    "    else:\n",
    "        mid = (start + end) // 2\n",
    "        if array[mid] == value:\n",
    "            return True\n",
    "        elif value < array[mid]:\n",
    "            return binary_search(array, value, start, mid-1)\n",
    "        else:\n",
    "            return binary_search(array, value, mid+1, end)\n",
    "            \n",
    "\n",
    "# store = [i for i in range(1000000)]\n",
    "# call = [random.randint(1,1530103) for _ in range(1000)]\n",
    "\n",
    "\n",
    "for num in call:\n",
    "    if binary_search(store, num, 0, len(store)-1):\n",
    "        print(num, 'yes', end=' ')\n",
    "    else:\n",
    "        print(num, 'no', end=' ')\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "a66d40bb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 no 7 yes 9 yes CPU times: user 513 µs, sys: 297 µs, total: 810 µs\n",
      "Wall time: 706 µs\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "## 계수 정렬을 적용하기\n",
    "def array_sort(array):\n",
    "    idx_arr = [0]*(max(array)+1)\n",
    "    for i in array:  # O(N)\n",
    "        idx_arr[i] += 1\n",
    "        \n",
    "    sort_arr = []\n",
    "    for j in range(len(idx_arr)):\n",
    "        if idx_arr[j] != 0:\n",
    "            sort_arr += [j]*idx_arr[j]\n",
    "    return sort_arr\n",
    "\n",
    "\n",
    "# 계수 정렬 적용한 이진탐색\n",
    "def binary_search(array, value, start, end):\n",
    "    array = array_sort(array)\n",
    "    if start > end:\n",
    "        return False\n",
    "    else:\n",
    "        mid = (start + end) // 2\n",
    "        if array[mid] == value:\n",
    "            return True\n",
    "        elif value < array[mid]:\n",
    "            return binary_search(array, value, start, mid-1)\n",
    "        else:\n",
    "            return binary_search(array, value, mid+1, end)\n",
    "            \n",
    "\n",
    "# store = [i for i in range(1000000)]\n",
    "# call = [random.randint(1,1530103) for _ in range(1000)]\n",
    "\n",
    "\n",
    "for num in call:\n",
    "    if binary_search(store, num, 0, len(store)-1):\n",
    "        print(num, 'yes', end=' ')\n",
    "    else:\n",
    "        print(num, 'no', end=' ')\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "313fca51",
   "metadata": {},
   "source": [
    "## 실전문제 - 떡볶이 떡 만들기"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ba5aa8d2",
   "metadata": {},
   "outputs": [],
   "source": [
    "총길이 M 일때 적어도 M길이만큼의 떡 얻기 위해서 \n",
    "절단기에 설정할 수 있는 높이의 최댓값 설정하기\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5aee13c8",
   "metadata": {},
   "outputs": [],
   "source": [
    "19 15 10 17 - -> 6센티 가져가기 위해 최대 15센티 높이로 자르면 됨. 딱 6센티.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e8a8d19f",
   "metadata": {},
   "outputs": [],
   "source": [
    "Sum(x - 절단기길이) >= Mcm 일때 등식이 성립하는 절단기길이를 구해야함.\n",
    "\n",
    "일단 제일 큰 떡의 길이부터 낮춰가면서 찾으면된다.\n",
    "\n",
    "19 , 18, 17, 16, 15\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "2e5fa561",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n"
     ]
    }
   ],
   "source": [
    "M = 6\n",
    "dd = [19,15,10,17]\n",
    "\n",
    "for cut in range(max(dd),0,-1):\n",
    "    dsum = sum([i-cut for i in dd if i-cut >= 0])\n",
    "    if dsum >= M:\n",
    "        break\n",
    "        \n",
    "print(cut)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "f1f7d216",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000000 1353183562\n"
     ]
    }
   ],
   "source": [
    "N, M = map(int, input().split(' '))\n",
    "\n",
    "import random\n",
    "dlist = [random.randint(0,1e9) for _ in range(N)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "id": "58462d79",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "499999398\n",
      "125153203788561\n",
      "higher the cut\n",
      "749999097\n",
      "31301439252552\n",
      "higher the cut\n",
      "874998947\n",
      "7822562308118\n",
      "higher the cut\n",
      "937498872\n",
      "1953173882655\n",
      "higher the cut\n",
      "968748834\n",
      "487763378707\n",
      "higher the cut\n",
      "984373815\n",
      "121145716716\n",
      "higher the cut\n",
      "992186306\n",
      "30592991362\n",
      "higher the cut\n",
      "996092551\n",
      "7798168185\n",
      "higher the cut\n",
      "998045674\n",
      "1982726245\n",
      "higher the cut\n",
      "999022235\n",
      "487938469\n",
      "lower the cut\n",
      "998533954\n",
      "1107447352\n",
      "lower the cut\n",
      "998289814\n",
      "1513634017\n",
      "higher the cut\n",
      "998411884\n",
      "1302416475\n",
      "lower the cut\n",
      "998350849\n",
      "1406165752\n",
      "higher the cut\n",
      "998381366\n",
      "1353845571\n",
      "higher the cut\n",
      "998396625\n",
      "1328038302\n",
      "lower the cut\n",
      "998388995\n",
      "1340921945\n",
      "lower the cut\n",
      "998385180\n",
      "1347374214\n",
      "lower the cut\n",
      "998383273\n",
      "1350607485\n",
      "lower the cut\n",
      "998382319\n",
      "1352227377\n",
      "lower the cut\n",
      "998381842\n",
      "1353037323\n",
      "lower the cut\n",
      "998381604\n",
      "1353441447\n",
      "higher the cut\n",
      "998381723\n",
      "1353239385\n",
      "higher the cut\n",
      "998381782\n",
      "1353139203\n",
      "lower the cut\n",
      "998381752\n",
      "1353190143\n",
      "higher the cut\n",
      "998381767\n",
      "1353164673\n",
      "lower the cut\n",
      "998381759\n",
      "1353178257\n",
      "lower the cut\n",
      "998381755\n",
      "1353185049\n",
      "higher the cut\n",
      "998381757\n",
      "1353181653\n",
      "lower the cut\n",
      "998381756\n",
      "1353183351\n",
      "lower the cut\n",
      "None\n",
      "998381755\n",
      "CPU times: user 1.28 s, sys: 15.3 ms, total: 1.3 s\n",
      "Wall time: 1.3 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "# 자르는걸 이진탐색!\n",
    "# def d_sum(dlist, cut):\n",
    "#     return sum\n",
    "\n",
    "dlist_sort = sorted(dlist)\n",
    "\n",
    "cut_list = []\n",
    "def cut_binary(duk_arr, duk_len, start, end):\n",
    "    if start > end:\n",
    "        return None\n",
    "    else:\n",
    "        mid = (start + end) // 2\n",
    "        print(mid)\n",
    "        # mid 위로만 해서 자른 길이들을 합한다\n",
    "        cut_sum = sum([duk-mid for duk in duk_arr if duk-mid > 0])\n",
    "        print(cut_sum)\n",
    "        if cut_sum == duk_len:\n",
    "            cut_list.append(mid)\n",
    "            print('matched')\n",
    "            return None\n",
    "        elif cut_sum < duk_len:\n",
    "            print('lower the cut')\n",
    "            # 더 떡 많이 잘라야 하므로 높이를 낮춘다\n",
    "            return cut_binary(duk_arr, duk_len, start, mid-1)\n",
    "        else:\n",
    "            # 떡이 남는 경우 - 자른길이들을 저장한다 - 저장된 길이들중 최소값을 뽑는다\n",
    "            print('higher the cut')\n",
    "            cut_list.append(mid)\n",
    "            return cut_binary(duk_arr, duk_len, mid+1, end)\n",
    "            \n",
    "        \n",
    "print(cut_binary(dlist_sort, M, 0, max(dlist_sort)))\n",
    "print(max(cut_list))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "id": "c6db2c57",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12\n",
      "34\n",
      "higher the cut\n",
      "19\n",
      "9\n",
      "lower the cut\n",
      "15\n",
      "21\n",
      "higher the cut\n",
      "17\n",
      "15\n",
      "higher the cut\n",
      "18\n",
      "12\n",
      "higher the cut\n",
      "None\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[12, 15, 17, 18]"
      ]
     },
     "execution_count": 119,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cut_list = []\n",
    "print(cut_binary([1,3,7,10,13,15,19,22,25],11,0,25))\n",
    "cut_list"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cb8af8b8",
   "metadata": {},
   "source": [
    "위 문제는 재귀적으로 풀었을 때 귀찮아지므로, 반복문을 통해서 푸는 것이 더 간결하다.  \n",
    "재귀적 접근 해보고 안되겠다 싶으면 반복문으로 가자"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "DA",
   "language": "python",
   "name": "da"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}