이코테 - 알고리즘 이론 1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 그리디\n",
    "\n",
    "- 구현\n",
    "\n",
    "- DFS / BFS\n",
    "\n",
    "- 정렬"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 8 3\n",
      "2 4 5 4 6\n",
      "46\n"
     ]
    }
   ],
   "source": [
    "# 그리디 알고리즘 - 큰 수의 법칙\n",
    "\n",
    "n, m, k = map(int, input().split())\n",
    "num = list(map(int, input().split()))\n",
    "\n",
    "num.sort()\n",
    "sup = num[-1]\n",
    "sub = num[-2]\n",
    "\n",
    "syn = 0\n",
    "while True:\n",
    "    \n",
    "    for i in range(k):\n",
    "        if m == 0:\n",
    "            break\n",
    "        m -= 1\n",
    "        syn += sup\n",
    "    \n",
    "    if m == 0:\n",
    "        break\n",
    "    m -= 1\n",
    "    syn += sub\n",
    "\n",
    "print(syn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1260\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "# 예제 3-1 \n",
    "\n",
    "n = int(input())\n",
    "coin = [500, 100, 50, 10]\n",
    "count = 0\n",
    "\n",
    "for i in coin:\n",
    "    count += n//i\n",
    "    n = n % i\n",
    "\n",
    "print(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 4\n",
      "7 3 1 8\n",
      "3 3 3 4\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# 그리디 알고리즘 - 숫자 카드 게임\n",
    "\n",
    "n, m = map(int, input().split())\n",
    "card = []\n",
    "\n",
    "for i in range(n):\n",
    "    row = list(map(int, input().split()))\n",
    "    card.append(row)\n",
    "\n",
    "great_num = 0\n",
    "for i in card:\n",
    "    if min(i) > great_num:\n",
    "        great_num = min(i)\n",
    "\n",
    "print(great_num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[4, 1, 4], [2, 2, 2], [3, 1, 2]]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 그리디 알고리즘 - 숫자 카드 게임 답안 예시\n",
    "\n",
    "n, m = map(int, input().split())\n",
    "\n",
    "result = 0\n",
    "for i in range(n):\n",
    "    data = list(map(int, input().split()))\n",
    "    min_value = min(data)\n",
    "    result = max(result, min_value)\n",
    "    \n",
    "print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "25 3\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "# 그리디 알고리즘 - 1이 될 때까지\n",
    "\n",
    "n, k = map(int, input().split())\n",
    "\n",
    "count = 0\n",
    "while True:\n",
    "    if n == 1:\n",
    "        break\n",
    "    elif n % k == 0:\n",
    "        n = n / k\n",
    "        count += 1\n",
    "    else:\n",
    "        n -= 1\n",
    "        count += 1\n",
    "\n",
    "print(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "R R R U D D\n",
      "3 4\n"
     ]
    }
   ],
   "source": [
    "# 예제 4-1\n",
    "\n",
    "n = int(input())\n",
    "iti = list(input().split())\n",
    "\n",
    "x, y = 1, 1\n",
    "drt = ['L', 'R', 'U', 'D']\n",
    "\n",
    "for i in iti:\n",
    "    for j in drt:\n",
    "        if i == j:\n",
    "            if i == 'L':\n",
    "                ex = x\n",
    "                ey = y - 1\n",
    "            elif i == 'R':\n",
    "                ex = x\n",
    "                ey = y + 1\n",
    "            elif i == 'U':\n",
    "                ex = x - 1\n",
    "                ey = y\n",
    "            elif i == 'D':\n",
    "                ex = x + 1\n",
    "                ey = y\n",
    "\n",
    "    if ey < 1 or ey > n or ex < 1 or ex > n:\n",
    "        continue\n",
    "    x, y = ex, ey\n",
    "    \n",
    "print(x, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "11475\n"
     ]
    }
   ],
   "source": [
    "# 구현 -  시각\n",
    "\n",
    "n = int(input())\n",
    "cnt = 0\n",
    "for i in range(n + 1):\n",
    "    for j in range(60):\n",
    "        for k in range(60):\n",
    "            num = str(i) + str(j) + str(k)\n",
    "            if num.count('3') > 0:\n",
    "                cnt += 1\n",
    "        \n",
    "print(cnt)\n",
    "# if '3' in str(i) + str(j) + str(k):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1575"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 구현 - 왕실의 나이트\n",
    "\n",
    "coor = input()\n",
    "row = coor[1]\n",
    "col = coor[0]\n",
    "col_ls = [a, b, c, d, e, f, g, h]\n",
    "count = 0\n",
    "\n",
    "for i in col:\n",
    "    for j in range(1, 9):\n",
    "        if coor == str(i) + str(j):\n",
    "            lct = \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 4\n",
      "1 1 0\n",
      "1 1 1 1\n",
      "1 0 0 1\n",
      "1 1 0 1\n",
      "1 1 1 1\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "# 구현 - 게임 개발\n",
    "\n",
    "n, m = map(int, input().split())\n",
    "a, b, d = map(int, input().split())\n",
    "khan = []\n",
    "for i in range(n):\n",
    "    khan.append(list(map(int, input().split())))\n",
    "    \n",
    "f_print = [[0]*m for i in range(n)]\n",
    "f_print[a][b] = 1\n",
    "\n",
    "direction = [0, 1, 2, 3]\n",
    "x_ls = [-1, 0, 1, 0] # 북 동 남 서\n",
    "y_ls = [0, 1, 0, -1]\n",
    "\n",
    "count = 1\n",
    "turn_times = 0\n",
    "while True:\n",
    "    d = direction[d-1]\n",
    "    ex = a + x_ls[d]\n",
    "    ey = b + y_ls[d]\n",
    "    \n",
    "    if f_print[ex][ey] == 0 and khan[ex][ey] == 0:\n",
    "        a = ex\n",
    "        b = ey\n",
    "        f_print[ex][ey] = 1\n",
    "        count += 1\n",
    "        turn_times = 0\n",
    "        continue\n",
    "        \n",
    "    else:\n",
    "        turn_times += 1\n",
    "    \n",
    "    if turn_times == 4:\n",
    "        ex = a - x_ls[d]\n",
    "        ey = b - y_ls[d]\n",
    "        \n",
    "        if khan[ex][ey] == 0:\n",
    "            a = ex\n",
    "            b = ey\n",
    "            \n",
    "        else:\n",
    "            break\n",
    "        \n",
    "        turn_times = 0\n",
    "        \n",
    "print(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# DFS 예제 따라쓰기\n",
    "\n",
    "def dfs(graph, v, visited):\n",
    "    visited[v] = True\n",
    "    print(v, end = ' ')\n",
    "    for i in graph[v]:\n",
    "        if not visited[i]:\n",
    "            dfs(graph, i, visited)\n",
    "\n",
    "graph = [\n",
    "    [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]\n",
    "]\n",
    "\n",
    "visited = [False]*9\n",
    "\n",
    "dfs(graph, 1, visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# BFS 예제 따라쓰기\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "def bfs(graph, start, visited):\n",
    "    queue = deque([start])\n",
    "    visited[start] = True\n",
    "    while queue:\n",
    "        v = queue.popleft()\n",
    "        print(v, end = ' ')\n",
    "        for i in graph[v]:\n",
    "            if not visited[i]:\n",
    "                queue.append(i)\n",
    "                visited[i] = True\n",
    "\n",
    "graph = [\n",
    "    [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]\n",
    "]\n",
    "\n",
    "visited = [False]*9\n",
    "\n",
    "dfs(graph, 1, visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 3\n",
      "001\n",
      "010\n",
      "101\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# DFS/BFS - 음료수 얼려 먹기\n",
    "# 깊이우선탐색이다\n",
    "\n",
    "n, m = map(int, input().split())\n",
    "frame = []\n",
    "count = 0\n",
    "for i in range(n):\n",
    "    frame.append(list(map(int, input())))\n",
    "\n",
    "def um(a, b):\n",
    "    if a < 0 or a >= n or b < 0 or b >= m:\n",
    "        return False\n",
    "    \n",
    "    elif frame[a][b] == 0:\n",
    "        frame[a][b] = 1\n",
    "        \n",
    "        um(a+1, b)\n",
    "        um(a-1, b)\n",
    "        um(a, b+1)\n",
    "        um(a, b-1)\n",
    "        \n",
    "        return True\n",
    "    \n",
    "    return False\n",
    "\n",
    "for i in range(n):\n",
    "    for j in range(m):\n",
    "        if um(i, j) == True:\n",
    "            count += 1\n",
    "            \n",
    "print(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# DFS/BFS - 미로 탈출\n",
    "# 큐가 빌 때까지 반복하는데, 네 방향으로 위치 확인을 하면서 특정 노드를 처음 방문할 때만 최단거리를 기록한다.\n",
    "# 최단거리 기록은 이전 방문 노드값에 1을 더하는 방식으로 한다. 그러니까 방문한 노드 숫자가 1이면 처음 방문하는 노드인 거지.\n",
    "# 다매함\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "n, m = map(int, input().split())\n",
    "maze = []\n",
    "for i in range(n):\n",
    "    maze.append(list(map(int, input())))\n",
    "\n",
    "dx = [-1, 1, 0, 0]\n",
    "dy = [0, 0, -1, 1]\n",
    "\n",
    "def run(a, b):\n",
    "    queue = deque()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 정렬! 선택 정렬 예시 코드\n",
    "# 가장 작은 수를 찾는다.\n",
    "def selection_sort(arr):\n",
    "    for i in range(len(arr)):\n",
    "        min_idx = i\n",
    "        for j in range(i+1, len(arr)):\n",
    "            if arr[min_idx] > arr[j]:\n",
    "                min_idx = j\n",
    "        arr[i], arr[min_idx] = arr[min_idx], arr[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 삽입 정렬 예시 코드\n",
    "\n",
    "def insert_sort(arr):\n",
    "    for i in range(1, len(arr)):\n",
    "        for j in range(i, 0, -1):\n",
    "            if arr[j] < arr[j-1]:\n",
    "                arr[j], arr[j-1] = arr[j-1], arr[j]\n",
    "            else:\n",
    "                break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 퀵 정렬 예시 코드\n",
    "\n",
    "def quick_sort(arr, start, end):\n",
    "    if start >= end:\n",
    "        return\n",
    "    \n",
    "    pivot = start # 0\n",
    "    left = start + 1 # 1\n",
    "    right = end\n",
    "    \n",
    "    while left <= right:\n",
    "        \n",
    "        while left <= end and arr[left] <= arr[pivot]:\n",
    "            left += 1\n",
    "        \n",
    "        while right > start and arr[right] >= arr[pivot]:\n",
    "            right -= 1\n",
    "        \n",
    "        if left > right:\n",
    "            arr[right], arr[pivot] = arr[pivot], arr[right]\n",
    "        \n",
    "        else:\n",
    "            arr[left], arr[right] = arr[right], arr[left]\n",
    "            \n",
    "    quick_sort(arr, start, right - 1)\n",
    "    quick_sort(arr, right + 1, end)\n",
    "    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 계수 정렬 예시 코드\n",
    "\n",
    "def counting_sort(arr):\n",
    "    count = [0] * (max(arr) + 1)\n",
    "    \n",
    "    for i in range(len(arr)):\n",
    "        count[arr[i]] += 1\n",
    "        \n",
    "    for i in range(len(count)):\n",
    "        for j in range(count[i]):\n",
    "            print(i, end = ' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "15\n",
      "27\n",
      "12\n",
      "27 15 12\n"
     ]
    }
   ],
   "source": [
    "# 정렬 - 위에서 아래로\n",
    "\n",
    "n = int(input())\n",
    "sequence = []\n",
    "for i in range(n):\n",
    "    sequence.append(int(input()))\n",
    "sequence = sorted(sequence, reverse = True)\n",
    "\n",
    "print(*sequence)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "홍길동 95\n",
      "김첨지 90\n",
      "김첨지 홍길동 "
     ]
    }
   ],
   "source": [
    "# 정렬 - 성적이 낮은 순서로 학생 출력하기\n",
    "\n",
    "n = int(input())\n",
    "ls = []\n",
    "for i in range(n):\n",
    "    a, b = map(str, input().split())\n",
    "    b = int(b)\n",
    "    ls.append(tuple([a, b]))\n",
    "\n",
    "ls = sorted(ls, key = lambda x : x[0])\n",
    "\n",
    "for i in ls:\n",
    "    print(i[0], end = ' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 3\n",
      "1 2 5 4 3\n",
      "5 5 6 6 5\n",
      "26\n"
     ]
    }
   ],
   "source": [
    "# 정렬 - 두 배열의 원소 교체\n",
    "\n",
    "n, k = map(int, input().split())\n",
    "a = list(map(int, input().split()))\n",
    "b = list(map(int, input().split()))\n",
    "\n",
    "a.sort()\n",
    "b.sort(reverse = True)\n",
    "\n",
    "for i in range(k):\n",
    "    if a[i] < b[i]:\n",
    "        a[i], b[i] = b[i], a[i]\n",
    "\n",
    "print(sum(a))\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.7.5 64-bit ('Namlister': virtualenv)",
   "language": "python",
   "name": "python37564bitnamlistervirtualenv5d7bb17d3c984c36aee202a2f6a91336"
  },
  "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.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}