{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 리스트, 딕셔너리"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 리스트\n",
    "\n",
    "리스트 : 입력순서가 유지되며, 내부적으로 동적 배열로 구현되어 있는 순서대로 저장하는 시퀀스이자 변경가능한 목록\n",
    "\n",
    "파이썬 : list()  \n",
    "C++ : std::vector  \n",
    "자바 : ArrayList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- len(a) : O(1)\n",
    "- a[i] : O(1)\n",
    "- a[i:j]: O(k)\n",
    "- elem in a : : O(n)\n",
    "- a.count(elem) : O(n)\n",
    "- a.index(elem) : O(n)\n",
    "- a.append(elem): O(1)\n",
    "- a.pop() : O(1)\n",
    "- a.pop(0) : O(n) -> deque 권장\n",
    "- del a[i] : O(n)\n",
    "- a.sort() : O(nlogn) -> Timsort\n",
    "- min(a), max(a) : O(n)\n",
    "- a.reverse() : : O(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 딕셔너리"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "파이썬 3.7+ 에서는 입력 순서가 유지되며 내부적으로는 해시 테이블로 구현되어 있다.\n",
    "\n",
    "파이썬 : dict()  \n",
    "C++ : std::unordered_map  \n",
    "자바 : HashMap  \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- len(a) : O(1)\n",
    "- a[key] : O(1)\n",
    "- a[key] = value : O(1)\n",
    "- key in a : O(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "파이썬 3.7+: 딕셔너리 입력 순서 유지\n",
    "파이썬 3.6+: 딕셔너리 메모리 사용량 20% 감소\n",
    "\n",
    "3.6이하에서는 입력 순서가 유지되는 collection.OrderDict()을 사용한다.\n",
    "\n",
    "요소의 값을 키로 하고 개수를 값 형태로 만들어 카운팅하는 collections.Counter() 등이 있다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### defaultdict \n",
    "존재하지 않는 키를 조회할 경우, 에러 메시지를 출력하는 대신 디폴트 값을 기준으로 해당 키에 대한 딕셔너리 아이템을 생성해준다.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import collections\n",
    "\n",
    "a = collections.defaultdict(int)\n",
    "a['B']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Counter\n",
    "아이템에 대한 개수를 계산해 딕셔너리로 리턴하며, 다음과 같이 사용한다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [1, 2, 3, 3, 4, 4, 4, 4, 5, 6, 6]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "b= collections.Counter(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({1: 1, 2: 1, 3: 2, 4: 4, 5: 1, 6: 2})"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(4, 4), (3, 2)]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b.most_common(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### OrderedDict\n",
    "3.6 이하에서 사용하는 순서가 유지되는 딕셔너리"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "OrderedDict([('banana', 3), ('pear', 4), ('apple', 1), ('orange', 4)])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "collections.OrderedDict({'banana': 3, 'pear': 4, 'apple': 1, 'orange':4})"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}