선형_자료구조_공부중.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyP1z0F3esWe+UtBIaXpDv1i",
      "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/JounKK/Algorithm/blob/main/%EC%84%A0%ED%98%95_%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0_%EA%B3%B5%EB%B6%80%EC%A4%91.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",
        "- 즉, 알고리즘의 성능을 판단하는 2 기준\n",
        "- 시간 복잡도는 알고리즘이 시작되어 완료되는 데까지 걸리는 시간을 의미한다.\n",
        "    - 하지만 실제 실행 시간은 하드웨어 성능 혹은 프로그래밍 언어에 따라 값이 달라지기 때문에 고려하지 않는다.\n",
        "    - 따라서 알고리즘에서의 시간 복잡도란 실행 명령어의 실행 횟수를 뜻한다.\n",
        "- 공간 복잡도 또한 기본적으로 시간 복잡도와 동일하지만, 처리 시간 대신 메모리 사용량을 뜻한다."
      ],
      "metadata": {
        "id": "CE7wtuLbLmUs"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# 시간복잡도 함수\n"
      ],
      "metadata": {
        "id": "ROx4TE0rVIyw"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 빅오\n",
        "* 빅오 치트싯 : https://www.bigocheatsheet.com/\n",
        "\n",
        "각 자료구조 연산 별 시간복잡도\n"
      ],
      "metadata": {
        "id": "OISPQo5Ne5Rj"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# 리스트, 연결리스트(LinkedList)\n",
        "- Single LinkedList : 한방향으로만 연결됨\n",
        "- Double LinkedList : 양방향으로 왔다갔다 가능\n",
        "- 개념 : https://en.wikipedia.org/wiki/Linked_list\n",
        "- 알고리즘 시각화 : https://visualgo.net/ko\n",
        "- 스택, 데크, 트리 등에서 활용가능"
      ],
      "metadata": {
        "id": "W4-IsiGtUA5c"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "22, 2, 77, 6,\n",
        "# 이해하기 쉽도록 간결하게 구현한 링크드리스트입니다.\n",
        "# next 가 가리키고 있는 게 결국 다음 링크입니다.\n",
        "연결리스트 = {\n",
        "    'head' :{\n",
        "        'value' : 22,\n",
        "        'next' :{\n",
        "            'value' : 2,\n",
        "            'next' :{\n",
        "                'value' : 77,\n",
        "                'next' :{\n",
        "                    'value' : 6,\n",
        "                    'next' : None\n",
        "                }\n",
        "            }\n",
        "        }\n",
        "    }\n",
        "}"
      ],
      "metadata": {
        "id": "jRsvwU7KUC5i"
      },
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# 우리가 구현에서 실제 하고 싶은 코드\n",
        "연결리스트['head']['next']['next']['value']"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "_Bpie25h1zCx",
        "outputId": "9c6fa314-add6-498a-a863-44cf27fa631a"
      },
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "77"
            ]
          },
          "metadata": {},
          "execution_count": 2
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# 쉬운 방법 2\n",
        "연결리스트 = {\n",
        "    'head' : None\n",
        "}\n",
        "\n",
        "list1= {'value':22, 'next':None}\n",
        "list2= {'value': 2, 'next':None}\n",
        "list3= {'value':77, 'next':None}\n",
        "list4= {'value': 6, 'next':None}\n",
        "\n",
        "연결리스트['head']= list1\n",
        "list1['next'] = list2\n",
        "list2['next'] = list3\n",
        "list3['next'] = list4"
      ],
      "metadata": {
        "id": "0_-lMcUp10cS"
      },
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# 우리가 구현에서 실제 하고 싶은 코드\n",
        "연결리스트['head']['next']['next']['value']"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "NBnR2iCz12su",
        "outputId": "cbcacae0-eaa8-4d06-dacf-4b9a22823891"
      },
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "77"
            ]
          },
          "metadata": {},
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 문제를 통한 구현\n",
        "- head -> [90, next] -> [2, next] -> [77, next] -> [35, next] -> [21, next] -> None\n",
        "- 35를 출력해주세요."
      ],
      "metadata": {
        "id": "8twovTUm2IIF"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# 쉬운방법 1\n",
        "연결리스트 = {\n",
        "    'head' :{\n",
        "        'value' : 90,\n",
        "        'next' :{\n",
        "            'value' : 2,\n",
        "            'next' : {\n",
        "                'value' : 77,\n",
        "                'next' : {\n",
        "                    'value' : 35,\n",
        "                    'next' : {\n",
        "                        'value': 21,\n",
        "                        'next' : None\n",
        "                    }\n",
        "                }\n",
        "            }\n",
        "        }\n",
        "    }\n",
        "}"
      ],
      "metadata": {
        "id": "xirJecJa2Lix"
      },
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "연결리스트['head']['next']['next']['next']['value']"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "11urP_PU2nFA",
        "outputId": "0d070d1d-3472-4006-91ab-732a580867b9"
      },
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "35"
            ]
          },
          "metadata": {},
          "execution_count": 6
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# 쉬운방법 2\n",
        "연결리스트 = {\n",
        "    'head' : None\n",
        "}\n",
        "list1= {'value':90, 'next':None}\n",
        "list2= {'value':2, 'next':None}\n",
        "list3= {'value':77, 'next':None}\n",
        "list4= {'value':35, 'next':None}\n",
        "list5= {'value':21, 'next':None}\n",
        "\n",
        "연결리스트['head'] = list1\n",
        "list1['next'] = list2\n",
        "list2['next'] = list3\n",
        "list3['next'] = list4\n",
        "list4['next'] = list5"
      ],
      "metadata": {
        "id": "oKxJcuBW2z-Q"
      },
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "연결리스트['head']['next']['next']['next']['value']"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "w5vM_CQy3MvM",
        "outputId": "1ef50149-6ca6-4566-fbaf-e4662bc80604"
      },
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "35"
            ]
          },
          "metadata": {},
          "execution_count": 8
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### 노드를 만들어서 구현"
      ],
      "metadata": {
        "id": "9BB_rhwd30uC"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# 노드 만들기\n",
        "class Node:\n",
        "    def __init__(self, data):\n",
        "        self.data = data\n",
        "        self.next = None\n",
        "\n",
        "node1 = Node(90)\n",
        "node2 = Node(2)\n",
        "node3 = Node(77)\n",
        "node4 = Node(35)\n",
        "node5 = Node(21)\n",
        "\n",
        "# 수동 연결 -> 다음 노드 자동연결되도록\n",
        "node1.next = node2\n",
        "node2.next = node3\n",
        "node3.next = node4\n",
        "node4.next = node5\n",
        "\n",
        "# 호출 폼\n",
        "node1.next.next.next.data"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "jUt2RZkG3W1G",
        "outputId": "899abc7f-00a6-4015-9771-c94688a7f256"
      },
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "35"
            ]
          },
          "metadata": {},
          "execution_count": 9
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### 자동으로 다음 노드 연결되도록 구현"
      ],
      "metadata": {
        "id": "bH1EfOeX37tY"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class Node:\n",
        "    def __init__(self, data):\n",
        "        self.data = data\n",
        "        self.next = None\n",
        "\n",
        "# head -> ['init', next]\n",
        "#               ↑\n",
        "#              tail\n",
        "# head -> ['init', next] -> [90, next]\n",
        "#                               ↑\n",
        "#                              tail\n",
        "\n",
        "class LinkedList:\n",
        "    def __init__(self):\n",
        "        init = Node('init')\n",
        "        self.head = init\n",
        "        self.tail = init\n",
        "        self.데이터수 = 0\n",
        "\n",
        "    def append(self, data):\n",
        "        새로운노드 = Node(data)\n",
        "        self.tail.next = 새로운노드\n",
        "        self.tail = 새로운노드\n",
        "        self.데이터수 += 1\n",
        "\n",
        "l = LinkedList()\n",
        "l.append(90)\n",
        "l.append(2)\n",
        "l.append(77)\n",
        "l.append(35)\n",
        "l.append(21)\n",
        "\n",
        "print(l.head.next.next.next.next.data)\n",
        "\n",
        "# 이렇게 클래스화한 링크드리스트로 우리가 하고 싶은 것은?\n",
        "# 값 삽입\n",
        "# 값 삭제\n",
        "# 값 찾기\n",
        "# ....\n",
        "\n",
        "# 이렇게 구현하는 이유?\n",
        "# 1. 새로운 자료구조를 만들어야 할 때 (tree)\n",
        "# 2. 더 가벼운 자료형을 사용해야 할 때(이게 훨씬 가볍기 때문 !!)\n",
        "# 3. 기존에 있는 자료형에 추가 기능을 넣고 싶을 때"
      ],
      "metadata": {
        "id": "E1PpodwV3zX3"
      },
      "execution_count": 11,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### 추가 기능 구현\n",
        "- len, str, iter\n",
        "- 제너레이터 설명 : https://www.daleseo.com/python-yield/\n",
        "- append, pop, find, insert"
      ],
      "metadata": {
        "id": "Tx8oabL25Kyv"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class Node:\n",
        "    def __init__(self, data):\n",
        "        self.data = data\n",
        "        self.next = None\n",
        "\n",
        "class LinkedList:\n",
        "    def __init__(self):\n",
        "        init = Node('init')\n",
        "        self.head = init\n",
        "        self.tail = init\n",
        "        self.데이터수 = 0\n",
        "\n",
        "    def __len__(self):\n",
        "        return self.데이터수\n",
        "\n",
        "    def __str__(self):\n",
        "        현재노드 = self.head # init 노드임\n",
        "        현재노드 = 현재노드.next # 데이터 있는 노드로 변경\n",
        "        s =''\n",
        "\n",
        "        for i in range(self.데이터수):\n",
        "            s+= f'{현재노드.data}, '\n",
        "            현재노드 = 현재노드.next\n",
        "\n",
        "        return f'<{s[:-2]}>'\n",
        "\n",
        "    def __iter__(self):\n",
        "        현재노드 = self.head\n",
        "        현재노드 = 현재노드.next\n",
        "        while 현재노드:\n",
        "            yield 현재노드.data # yield는 결과값을 메모리에 하나씩 올림\n",
        "            현재노드 = 현재노드.next\n",
        "\n",
        "    def append(self, data):\n",
        "        새로운노드 = Node(data)\n",
        "        self.tail.next = 새로운노드\n",
        "        self.tail = 새로운노드\n",
        "        self.데이터수 += 1\n",
        "\n",
        "    def insert(self, input_index, input_data):\n",
        "        현재노드 = self.head\n",
        "\n",
        "        for i in range(input_index):\n",
        "            현재노드 = 현재노드.next\n",
        "\n",
        "        신규노드 = Node(input_data)\n",
        "        신규노드.next = 현재노드.next\n",
        "        현재노드.next = 신규노드\n",
        "\n",
        "        self.데이터수 += 1\n",
        "\n",
        "    def pop(self):\n",
        "        마지막값 = self.tail.data\n",
        "        현재노드 = self.head\n",
        "\n",
        "        for i in range(self.데이터수):\n",
        "            if 현재노드.next is self.tail:\n",
        "                self.tail = 현재노드\n",
        "                현재노드.next = None\n",
        "                break\n",
        "            현재노드 = 현재노드.next\n",
        "        self.데이터수 -= 1\n",
        "\n",
        "    def find(self, data):\n",
        "        index = -1\n",
        "        현재노드 = self.head\n",
        "\n",
        "        for i in range(self.데이터수+1):\n",
        "            if 현재노드.data == data:\n",
        "                return index\n",
        "            index += 1\n",
        "            현재노드 = 현재노드.next\n",
        "\n",
        "        if index == self.데이터수:\n",
        "            index = -1 # 값 못 찾으면 -1 반환\n",
        "\n",
        "        return index"
      ],
      "metadata": {
        "id": "jA66_zz34uBY"
      },
      "execution_count": 46,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "l = LinkedList()\n",
        "l.append(12)\n",
        "l.append(99)\n",
        "l.append(37)\n",
        "l.append(2)\n",
        "print(l.head.next.next.data)\n",
        "print(len(l))\n",
        "print(l)\n",
        "print(l.find(4400))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "cJW8EuujAPOV",
        "outputId": "83fee5eb-4816-4a7d-87bd-6019268a25ad"
      },
      "execution_count": 47,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "99\n",
            "4\n",
            "<12, 99, 37, 2>\n",
            "-1\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "l.insert(2, 1000)\n",
        "print(l)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "7-qiJULfAQXo",
        "outputId": "6b3e009b-a79c-4db0-fbbf-72e4b5ee48fd"
      },
      "execution_count": 48,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "<12, 99, 1000, 37, 2>\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 더블링크드리스트"
      ],
      "metadata": {
        "id": "CnCDef3eAfTt"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# 더블 링크드 리스트의 기본 형태\n",
        "# pre값이 추가되었다.\n",
        "\n",
        "배열 = {\n",
        "    'head': 'None'\n",
        "}\n",
        "\n",
        "list1 = {'value':12, 'next':None, 'pre':None}\n",
        "list2 = {'value':99, 'next':None, 'pre':None}\n",
        "list3 = {'value':37, 'next':None, 'pre':None}\n",
        "list4 = {'value':2, 'next':None, 'pre':None}\n",
        "list1['next'] = list2\n",
        "list2['next'] = list3\n",
        "list3['next'] = list4\n",
        "list1['pre']= 배열['head']\n",
        "list2['pre']= list1\n",
        "list3['pre']= list2\n",
        "list4['pre']= list3\n",
        "배열['head'] = list1"
      ],
      "metadata": {
        "id": "BPATtcBrAhMU"
      },
      "execution_count": 49,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# head <-> 12 <-> 99 <-> 37 <-> 2\n",
        "\n",
        "배열['head']['next']['value']\n",
        "배열['head']['next']['next']['value']\n",
        "배열['head']['next']['next']['pre']['value']"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "VEAVDClpAkfe",
        "outputId": "f423141d-6ae4-40ac-d65a-d93bab8bc268"
      },
      "execution_count": 50,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "99"
            ]
          },
          "metadata": {},
          "execution_count": 50
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# step 5 더블 링크드 리스트의 기본 형태(동작X)\n",
        "class Node:\n",
        "    def __init__(self, data):\n",
        "        self.data = data\n",
        "        self.pre = None\n",
        "        self.next = None\n",
        "\n",
        "# class DoubleLinkedList:\n",
        "    # # ... 중략 ...\n",
        "    # def append(self, data):\n",
        "    #     새로운노드 = Node(data)\n",
        "    #     self.tail.next = 새로운노드\n",
        "    #     새로운노드.pre = self.tail\n",
        "    #     self.tail = 새로운노드\n",
        "    # # ... 중략 ...\n",
        "\n",
        "\n",
        "# l = DoubleLinkedList()\n",
        "# l.append(1)"
      ],
      "metadata": {
        "id": "s2xoVkJEAmR2"
      },
      "execution_count": 55,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# 스택(Stack)\n",
        "- 말 그대로 자료를 쌓아올린다.\n",
        "- 그러니까 출입구는 하나. 먼저 들어온 것이 제일 아래쌓이면서 가장 나중에 들어온 게 먼저 나감\n",
        "- LIFO(Last In First Out)\n",
        "- ADT(adstract data type)\n",
        "    - push()\n",
        "    - pop()\n",
        "    - peek()/top()\n",
        "    - bottom()\n",
        "    - empty()\n",
        "\n",
        "- 모델 구현은 보통 링크드리스트로 하지만, 일단 리스트로 한 번 구현해보고 링크드 리스트로 해보겠음."
      ],
      "metadata": {
        "id": "orMWOFvMZz_T"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "jvmC9LVRZwmK",
        "outputId": "07c8ff6b-ac6a-46bd-f6c5-3e6576cb404d"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Stack이 생성되었습니다.\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "20"
            ]
          },
          "metadata": {},
          "execution_count": 1
        }
      ],
      "source": [
        "class Stack:\n",
        "    def __init__(self):\n",
        "        print(\"Stack이 생성되었습니다.\")\n",
        "        self.l = []\n",
        "\n",
        "    def push(self, data):\n",
        "        self.l.append(data)\n",
        "\n",
        "    def pop(self):\n",
        "        return self.l.pop()\n",
        "\n",
        "    def top(self):\n",
        "        return self.l[-1]\n",
        "\n",
        "    def bottom(self):\n",
        "        return self.l[0]\n",
        "\n",
        "    def empty(self):\n",
        "        if not self.l:\n",
        "            return 1\n",
        "        return 0\n",
        "\n",
        "s = Stack()\n",
        "s.push(10)\n",
        "s.push(20)\n",
        "s.top()\n",
        "s.pop()"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# 링크드리스트로 구현"
      ],
      "metadata": {
        "id": "rTN1uPhTbQ86"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "class Node:\n",
        "    def __init__(self, data):\n",
        "        self.data = data\n",
        "        self.next = None\n",
        "\n",
        "class Stack:\n",
        "    def __init__(self):\n",
        "        print(\"스택이 생성됨\")\n",
        "        self.head = None\n",
        "\n",
        "    def push(self, data):\n",
        "        새로운노드 = Node(data)\n",
        "        새로운노드.next = self.head\n",
        "        self.head = 새로운노드\n",
        "\n",
        "    def pop(self):\n",
        "        if self.is_empty():\n",
        "            return -1\n",
        "        data = self.head.data\n",
        "        self.head = self.head.next\n",
        "        return data\n",
        "\n",
        "    def is_empty(self):\n",
        "        if self.head:\n",
        "            return False\n",
        "        return True\n",
        "\n",
        "    def peek(self):\n",
        "        if self.is_empty():\n",
        "            return -1\n",
        "        return self.head.data"
      ],
      "metadata": {
        "id": "8epELUoU1jPn"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "s = Stack()\n",
        "s.push(10)\n",
        "s.push(20)\n",
        "s.push(30)\n",
        "s.pop()\n",
        "s.peek()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "V71_Jho23yx0",
        "outputId": "78afa78b-894e-49d5-a3e1-282ede4a9605"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "스택이 생성됨\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "20"
            ]
          },
          "metadata": {},
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## 백준 stack 문제\n",
        "* 문제링크 : https://www.acmicpc.net/problem/10828\n",
        "\n",
        "\n",
        "정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.\n",
        "명령은 총 다섯 가지이다.\n",
        "\n",
        "- push X: 정수 X를 스택에 넣는 연산이다.\n",
        "- pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.\n",
        "- size: 스택에 들어있는 정수의 개수를 출력한다.\n",
        "- empty: 스택이 비어있으면 1, 아니면 0을 출력한다.\n",
        "- top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.\n",
        "\n",
        "\n",
        "입력:\n",
        "\n",
        "첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.\n",
        "\n",
        "\n",
        "예시:\n",
        "\n",
        "7\n",
        "pop\n",
        "top\n",
        "push 123\n",
        "top\n",
        "pop\n",
        "top\n",
        "pop\n",
        "\n",
        "출력예시:\n",
        "-1\n",
        "-1\n",
        "123\n",
        "123\n",
        "-1\n",
        "-1"
      ],
      "metadata": {
        "id": "Y_pkJRBp59oQ"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# import sys\n",
        "# input = sys.stdin.readline\n",
        "\n",
        "# # N = int(input())\n",
        "# stack = []\n",
        "\n",
        "# for _ in range(N):\n",
        "#     cmd = input().strip().split()\n",
        "#     if cmd[0] == 'push':\n",
        "#         if len(cmd) > 1:\n",
        "#             stack.append(int(cmd[1]))\n",
        "#     elif cmd[0] == 'pop':\n",
        "#         if stack:\n",
        "#             print(stack.pop())\n",
        "#         else:\n",
        "#             print(-1)\n",
        "#     elif cmd[0] == 'size':\n",
        "#         print(len(stack))\n",
        "#     elif cmd[0] == 'empty':\n",
        "#         print(int(not stack))\n",
        "#     elif cmd[0] == 'top':\n",
        "#         if stack:\n",
        "#             print(stack[-1])\n",
        "#         else:\n",
        "#             print(-1)"
      ],
      "metadata": {
        "id": "nobG1fF7IQRm"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# import sys\n",
        "# input = sys.stdin.readline  # 이거 안쓰면 시간초과 됌\n",
        "\n",
        "class Node:\n",
        "    def __init__(self, data):\n",
        "        self.data = data\n",
        "        self.next = None\n",
        "\n",
        "class Stack:\n",
        "    def __init__(self):\n",
        "        self.head = None\n",
        "        self.데이터수 = 0\n",
        "\n",
        "    def push(self, data):\n",
        "        새로운노드 = Node(data)\n",
        "        새로운노드.next = self.head\n",
        "        self.head = 새로운노드\n",
        "        self.데이터수 += 1\n",
        "\n",
        "    def pop(self):\n",
        "        if self.empty():\n",
        "            return -1\n",
        "        data = self.head.data\n",
        "        self.head = self.head.next\n",
        "        self.데이터수 -= 1\n",
        "        return data\n",
        "\n",
        "    def size(self):\n",
        "        return self.데이터수\n",
        "\n",
        "    def empty(self):\n",
        "        return 0 if self.head else 1\n",
        "\n",
        "    def top(self):\n",
        "        return -1 if self.empty() else self.head.data"
      ],
      "metadata": {
        "id": "H67pZGA131xG"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# 링크드리스트 클래스로 스택 구현해둔 것 사용하기\n",
        "# n = int(input())\n",
        "# s = Stack()\n",
        "\n",
        "# for _ in range(n):\n",
        "#     cmd = input().split()\n",
        "#     if cmd[0] == 'push':\n",
        "#         s.push(int(cmd[1]))\n",
        "#     elif cmd[0] == 'pop':\n",
        "#         print(s.pop())\n",
        "#     elif cmd[0] == 'size':\n",
        "#         print(s.size())\n",
        "#     elif cmd[0] == 'empty':\n",
        "#         print(s.empty())\n",
        "#     elif cmd[0] == 'top':\n",
        "#         print(s.top())to\n",
        "#     else:\n",
        "#         print(\"unacceptable op\")\n"
      ],
      "metadata": {
        "id": "ZR2dkscZ7h0b"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# 큐(Queue)\n",
        "- 앞에서 넣고 뒤에서 빼고 : 넣은 대로 빠짐\n",
        "- FIFO : First In, First Out\n",
        "- 관을 통과한다고 생각하자.\n",
        "- 너비우선, 깊이우선탐색에서 응용됨"
      ],
      "metadata": {
        "id": "6zj8KgJ3Ktpv"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class Queue:\n",
        "\n",
        "    def __init__(self):\n",
        "        print(\"Queue 생썽 !\")\n",
        "        self.L = []\n",
        "\n",
        "    def push(self, data):\n",
        "        self.L.append(data)\n",
        "\n",
        "    def pop(self):\n",
        "        return self.L.pop(0)"
      ],
      "metadata": {
        "id": "h_HBw8o_7hrV"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "q = Queue()\n",
        "\n",
        "q.push(1)\n",
        "q.push(2)\n",
        "q.push(3)\n",
        "q.pop()\n",
        "q.pop()"
      ],
      "metadata": {
        "id": "feM4w19_FFDA",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ca211962-5774-47ae-99ad-36c3d964cc29"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Queue 생썽 !\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2"
            ]
          },
          "metadata": {},
          "execution_count": 9
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## 백준 식당 입구 대기 줄 문제\n",
        "- 문제링크 : https://www.acmicpc.net/problem/26042\n",
        "\n",
        "학생이 학교 식당에 도착하고 식사가 준비되는 n개의 정보가 저장된 A가 주어진다. A에 저장된 첫 번째 정보부터 n번째 정보까지 순서대로 처리한 다음, 식당 입구에 줄을 서서 대기하는 학생 수가 최대가 되었던 순간의 학생 수와 이때 식당 입구의 맨 뒤에 대기 중인 학생의 번호를 출력하자.\n",
        "\n",
        "대기하는 학생 수가 최대인 경우가 여러 번이라면 맨 뒤에 줄 서 있는 학생의 번호가 가장 작은 경우를 출력하자.\n",
        "\n",
        "A에 저장된 n개의 정보는 아래 두 가지 유형으로 구분된다. 첫 번째가 유형 1, 두 번째가 유형 2이다.\n",
        "\n",
        "- 1 a: 학생 번호가 양의 정수 a인 학생 1명이 학교 식당에 도착하여 식당 입구의 맨 뒤에 줄을 서기 시작한다.\n",
        "- 2: 식사 1인분이 준비되어 식당 입구의 맨 앞에서 대기 중인 학생 1명이 식사를 시작한다.\n",
        "식사 1인분이 준비될 때는 식당 입구에서 대기 중인 학생이 항상 존재한다. 식당 입구에 줄을 서서 대기하였으나 식사가 준비 안 된 학생은 식사를 못 한다."
      ],
      "metadata": {
        "id": "jJgXk9qTXS78"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "A = []\n",
        "n = int(input())\n",
        "max = [0, 0]\n",
        "\n",
        "for _ in range(n):\n",
        "    cmd = input().split()\n",
        "    if cmd[0] == '1':\n",
        "        A.append(int(cmd[1]))\n",
        "    elif cmd[0] == '2':\n",
        "        A.pop(0)\n",
        "\n",
        "    if max[0] < len(A):\n",
        "        max[0] = len(A)\n",
        "        max[1] = A[-1]\n",
        "    elif max[0] == len(A):\n",
        "        max[1] = min(max[1], A[-1])\n",
        "\n",
        "print(max[0], max[1])"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "a59dhjaQXScf",
        "outputId": "83645527-3269-4540-c616-dafa4b9f42b4"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5\n",
            "1 2\n",
            "1 1\n",
            "2\n",
            "1 3\n",
            "2\n",
            "2 1\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# 데크(Deque, Double Ended Queue)\n",
        "- 양 끝에서 모두 삽입과 삭제가 가능한 큐\n",
        "- 덱은 스택 + 큐 연산\n",
        "    - ADT는 스택과 큐에 구현되어 있는 것과 유사하게 구현\n",
        "- collections 라는 모듈에 deque라는 클래스로 이미 구현되어 있음.\n",
        "- 양방향 연결리스트로 구성\n",
        "- 단순히 값을 삽입/삭제시에는 O(1)만큼의 시간밖에 할애되지 않기 때문에 아주 효율적임\n",
        "\n",
        "- 프로그래머스 풀다가 데크 공부했던 설명\n",
        "https://jounkim.tistory.com/24"
      ],
      "metadata": {
        "id": "VRLHzF81Kw89"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from collections import deque\n",
        "\n",
        "d = deque()\n",
        "print(type(d))\n",
        "\n",
        "# append(x) : 오른쪽에 (x) 삽입\n",
        "# O(1)\n",
        "for i in range(10):\n",
        "    d.append(i)\n",
        "print(d)\n",
        "\n",
        "# appendleft(x) : 왼쪽에 x 삽입\n",
        "# O(1)\n",
        "d.appendleft(100)\n",
        "print(d)\n",
        "\n",
        "# insert(idx, x) : idx 위치에 x 삽입\n",
        "# 삽입으로 인해 제한된 길이의 데크가 maxlen 이상으로 커지면, IndexError 발생\n",
        "# O(N)\n",
        "d.insert(5, 123)\n",
        "print(d)\n",
        "\n",
        "# extendleft / extend\n",
        "# 왼쪽/오른쪽에 iterable한 객체를 통째로 append 하여 연장시키는 연산\n",
        "# O(K)\n",
        "d.extend([-1,-2,-3])\n",
        "print(d)\n",
        "d.extendleft([-100,-200,-300])\n",
        "print(d)\n",
        "\n",
        "# pop() : 스택처럼 오른(위)쪽에서 하나씩 삭제, 삭제한 것은 반환됌\n",
        "# O(1)\n",
        "for i in range(3):\n",
        "    r = d.pop()\n",
        "    print(r)\n",
        "print(d)\n",
        "\n",
        "# popleft() : 큐처럼 왼(아래)쪽에서 하나씩 삭제, return\n",
        "# O(1)\n",
        "for i in range(3):\n",
        "    r = d.popleft()\n",
        "    print(r)\n",
        "print(d)\n",
        "\n",
        "# index(x, start, stop)\n",
        "# O(N)\n",
        "print(d.index(4,0,10)) # 인덱스 0-10 사이에 4를 찾아라\n",
        "\n",
        "# count(x) : x의 개수 세기, return x\n",
        "# O(N)\n",
        "print(d.count(100)) # 100의 개수\n",
        "\n",
        "# rotate(n=1)\n",
        "# n이 음수이면 왼쪽으로 회전\n",
        "# O(K)\n",
        "d.rotate(2) # 오른쪽으로 2번 회전\n",
        "print(d)\n",
        "\n",
        "# 리스트로 변환 가능\n",
        "print(list(d))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lrsn4ZDZLiWx",
        "outputId": "f3a7ad27-09fa-480b-9fe2-7725efebaded"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "<class 'collections.deque'>\n",
            "deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])\n",
            "deque([100, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9])\n",
            "deque([100, 0, 1, 2, 3, 123, 4, 5, 6, 7, 8, 9])\n",
            "deque([100, 0, 1, 2, 3, 123, 4, 5, 6, 7, 8, 9, -1, -2, -3])\n",
            "deque([-300, -200, -100, 100, 0, 1, 2, 3, 123, 4, 5, 6, 7, 8, 9, -1, -2, -3])\n",
            "-3\n",
            "-2\n",
            "-1\n",
            "deque([-300, -200, -100, 100, 0, 1, 2, 3, 123, 4, 5, 6, 7, 8, 9])\n",
            "-300\n",
            "-200\n",
            "-100\n",
            "deque([100, 0, 1, 2, 3, 123, 4, 5, 6, 7, 8, 9])\n",
            "6\n",
            "1\n",
            "deque([8, 9, 100, 0, 1, 2, 3, 123, 4, 5, 6, 7])\n",
            "[8, 9, 100, 0, 1, 2, 3, 123, 4, 5, 6, 7]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## 백준 데크 문제\n",
        "- 문제링크 : (https://www.acmicpc.net/problem/10866)\n",
        "\n",
        "정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.\n",
        "\n",
        "명령은 총 여덟 가지이다.\n",
        "\n",
        "- push_front X: 정수 X를 덱의 앞에 넣는다.\n",
        "- push_back X: 정수 X를 덱의 뒤에 넣는다.\n",
        "- pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.\n",
        "- pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.\n",
        "- size: 덱에 들어있는 정수의 개수를 출력한다.\n",
        "- empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.\n",
        "- front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.\n",
        "- back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다."
      ],
      "metadata": {
        "id": "oD9lHEWKS-m0"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# 단방향 링크드리스트로 구현\n",
        "# 양방향 링크드리스트(더블링크드리스트)로 구현하는 게 더 나을듯\n",
        "\n",
        "import sys\n",
        "input = sys.stdin.readline\n",
        "\n",
        "class Node:\n",
        "    def __init__(self, data):\n",
        "        self.data = data\n",
        "        self.next = None\n",
        "\n",
        "class Deque:\n",
        "    def __init__(self):\n",
        "        init = Node('init')\n",
        "        self.head = init\n",
        "        self.tail = init\n",
        "\n",
        "        self.현재노드 = None\n",
        "        self.데이터수 = 0\n",
        "\n",
        "    def push_front(self, data):\n",
        "        새로운노드 = Node(data)\n",
        "        새로운노드.next = self.head\n",
        "        self.head = 새로운노드\n",
        "        self.데이터수 += 1\n",
        "        if self.데이터수 == 1:\n",
        "            self.tail = 새로운노드\n",
        "\n",
        "    def push_back(self, data):\n",
        "        새로운노드 = Node(data)\n",
        "        self.tail.next = 새로운노드\n",
        "        self.tail = 새로운노드\n",
        "        self.데이터수 += 1\n",
        "        if self.데이터수 == 1:\n",
        "            self.head = 새로운노드\n",
        "\n",
        "    def pop_front(self):\n",
        "        if self.데이터수 == 0:\n",
        "            return -1\n",
        "        data = self.head.data\n",
        "        self.head = self.head.next\n",
        "        self.데이터수 -= 1\n",
        "        return data\n",
        "\n",
        "    def pop_back(self):\n",
        "        if self.데이터수 == 0:\n",
        "            return -1\n",
        "\n",
        "        data = self.tail.data\n",
        "        현재노드 = self.head\n",
        "\n",
        "        for i in range(self.데이터수):\n",
        "            if 현재노드.next is self.tail:\n",
        "                self.tail = 현재노드\n",
        "                break\n",
        "            현재노드 = 현재노드.next\n",
        "\n",
        "        self.데이터수 -= 1\n",
        "        return data\n",
        "\n",
        "    def size(self):\n",
        "        return self.데이터수\n",
        "\n",
        "    def empty(self):\n",
        "        return 1 if self.데이터수 == 0 else 0\n",
        "\n",
        "    def front(self):\n",
        "        if self.데이터수 == 0:\n",
        "            return -1\n",
        "        return self.head.data\n",
        "\n",
        "    def back(self):\n",
        "        if self.데이터수 == 0:\n",
        "            return -1\n",
        "        return self.tail.data"
      ],
      "metadata": {
        "id": "pN_lt-rCS5T5"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "n = int(input())\n",
        "d = Deque()\n",
        "\n",
        "for _ in range(n):\n",
        "    cmd = input().split()\n",
        "    if cmd[0] == 'push_back':\n",
        "        d.push_back(int(cmd[1]))\n",
        "    elif cmd[0] == 'push_front':\n",
        "        d.push_front(int(cmd[1]))\n",
        "    elif cmd[0] == 'pop_front':\n",
        "        print(d.pop_front())\n",
        "    elif cmd[0] == 'pop_back':\n",
        "        print(d.pop_back())\n",
        "    elif cmd[0] == 'size':\n",
        "        print(d.size())\n",
        "    elif cmd[0] == 'empty':\n",
        "        print(d.empty())\n",
        "    elif cmd[0] == 'front':\n",
        "        print(d.front())\n",
        "    elif cmd[0] == 'back':\n",
        "        print(d.back())\n",
        "    else:\n",
        "        print(\"unacceptable op\")\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "mUvvl-2CZj2Q",
        "outputId": "71ec5675-4314-43c4-8466-b02c53e3b79c"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5\n",
            "push_front 1\n",
            "push_front 3\n",
            "pop_front\n",
            "3\n",
            "pop_back\n",
            "1\n",
            "empty\n",
            "1\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# 라이브러리 사용해서 구현하기\n",
        "from collections import deque\n",
        "\n",
        "n = int(input())\n",
        "d = deque()\n",
        "\n",
        "for _ in range(n):\n",
        "    cmd = input().split()\n",
        "    if cmd[0] == 'push_front':\n",
        "        d.appendleft(int(cmd[1]))\n",
        "    elif cmd[0] == 'push_back':\n",
        "        d.append(int(cmd[1]))\n",
        "    elif cmd[0] == 'pop_front':\n",
        "        print(d.popleft()) if d else print(-1)\n",
        "    elif cmd[0] == 'pop_back':\n",
        "        print(d.pop()) if d else print(-1)\n",
        "    elif cmd[0] == 'size':\n",
        "        print(len(d))\n",
        "    elif cmd[0] == 'empty':\n",
        "        print(0) if d else print(1)\n",
        "    elif cmd[0] == 'front':\n",
        "        print(d[0]) if d else print(-1)\n",
        "    elif cmd[0] == 'back':\n",
        "        print(d[-1]) if d else print(-1)\n",
        "    else:\n",
        "        print(\"unacceptable op\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "JHCcfqfmi-gF",
        "outputId": "8fcae538-5ef7-4e39-c350-defae95d0fe6"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "22\n",
            "front\n",
            "-1\n",
            "back\n",
            "-1\n",
            "pop_front\n",
            "-1\n",
            "pop_back\n",
            "-1\n",
            "push_front 1\n",
            "front\n",
            "1\n",
            "pop_back\n",
            "1\n",
            "push_back 2\n",
            "back\n",
            "2\n",
            "pop_front\n",
            "2\n",
            "push_front 10\n",
            "push_front 333\n",
            "front\n",
            "333\n",
            "back\n",
            "10\n",
            "pop_back\n",
            "10\n",
            "pop_back\n",
            "333\n",
            "push_back 20\n",
            "push_back 1234\n",
            "front\n",
            "20\n",
            "back\n",
            "1234\n",
            "pop_back\n",
            "1234\n",
            "pop_back\n",
            "20\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "- 확실히 클래스로 구현한 게 빠름 (56ms vs. 72ms)\n",
        "- 메모리는 비슷"
      ],
      "metadata": {
        "id": "hrHqgb8QlLdt"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 백준문제12789번 : 도키도키 간식드리미\n",
        "- 문제링크 : https://www.acmicpc.net/problem/12789"
      ],
      "metadata": {
        "id": "kODVkK1_8c5r"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from collections import deque\n",
        "\n",
        "n = int(input())\n",
        "que = deque(map(int, input().split()))\n",
        "stack = deque()\n",
        "ord = 1\n",
        "\n",
        "while que:\n",
        "    if que[0] != ord:\n",
        "        stack.append(que.popleft())\n",
        "\n",
        "    else:\n",
        "        que.popleft()\n",
        "        ord += 1\n",
        "\n",
        "    while stack and stack[-1] == ord:\n",
        "        stack.pop()\n",
        "        ord += 1\n",
        "\n",
        "print(\"Nice\" if not stack else \"Sad\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8gKX-gSa8nCA",
        "outputId": "7474b812-205f-4433-cc3c-20c1a8c644e2"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5\n",
            "5 4 1 3 2\n",
            "Nice\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# 해시테이블"
      ],
      "metadata": {
        "id": "KvvQcqERLqNx"
      }
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "jxa_K8jmLrKM"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# 셋"
      ],
      "metadata": {
        "id": "jO6wg7RBLrls"
      }
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "wTosANusLsfi"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# 알고리즘\n",
        "- 재귀, 재귀적으로 생각하기, 하노이탑\n",
        "- 정렬(버블, 선택, 삽입, 병합, 퀵)\n",
        "- 동적프로그래밍(메모이제이션, 타뷸레이션)"
      ],
      "metadata": {
        "id": "UT3s6A5sLtKX"
      }
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "CKzoZINjL9X8"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}