chpt7_binary_search.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "6cd4535d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하시오.\n",
      "5 Dongbin\n",
      "앞서 적은 원소 개수만큼 문자열을 입력하시오. 구분은 띄어쓰기 한 칸으로 합니다.\n",
      "Hanul Jonggu Dongbin Taeil Sangwook\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# 7-1. 순차 탐색 소스코드\n",
    "\n",
    "# 순차 탐색 소스코드 구현\n",
    "\n",
    "def sequential_search(n, target, array):\n",
    "    for i in range(n):\n",
    "        if array[i] == target:\n",
    "            return i+1\n",
    "        \n",
    "print(\"생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하시오.\")\n",
    "\n",
    "input_data = input().split()\n",
    "n = int(input_data[0])\n",
    "target = input_data[1]\n",
    "\n",
    "print(\"앞서 적은 원소 개수만큼 문자열을 입력하시오. 구분은 띄어쓰기 한 칸으로 합니다.\")\n",
    "array = input().split()\n",
    "\n",
    "print(sequential_search(n, target, array))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "52fa8414",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 7\n",
      "1 3 5 7 9 11 13 15 17 19\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "# 7-2. 재귀 함수로 구현한 이진 탐색 소스코드\n",
    "\n",
    "def binary_search(array, target, start, end):\n",
    "    if start > end:\n",
    "        return None\n",
    "    \n",
    "    mid = (start+end)//2 # 나머지 버림\n",
    "    \n",
    "    if array[mid] == target:\n",
    "        return mid\n",
    "    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인\n",
    "    elif array[mid]>target:\n",
    "        return binary_search(array, target, start, mid-1)\n",
    "    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인\n",
    "    else:\n",
    "        return binary_search(array, target, mid+1, end)\n",
    "\n",
    "# 원소의 개수와 target을 입력받기\n",
    "n, target = list(map(int, input().split()))\n",
    "\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(\"Target isn't existed.\")\n",
    "else:\n",
    "    print(result + 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "23d68530",
   "metadata": {},
   "outputs": [],
   "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",
    "        elif array[mid]>target:\n",
    "            end = mid-1\n",
    "        else:\n",
    "            start = mid+1\n",
    "    return None\n",
    "\n",
    "n, target = list(map(int, input().split()))\n",
    "\n",
    "array = list(map(int, input().split()))\n",
    "\n",
    "result = binary_search(array, target, 0, n-1)\n",
    "if result == None:\n",
    "    print(\"Target isn't existed.\")\n",
    "else:\n",
    "    print(result + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "8ecdc2df",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "# 7-4. 한 줄 입력받아 출력하는 소스코드\n",
    "\n",
    "import sys\n",
    "\n",
    "# 하나의 문자열 데이터 입력받기\n",
    "input_data = sys.stdin.readline().rstrip()\n",
    "\n",
    "print(input_data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "e59ee3d6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "8 3 7 9 2\n",
      "3\n",
      "5 7 9\n",
      "no yes yes "
     ]
    }
   ],
   "source": [
    "# 7-2 / 실전 문제 / 부품 찾기 written by me\n",
    "\n",
    "def binary_search(array, target, start, end):\n",
    "    if start >= end:\n",
    "        return None\n",
    "    mid = (start + end) // 2\n",
    "    if array[mid] == target:\n",
    "        return mid+1\n",
    "    elif array[mid] > target:\n",
    "        return binary_search(array, target, start, mid-1)\n",
    "    else:\n",
    "        return binary_search(array, target, mid+1, end)\n",
    "\n",
    "n = int(input())\n",
    "haveParts = list(map(int, input().split()))\n",
    "\n",
    "m = int(input())\n",
    "wantParts = list(map(int, input().split()))\n",
    "\n",
    "haveParts.sort()\n",
    "\n",
    "for i in wantParts:\n",
    "    if binary_search(haveParts, i, 0, n-1):\n",
    "        print(\"yes\", end=' ')\n",
    "    else:\n",
    "        print(\"no\", end=' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5527a470",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 7-5. 답안 예시 written by author\n",
    "\n",
    "def binary_search(array, target, start, end):\n",
    "    while start<=end:\n",
    "        mid = (start+end)//2\n",
    "        if array[mid] == target:\n",
    "            return mid\n",
    "        elif array[mid] > target:\n",
    "            end = mid-1\n",
    "        else:\n",
    "            start = mid+1\n",
    "    return None\n",
    "\n",
    "n = int(input())\n",
    "\n",
    "array = list(map(int, input().split()))\n",
    "\n",
    "array.sort()\n",
    "\n",
    "m = int(input())\n",
    "\n",
    "x = list(map(int, input().split()))\n",
    "\n",
    "for i in x:\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",
    "# 198p까지!, 계수 정렬 답안 예시는 작성해야 함"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "afcb7280",
   "metadata": {},
   "outputs": [
    {
     "ename": "KeyboardInterrupt",
     "evalue": "Interrupted by user",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[0;32m/var/folders/kn/gg6frwt12s7gcf_n79d00hy80000gn/T/ipykernel_3699/4200338773.py\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;31m# 7-6. 답안 예시(counting sort) written by author\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0mn\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0minput\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      4\u001b[0m \u001b[0marray\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0;36m100001\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/Library/Frameworks/Python.framework/Versions/3.10/lib/python3.10/site-packages/ipykernel/kernelbase.py\u001b[0m in \u001b[0;36mraw_input\u001b[0;34m(self, prompt)\u001b[0m\n\u001b[1;32m   1004\u001b[0m                 \u001b[0;34m\"raw_input was called, but this frontend does not support input requests.\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1005\u001b[0m             )\n\u001b[0;32m-> 1006\u001b[0;31m         return self._input_request(\n\u001b[0m\u001b[1;32m   1007\u001b[0m             \u001b[0mstr\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mprompt\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1008\u001b[0m             \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_parent_ident\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"shell\"\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/Library/Frameworks/Python.framework/Versions/3.10/lib/python3.10/site-packages/ipykernel/kernelbase.py\u001b[0m in \u001b[0;36m_input_request\u001b[0;34m(self, prompt, ident, parent, password)\u001b[0m\n\u001b[1;32m   1049\u001b[0m             \u001b[0;32mexcept\u001b[0m \u001b[0mKeyboardInterrupt\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1050\u001b[0m                 \u001b[0;31m# re-raise KeyboardInterrupt, to truncate traceback\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1051\u001b[0;31m                 \u001b[0;32mraise\u001b[0m \u001b[0mKeyboardInterrupt\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Interrupted by user\"\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   1052\u001b[0m             \u001b[0;32mexcept\u001b[0m \u001b[0mException\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1053\u001b[0m                 \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlog\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mwarning\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Invalid Message:\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mexc_info\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mTrue\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: Interrupted by user"
     ]
    }
   ],
   "source": [
    "# 7-6. 답안 예시(counting sort) written by author\n",
    "\n",
    "n = int(input())\n",
    "array = [0]*100001\n",
    "\n",
    "for i in input().split():\n",
    "    array[int(i)] = 1\n",
    "    \n",
    "m = int(input())\n",
    "\n",
    "x = list(map(int, input().split()))\n",
    "\n",
    "for i in x:\n",
    "    \n",
    "    if array[i] == 1:\n",
    "        print('yes', end =' ')\n",
    "    else:\n",
    "        print('no', end=' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1fa4aaa8",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 7-7. 답안 예시(using set data structure) written by author\n",
    "\n",
    "n = int(input())\n",
    "\n",
    "array = set(map(int, input().split()))\n",
    "\n",
    "m = int(input())\n",
    "\n",
    "x = list(map(int, input().split()))\n",
    "\n",
    "for i in x:\n",
    "    if i in array:\n",
    "        print('yes', end=' ')\n",
    "    else:\n",
    "        print('no', end=' ')\n",
    "        \n",
    "# set()함수는 집합 자료형을 초기화할 때 사용, 단순히 특정한 데이터가 존재하는지 검사할 때에 매우 효과적으로 사용할 수 있음\n",
    "# 이진 탐색으로도 충분히 풀 수 있지만, 여러가지 관점에서 풀 수 있도록 생각해보기!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "58f0f2ad",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 6\n",
      "19 15 10 17\n",
      "15\n"
     ]
    }
   ],
   "source": [
    "# 7-3 / 실전 문제 / 떡볶이 떡 만들기\n",
    "\n",
    "n, m = map(int, input().split())\n",
    "\n",
    "rc = list(map(int, input().split()))\n",
    "\n",
    "rc.sort()\n",
    "\n",
    "examine = 0\n",
    "val = rc[len(rc)-1]\n",
    "\n",
    "while True:\n",
    "    for i in range(len(rc)):\n",
    "        if val<rc[i]:\n",
    "            examine += (rc[i]-val)\n",
    "    \n",
    "    if examine < m:\n",
    "        val-=1\n",
    "        examine = 0\n",
    "    else:\n",
    "        break\n",
    "\n",
    "print(val)\n",
    "\n",
    "# review 필요! binary_search 문제인데 sequential search로 풀었음.\n",
    "# 실제 상황에서는 time out이 나왔을 지도 모르는 경우"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "6c45d983",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 6\n",
      "20 10 16 18\n",
      "10 15 20\n",
      "16\n"
     ]
    }
   ],
   "source": [
    "# 7-3 / 떡볶이 떡 자르기 / 실전 문제 / written by me\n",
    "\n",
    "n, m = map(int, input().split())\n",
    "\n",
    "arr = list(map(int, input().split()))\n",
    "\n",
    "arr.sort()\n",
    "\n",
    "start = arr[0]\n",
    "end = arr[len(arr)-1]\n",
    "mid = (start+end)//2\n",
    "\n",
    "print(start, mid, end)\n",
    "def remainCake(arr, mid):\n",
    "    result = 0\n",
    "    for i in arr:\n",
    "        if i > mid:\n",
    "            result+=(i-mid)\n",
    "            \n",
    "    return result\n",
    "\n",
    "pre_res = 0\n",
    "\n",
    "while True:\n",
    "    cur_res = remainCake(arr, mid)\n",
    "    \n",
    "    if cur_res < m:\n",
    "        end = mid\n",
    "        mid = ((start+end)//2)\n",
    "    \n",
    "    elif cur_res >= m:\n",
    "        if pre_res > cur_res:\n",
    "            break\n",
    "        else:\n",
    "            pre_res = cur_res\n",
    "            start = mid\n",
    "            mid = ((start+end)//2)\n",
    "    \n",
    "print(mid)\n",
    "\n",
    "# solve!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "e0c27d02",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 6\n",
      "19 10 16 17\n",
      "15\n"
     ]
    }
   ],
   "source": [
    "# 4-3 / 떡볶이 떡 자르기 / 실전 문제 / written by author\n",
    "\n",
    "# 떡의 개수와 요청한 떡의 길이를 입력받기\n",
    "\n",
    "n, m = list(map(int, input().split(' ')))\n",
    "\n",
    "array = list(map(int, input().split()))\n",
    "\n",
    "start = 0\n",
    "end = max(array)\n",
    "\n",
    "result = 0\n",
    "while(start <= end):\n",
    "    total = 0\n",
    "    mid = (start+end)//2\n",
    "    \n",
    "    for x in array:\n",
    "        if x > mid:\n",
    "            total+= x- mid\n",
    "            \n",
    "    # 떡의 양이 부족한 경우 더 많이 자르기 (왼쪽 부분 탐색)\n",
    "    if total < m:\n",
    "        end = mid-1\n",
    "    # 떡의 양이 충분한 경우 덜 자르기 (오른쪽 부분 탐색)\n",
    "    else:\n",
    "        result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록\n",
    "        start = mid+1\n",
    "        \n",
    "print(result)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "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.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}