{"@attributes":{"version":"2.0"},"channel":{"title":"dev_record","link":"https:\/\/bird-j.tistory.com\/","description":"\uadf8\ub0e5 \uac1c\ubc1c\uc774 \uc990\uac70\uc6b4 \uc0ac\ub78c","language":"ko","pubDate":"Wed, 6 May 2026 23:56:29 +0900","generator":"TISTORY","ttl":"100","managingEditor":"hojoo","image":{"title":"dev_record","url":"https:\/\/tistory1.daumcdn.net\/tistory\/6247368\/attach\/0c479ce31ee34b5791f793118575f24e","link":"https:\/\/bird-j.tistory.com"},"item":[{"title":"\ud504\ub85c\uadf8\ub798\uba38\uc2a4 - \ub514\uc2a4\ud06c \ucee8\ud2b8\ub864\ub7ec","link":"https:\/\/bird-j.tistory.com\/105","description":"

\ubb38\uc81c \uc124\uba85<\/b><\/h2>\n

\n
<\/span><\/span><\/div>\n<\/figure>\n
<\/span><\/figure>\n<\/p>\n

\uc81c\ud55c\uc0ac\ud56d \ubc0f \uc785\ucd9c\ub825<\/b><\/h2>\n

<\/span><\/figure>\n<\/p>\n

\ud480\uc774<\/b><\/h2>\n

\ubb38\uc81c \uc124\uba85\uc5d0\uc11c \ubcfc \uc218 \uc788\ub4ef\uc774 \uac01 \uc791\uc5c5\uc5d0 \uc6b0\uc120\uc21c\uc704\uac00 \uc8fc\uc5b4\uc9c0\uace0 \uc774 \uc6b0\uc120\uc21c\uc704(\uc18c\uc694\uc2dc\uac04, \uc694\uccad \uc2dc\uac01)\ub97c \uae30\ubc18\uc73c\ub85c \uc791\uc5c5\uc744 \ucc98\ub9ac\ud574\uc57c\ud55c\ub2e4. \uc791\uc5c5 \ud050\uc5d0\uc11c \ub9e4\ubc88 \uac00\uc7a5 \uc791\uc740 \uc6b0\uc120\uc21c\uc704\ub97c \uc21c\ud68c\ud558\uba70 \ucc3e\uc744 \uc21c \uc5c6\uc73c\ub2c8 \ud799(heap)\uc744 \uc0ac\uc6a9\ud558\uc5ec \uac00\uc7a5 \uc791\uc740 \uc6b0\uc120\uc21c\uc704\ub97c \ube60\ub974\uac8c \ucc3e\uc744 \uc218 \uc788\ub3c4\ub85d \ud574\uc8fc\uc5c8\ub2e4. \ub610\ud55c \uc18c\uc694\uc2dc\uac04\uacfc \uc694\uccad \uc2dc\uac01\uc774 \uac19\ub2e4\uba74 \uc791\uc5c5\uc758 \ubc88\ud638\uac00 \uc791\uc740 \uac83\uc744 \uc6b0\uc120\uc21c\uc704\ub85c \ubcf8\ub2e4\uace0 \ud588\ub294\ub370, \uc0ac\uc2e4 \uc18c\uc694\uc2dc\uac04\uacfc \uc694\uccad \uc2dc\uac01\uc774 \uac19\ub2e4\uba74 \ubb34\uc5c7\uc744 \uba3c\uc800 \ucc98\ub9ac\ud558\ub4e0 \uad6c\ud558\ub824\ub294 \uc815\ub2f5\uc5d0\ub294 \ucc28\uc774\uac00 \uc5c6\uae30 \ub54c\ubb38\uc5d0 \uc81c\uc678\ud558\uace0 2\uac00\uc9c0\ub9cc \uace0\ub824\ud574\uc8fc\uc5c8\ub2e4.<\/p>\n

\ub0b4 \ucf54\ub4dc<\/b><\/h2>\n
from heapq import heappush, heappop\nfrom collections import deque\n\ndef solution(jobs):\n    # \uc694\uccad \uc2dc\uac01 \uae30\uc900\uc73c\ub85c \uc815\ub82c\n    jobs.sort()\n    jobs = deque(jobs)\n\n    time = 0        # \ud604\uc7ac \uc2dc\uac01\n    heap = []       # \ub300\uae30 \ud050\n    total_time = 0  # \uc804\uc81c \uc791\uc5c5\uc758 \uc18c\uc694 \uc2dc\uac04\n    job_length = len(jobs)\n    idx = 0\n    while idx < job_length:\n        # \ud604\uc7ac \uc2dc\uac01\uae4c\uc9c0 \ub3c4\ucc29\ud55c \uc791\uc5c5\ub4e4\uc744 \ud799\uc5d0 \ub123\uae30\n        while jobs and jobs[0][0] <= time:\n            request, duration = jobs.popleft()\n            heappush(heap, (duration, request))\n\n        # \ub300\uae30 \ud050\uac00 \uc788\ub2e4\uba74\n        if heap:\n            duration, request = heappop(heap)\n            time += duration\n            total_time += time - request\n            # \uc2e4\uc81c\ub85c \uc791\uc5c5\uc774 \ucc98\ub9ac\ub420 \ub54c\ub9cc \uc99d\uac00\n            idx += 1\n        else:\n            # \ub300\uae30 \ud050\uac00 \ube44\uc5b4\uc788\uc73c\uba74 \ub2e4\uc74c \uc791\uc5c5\uc758 \uc694\uccad \uc2dc\uac01\uc73c\ub85c \uc774\ub3d9\n            if jobs:\n                time = jobs[0][0]\n\n    return total_time \/\/ job_length<\/code><\/pre>\n
\uc8fc\uc5b4\uc9c4 \uc791\uc5c5 \ud050\uc5d0\uc11c \ud604\uc7ac \uc2dc\uac04\ubcf4\ub2e4 \uc791\uc740 \uc2dc\uac04\uc758 \uc791\uc5c5\ub4e4\uc744 \ubaa8\ub450 \ud799\uc5d0 \ub123\uace0 \ud799\uc774 \ube44\uc5b4\uc788\uc9c0 \uc54a\ub2e4\uba74 \ud558\ub098\uc529 \uaebc\ub0b4\uc11c \uc791\uc5c5\uc744 \ucc98\ub9ac\ud574\uc8fc\uc5c8\ub2e4.<\/p>\n
 <\/p>\n
\uc2dc\uac04 \ubcf5\uc7a1\ub3c4: O(n logN)<\/b><\/p>\n
-> \ud799 \uc5f0\uc0b0\uc774 log n\uc774\uace0 \ucd1d n\ubc88 \ubc18\ubcf5<\/b><\/b><\/p>","category":["Computer Science\/Problem Solving","\ub514\uc2a4\ud06c \ucee8\ud2b8\ub864\ub7ec","\ud504\ub85c\uadf8\ub798\uba38\uc2a4"],"author":"hojoo","guid":"https:\/\/bird-j.tistory.com\/105","comments":"https:\/\/bird-j.tistory.com\/105#entry105comment","pubDate":"Thu, 20 Nov 2025 00:35:46 +0900"},{"title":"\ud504\ub85c\uadf8\ub798\uba38\uc2a4 - [1\ucc28] \uce90\uc2dc (2018 KAKAO BLIND)","link":"https:\/\/bird-j.tistory.com\/104","description":"
\ubb38\uc81c \uc124\uba85<\/b><\/h2>\n
<\/span><\/figure>\n<\/p>\n
\uc81c\ud55c\uc0ac\ud56d \ubc0f \uc785\ucd9c\ub825<\/b><\/h2>\n
<\/span><\/figure>\n
<\/span><\/figure>\n<\/p>\n
\ud480\uc774<\/b><\/h2>\n
\uc0ac\uc2e4 LRU\ub97c LFU\ub85c \ucc29\uac01\ud558\uace0 \ud480\uc774\ud558\ub2e4\uac00 \uc774\uc0c1\ud568\uc744 \ub290\ub07c\uace0 \uace0\ucce4\ub2e4... \ubb38\uc81c\ub97c \ub611\ubc14\ub85c \uc77d\uc790<\/p>\n
\ubcc4\ub2e4\ub978 \uc54c\uace0\ub9ac\uc998\uc740 \uc5c6\ub294 \uac83 \uac19\uace0 \ud050\ub97c \uc774\uc6a9\ud55c \uad6c\ud604 \ubb38\uc81c\uc778 \uac83 \uac19\ub2e4. \uc8fc\uc5b4\uc9c4 \uce90\uc2dc \ud06c\uae30\ub9cc\ud07c \ubc30\uc5f4\uc744 \uc720\uc9c0\ud574\uc8fc\uba74\uc11c \uad6c\ud604\ud574\uc8fc\uc5c8\ub2e4.<\/p>\n
\ub0b4 \ucf54\ub4dc<\/b><\/h2>\n
from collections import deque\n\ndef solution(cacheSize, cities):\n    if cacheSize == 0:\n        return 5 * len(cities)\n\n    ans = 0\n    cache = deque([])\n    for city in cities:\n        # \ub300\uc18c\ubb38\uc790 \uad6c\ubd84 \uc5c6\uc73c\ub2c8\uae4c \uc815\uaddc\ud654\n        city = city.lower()\n\n        if city in cache:\n            ans += 1\n            cache.remove(city)\n            cache.append(city)\n        else:\n            ans += 5\n            if len(cache) == cacheSize:\n                cache.popleft()\n\n            cache.append(city)\n            \n\treturn ans<\/code><\/pre>\n
deque\uc744 \uc774\uc6a9\ud574\uc11c popleft \ud558\ub294 \uacfc\uc815\uc744 \uc870\uae08\uc774\ub098\ub9c8 \ucd5c\uc801\ud654\ud574\uc8fc\uc5c8\ub2e4. \uc77c\ubc18\uc801\uc778 \ubc30\uc5f4\uc5d0\uc11c \uccab \ubc88\uc9f8 \uc6d0\uc18c\ub97c \uc81c\uac70\ud558\ub294 \uc5f0\uc0b0\uc740 O(n)\uc758 \uc2dc\uac04\uc774 \ub4e4\uae30 \ub54c\ubb38\uc5d0 \uccab \ubc88\uc9f8 \uc6d0\uc18c \uc5f0\uc0b0\uc774 O(1)\uc778 deque\uc744 \uc0ac\uc6a9\ud558\uc5ec \ud480\uc774\ud588\ub2e4.<\/p>\n
 <\/p>\n
\uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 \ubaa8\ub4e0 cities\ub97c \uc21c\ud68c\ud558\uba74\uc11c \uce90\uc2dc\ub97c \uc21c\ud68c\ud558\uba70 \uc0ad\uc81c, \ucd94\uac00\ud574\uc8fc\uae30 \ub54c\ubb38\uc5d0 O(n * m) - n: cities\uc758 \ud06c\uae30, m: \uce90\uc2dc\uc758 \ud06c\uae30<\/b>\uc774\ub2e4.<\/p>\n
\uace0\ucc30<\/b><\/h2>\n
\uc544\ubb34\ub9ac \uc0dd\uac01\ud574\ub3c4 remove \uc5f0\uc0b0\uc774 \ub108\ubb34 \uac70\uc2ac\ub824\uc11c \ucd5c\uc801\ud654\ud560 \uc218 \uc788\ub294 \ubc29\ubc95\uc774 \uc5c6\uc744\uae4c \uace0\ubbfc\ud558\ub2e4\uac00 \ud30c\uc774\uc36c\uc758 OrderedDict\ub77c\ub294 \uc790\ub8cc\uad6c\uc870\ub97c \ubc1c\uacac\ud588\ub2e4! \uc21c\uc11c\ub97c \uc870\uc791\ud560 \uc218 \uc788\ub294 \ud574\uc2dc\ub9f5\uc774\ub77c\uace0 \ud55c\ub2e4. OrderedDict\ub97c \uc0ac\uc6a9\ud558\uba74 \uc790\uc5f0\uc2a4\ub7fd\uac8c \ub9c8\uc9c0\ub9c9 \uce90\uc2dc\uac00 \uac00\uc7a5 \ub9c8\uc9c0\ub9c9\uc73c\ub85c \uc0ac\uc6a9\ud55c \uce90\uc2dc\uac00 \ub418\uae30 \ub54c\ubb38\uc5d0 remove\ud574\uc8fc\ub294 \uacfc\uc815\uc774 O(1)\ub85c \uc904\uc5b4\ub4e0\ub2e4.<\/p>\n
# OrderedDict \uc0ac\uc6a9\n\nfrom collections import OrderedDict\n\ndef solution(cacheSize, cities):\n    if cacheSize == 0:\n        return 5 * len(cities)\n\n    ans = 0\n    cache = OrderedDict()\n\n    for city in cities:\n        city = city.lower()\n\n        if city in cache:\n            ans += 1\n            # \uac00\uc7a5 \ub9c8\uc9c0\ub9c9 \uc0bd\uc785\ub41c \uc6d0\uc18c\ub85c \ucde8\uae09\n            cache.move_to_end(city)\n        else:\n            ans += 5\n            if len(cache) == cacheSize:\n            \t# \uac00\uc7a5 \ucc98\uc74c \uc0bd\uc785\ub41c \uc6d0\uc18c \uc0ad\uc81c\n                cache.popitem(last=False)\n            cache[city] = True\n\n    return ans<\/code><\/pre>\n
 <\/p>\n
\uc2dc\uac04 \ubcf5\uc7a1\ub3c4: O(n)<\/b><\/p>","category":["Computer Science\/Problem Solving","\uce90\uc2dc","\ud504\ub85c\uadf8\ub798\uba38\uc2a4"],"author":"hojoo","guid":"https:\/\/bird-j.tistory.com\/104","comments":"https:\/\/bird-j.tistory.com\/104#entry104comment","pubDate":"Wed, 19 Nov 2025 14:52:53 +0900"},{"title":"\ud504\ub85c\uadf8\ub798\uba38\uc2a4 - \uac70\ub9ac\ub450\uae30 \ud655\uc778\ud558\uae30","link":"https:\/\/bird-j.tistory.com\/103","description":"
\ubb38\uc81c \uc124\uba85<\/b><\/h2>\n
<\/span><\/figure>\n<\/p>\n
\uc81c\ud55c\uc0ac\ud56d \ubc0f \uc785\ucd9c\ub825<\/b><\/h2>\n
<\/span><\/figure>\n
<\/span><\/figure>\n<\/p>\n
\ud480\uc774<\/b><\/h2>\n
\uc65c \uc774\ub7f0 \ubb38\uc81c\ub9cc \ubcf4\uba74 bfs\uc5d0 \uc0ac\ub85c\uc7a1\ud788\ub294\uac74\uc9c0 \ubaa8\ub974\uaca0\ub2e4. \ud2c0\uc5d0 \uac07\ud78c \uc0ac\uace0\uac00 \ub418\uc5b4\ubc84\ub9b0 \uac83\ub9cc \uac19\uc9c0\ub9cc \uadf8\ub798\ub3c4 \uac00\uc7a5 \uba3c\uc800 \uc0dd\uac01\ud55c \uc54c\uace0\ub9ac\uc998\uc73c\ub85c \ud480\uc774\ud574\ubcf4\uae30\ub85c \ud588\ub2e4..<\/p>\n
\uac01 \uc751\uc2dc\uc790\uc758 \uc790\ub9ac\uc5d0\uc11c bfs\ub97c \ub3cc\ub9ac\uba74\uc11c \ub9e8\ud574\ud2bc \uac70\ub9ac \ub0b4\uc5d0 \uc0ac\ub78c\uc774 \uc788\ub294\uc9c0 \ud655\uc778\ud574\uc8fc\uc5c8\ub2e4. while \ub8e8\ud504 \ub0b4\uc5d0 for\ubb38\uc73c\ub85c queue\uc758 \uae38\uc774\ub97c \uc7ac\uc11c \uac01 \ud0d0\uc0c9\uc744 \uad6c\ubd84\ud558\uc5ec \ub9e8\ud574\ud2bc\uac70\ub9ac\ub97c \uc7c0\ub2e4. bfs\ub97c \ub3cc\ub9b4 \ub54c \ud30c\ud2f0\uc158\uc740 \uadf8\ub0e5 \uc548\uac00\uba74 \uc62c\ubc14\ub978 \ub9e8\ud574\ud2bc \uac70\ub9ac\ub97c \ub3c4\ucd9c\ud560 \uc218 \uc788\ub2e4. \uc774\ud6c4 \ud55c \uba85\uc774\ub77c\ub3c4 \uc704\ubc18\ud588\ub2e4\uba74 0\uc73c\ub85c \uc138\ud305\ud558\uace0 ans \ubc30\uc5f4\uc5d0 \ub123\uc5b4\uc8fc\uc5c8\ub2e4.<\/p>\n
 <\/p>\n
\ub0b4 \ucf54\ub4dc<\/b><\/h2>\n
from collections import deque\n\ndx = [0, 1, -1, 0]\ndy = [1, 0, 0, -1]\n\ndef bfs(matrix, sx, sy):\n    queue = deque([(sx, sy)])\n    visited = set([(sx, sy)])\n    \n    cnt = 1\n    while queue:\n        for _ in range(len(queue)):\n            x, y = queue.popleft()\n            \n            for i in range(4):\n                nx = x + dx[i]\n                ny = y + dy[i]\n                \n                # 5 * 5 \uc870\uac74\n                if 0 <= nx < 5 and 0 <= ny < 5:\n                    # \ud30c\ud2f0\uc158\uc774 \uc544\ub2c8\uace0 \ubc29\ubb38\ud55c \uc801 \uc5c6\uc73c\uba74 \ud0d0\uc0c9\n                    if matrix[nx][ny] != 'X' and (nx, ny) not in visited:\n                        # \ub9e8\ud574\ud2bc \uac70\ub9ac 2 \ub0b4\ub85c \uc0ac\ub78c\uc774 \uc788\uc73c\uba74 false \ubc18\ud658\n                        if matrix[nx][ny] == 'P' and cnt <= 2:\n                            return False\n                        visited.add((nx, ny))\n                        queue.append((nx, ny))\n        \n        cnt += 1\n        if cnt > 2:\n            return True\n\ndef solution(places):\n    ans = []\n    \n    # \ubaa8\ub4e0 \ub300\uae30\uc2e4\uc758 \ubaa8\ub4e0 \uc0ac\ub78c\uc744 \uc2dc\uc791\uc810\uc73c\ub85c bfs \ub3cc\ub9ac\uae30\n    for place in places:\n        flag = 1\n        for j in range(5):\n            for k in range(5):\n                if place[j][k] == 'P':\n                    # \ud55c \uba85\uc774\ub77c\ub3c4 \uc548 \uc9c0\ucf1c\uc84c\uc73c\uba74 break \ud6c4 0\uc73c\ub85c \uc138\ud305\n                    if bfs(place, j, k) == 0:\n                        flag = 0\n                        break\n        \n            if not flag:\n                break\n        \n        # \ubaa8\ub450 \uc9c0\ucf1c\uc84c\uc73c\uba74 1\n        ans.append(flag)\n        \n    return ans<\/code><\/pre>\n
 <\/p>\n
\ud480\uc774\uc5d0 \ub300\ud55c \ubcc4\ub2e4\ub978 \ud2b9\uc774\uc810\uc740 \uc5c6\uae30 \ub54c\ubb38\uc5d0 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub9cc \uc124\uba85\ud574\ubcf4\uc790\uba74, \ub300\uae30\uc2e4\uc758 \uc218, \uaca9\uc790\uc758 \ud589\uc5f4\uc774 \ubaa8\ub450 5\ub85c \uace0\uc815\ub418\uc5b4\uc788\uae30 \ub54c\ubb38\uc5d0 O(5 * 5 * 5 * 25 * 4)\uc815\ub3c4 \uc77c \uac83 \uac19\ub2e4. (25\ub294 \ubaa8\ub4e0 \uc0ac\ub78c\uc774 \uaf49 \ucc28\uc788\ub2e4\uace0 \uac00\uc815\ud560\ub54c)<\/p>\n
\uace0\ucc30<\/b><\/h2>\n
\ud480\uc774\ud558\uace0 \ub098\ub2c8 \uadf8\ub0e5 \uac01 \ucc38\uc11d\uc790\ub4e4\uc744 \uae30\uc900\uc73c\ub85c \ub9e8\ud574\ud2bc \uac70\ub9ac\ub97c \uacc4\uc0b0\ud558\ub294 \ubc29\ubc95\uc774 \ub354 \uc26c\uc6b8 \uac83 \uac19\uc544\uc11c \ud480\uc774\ud574\ubcf4\uc558\ub2e4.<\/p>\n
 <\/p>\n
# \ub9e8\ud574\ud2bc \uac70\ub9ac 2\uae4c\uc9c0 \uc9c1\uc811 \ud655\uc778 \ndef check_place(place):\n    for i in range(5):\n        for j in range(5):\n            if place[i][j] != 'P':\n                continue\n\n            # \uac70\ub9ac 1 (\uc0c1\ud558\uc88c\uc6b0)\n            for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n                ni, nj = i + di, j + dj\n                if 0 <= ni < 5 and 0 <= nj < 5 and place[ni][nj] == 'P':\n                    return 0\n\n            # \uac70\ub9ac 2 (\uc9c1\uc120)\n            for di, dj in [(2, 0), (-2, 0), (0, 2), (0, -2)]:\n                ni, nj = i + di, j + dj\n                mi, mj = i + di \/\/ 2, j + dj \/\/ 2  # \uc911\uac04 \uce78\n                if 0 <= ni < 5 and 0 <= nj < 5:\n                    if place[ni][nj] == 'P' and place[mi][mj] == 'O':\n                        return 0\n\n            # \uac70\ub9ac 2 (\ub300\uac01\uc120)\n            for di, dj in [(1, 1), (1, -1), (-1, 1), (-1, -1)]:\n                ni, nj = i + di, j + dj\n                if 0 <= ni < 5 and 0 <= nj < 5 and place[ni][nj] == 'P':\n                    # \ub300\uac01\uc120\uc77c \ub54c \ub450 \uc911\uac04 \uce78 \uc911 \ud558\ub098\ub77c\ub3c4 O\uba74 \ud30c\ud2f0\uc158\uc774 \uc5c6\ub294 \ud310\uc815\n                    if place[i][nj] == 'O' or place[ni][j] == 'O':\n                        return 0\n\n    return 1\n\ndef solution(places):\n    return [check_place(place) for place in places]<\/code><\/pre>\n
\uad73\uc774 bfs\uae4c\uc9c0\ub294 \ud544\uc694\uc5c6\uc5c8\ub358 \uac83 \uac19\ub2e4..! \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub3c4 bfs\uc5d0\uc11c\ub294 \ud55c \ubc88 \ub354 \uae4a\uac8c \ud0d0\uc0c9\ud574\uc57c\ud558\ub294 \uacbd\uc6b0\ub3c4 \uc904\uc5b4\ub4e4\uc5b4 \uc870\uae08 \ub354 \ucd5c\uc801\ud654 \ub41c \uac83 \uac19\ub2e4.<\/p>","category":["Computer Science\/Problem Solving","\uac70\ub9ac\ub450\uae30 \ud655\uc778\ud558\uae30","\ud504\ub85c\uadf8\ub798\uba38\uc2a4"],"author":"hojoo","guid":"https:\/\/bird-j.tistory.com\/103","comments":"https:\/\/bird-j.tistory.com\/103#entry103comment","pubDate":"Tue, 18 Nov 2025 22:15:55 +0900"},{"title":"\ud504\ub85c\uadf8\ub798\uba38\uc2a4 - \uc870\uc774\uc2a4\ud2f1","link":"https:\/\/bird-j.tistory.com\/102","description":"
\ubb38\uc81c \uc124\uba85<\/b><\/h2>\n
<\/span><\/figure>\n<\/p>\n
\uc81c\ud55c\uc0ac\ud56d \ubc0f \uc785\ucd9c\ub825<\/b><\/h2>\n
<\/span><\/figure>\n<\/p>\n
\ud480\uc774<\/b><\/h2>\n
\ubb38\uc81c\uac00 \ucc38 \uac04\ub2e8\uba85\ub8cc\ud558\ub2e4. A\ub85c \ucd08\uae30\ud654\ub41c \ubb38\uc790\uc5f4\uc744 \uc0c1\ud558\uc88c\uc6b0\ub85c \uc6c0\uc9c1\uc5ec \ubaa9\ud45c \ubb38\uc790\uc5f4\ub85c \ubc14\uafb8\ub294 \ubb38\uc81c\uc774\ub2e4. \uc0c1\ud558\ub294 \uace0\uc815\ub418\uc5b4\uc788\uae30 \ub54c\ubb38\uc5d0 \uc544\uc2a4\ud0a4\ucf54\ub4dc\ub97c \uc774\uc6a9\ud574\uc11c \ucd5c\uc19f\uac12<\/b>\uc744 \uad6c\ud574\uc8fc\uc5c8\ub2e4. \uc8fc\uc758\ud560 \uc810\uc740 \uc88c\uc6b0\ub85c \uc6c0\uc9c1\uc77c \ub54c \ubaa9\ud45c \ubb38\uc790\uc5f4\uc758 \uc5f0\uc18d\ub41c A \uad6c\uac04\uc744 \ub9cc\ub09c\ub2e4\uba74 \uc9c1\uc9c4\ud558\ub294 \uac83\ubcf4\ub2e4 \ub3cc\uc544\uac00\ub294 \uac83\uc774 \ub354 \ube60\ub97c \uc218\ub3c4 \uc788\ub2e4\ub294 \uac83<\/b>\uc774\ub2e4. \ubb54\uac00 \uc218\ud559\uc801\uc73c\ub85c \uc811\uadfc\ud560 \uc218\ub3c4 \uc788\uc744 \uac83 \uac19\uc544\uc11c \uace0\ubbfc\uc744 \ud574\ubcf4\uc558\ub294\ub370,,, \uc798 \ub418\uc9c4 \uc54a\uc558\ub2e4.<\/p>\n
\uadf8\ub0e5 \uccab \ubc88\uc9f8 \uce78\ubd80\ud130 \uc804\ubd80 \ud655\uc778\ud558\uba74\uc11c \uc5b4\ub290 \uad6c\uac04\uc5d0\uc11c \uaebe\ub294 \uac83\uc774 \ub354 \ube60\ub978\uc9c0 \ubaa8\ub450 \uacc4\uc0b0\ud574\uc8fc\uba74\uc11c \ud480\uc774<\/b>\ud574\uc8fc\uc5c8\ub2e4.<\/p>\n
\ub0b4 \ucf54\ub4dc<\/b><\/h2>\n
def solution(name):\n    n = len(name)\n    updown = sum(min(ord(c) - 65, 26 - (ord(c) - 65)) for c in name)\n\n    move = n - 1\n    for i in range(n):\n        j = i + 1\n        \n        while j < n and name[j] == 'A':\n            j += 1\n        # \uc624\ub978\ucabd\uc73c\ub85c i\uae4c\uc9c0 \uac14\ub2e4\uac00 \uc67c\ucabd\uc73c\ub85c \ub3cc\uc544\uc11c j \uc774\ud6c4\ub85c \uac00\ub294 \ucf00\uc774\uc2a4\ub4e4 \ube44\uad50\n        move = min(move, 2 * i + (n - j), i + 2 * (n - j))\n\n    return updown + move<\/code><\/pre>\n
 <\/p>\n
\ub9e4\ubc88 move\ub97c \uac31\uc2e0\ud560 \ub54c i + 2 * (n - j)<\/b>\ub3c4 \ud655\uc778\ud574\uc8fc\uc5c8\ub294\ub370, \ucc98\uc74c\uc5d4 \uc67c\ucabd\uc73c\ub85c \uac00\ub294 \uacbd\uc6b0\ub9cc \uc0dd\uac01\ud574\uc8fc\ub2e4\uac00 \ud2c0\ub838\ub2e4. \uc0dd\uac01\ud574\ubcf4\ub2c8 \uc5f0\uc18d\ub41c A \uad6c\uac04\uc774 \uc55e\ucabd\uc5d0 \uac00\uae5d\ub2e4\uba74 \ub4b7\ucabd\uc744 \uba3c\uc800 \ucc98\ub9ac\ud558\uace0 \uc640\uc57c\ud558\uae30 \ub54c\ubb38<\/b>\uc5d0 \uc774 \uacbd\uc6b0\ub3c4 \uc0dd\uac01\ud574\uc8fc\uc5b4\uc57c\ud55c\ub2e4... \uc774 \ubd80\ubd84\uc774 \uc774 \ubb38\uc81c\uc758 \ud575\uc2ec\uc774\uc5c8\ub358 \uac83 \uac19\ub2e4.<\/p>\n
 <\/p>\n
\uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(n)<\/b>\uc774\ub2e4. \ub0b4\ubd80 while\ubb38\uc5d0\uc11c\ub3c4 \ucd5c\uc545\uc758 \uacbd\uc6b0 \uc5b4\ucc28\ud53c \uc21c\ud68c\ub294 \ud55c \ubc88\ub9cc \uc77c\uc5b4\ub098\uae30 \ub54c\ubb38\uc5d0 n\uc744 \ubc97\uc5b4\ub098\uc9c0 \uc54a\ub294\ub2e4.<\/p>","category":["Computer Science\/Problem Solving","\uc870\uc774\uc2a4\ud2f1","\ud504\ub85c\uadf8\ub798\uba38\uc2a4"],"author":"hojoo","guid":"https:\/\/bird-j.tistory.com\/102","comments":"https:\/\/bird-j.tistory.com\/102#entry102comment","pubDate":"Mon, 17 Nov 2025 20:33:33 +0900"},{"title":"\ud504\ub85c\uadf8\ub798\uba38\uc2a4 - \uba54\ub274 \ub9ac\ub274\uc5bc","link":"https:\/\/bird-j.tistory.com\/100","description":"
\ubb38\uc81c \uc124\uba85<\/b><\/h2>\n
<\/span><\/figure>\n
<\/span><\/figure>\n<\/p>\n
\uc81c\ud55c\uc0ac\ud56d \ubc0f \uc785\ucd9c\ub825<\/b><\/h2>\n
<\/span><\/figure>\n
<\/span><\/figure>\n<\/p>\n
\ud480\uc774<\/b><\/h2>\n
\uc5ed\uc2dc \uce74\uce74\uc624\ub2f5\uac8c \ubb38\uc81c\uac00 \uc27d\uc9c0\uc54a\ub2e4. \uc815\ub9ac\ud574\ubcf4\uc790\uba74 \uc190\ub2d8\uc774 \ub2e8\ud488\uc73c\ub85c \uc8fc\ubb38\ud55c \uba54\ub274\ub4e4<\/b>\uacfc \ub9cc\ub4e4\uc5b4\uc57c\ud558\ub294 \ucf54\uc2a4\uc694\ub9ac\uc5d0 \ud3ec\ud568\ub418\uc5b4\uc57c\ud558\ub294 \ub2e8\ud488 \uc694\ub9ac \uc218<\/b>\uac00 \uc8fc\uc5b4\uc9c0\uace0, \ub9cc\ub4e4\uc5b4\uc57c\ud558\ub294 \ucf54\uc2a4 \uc694\ub9ac\uc758 \uc81c\uc57d\uc870\uac74\uc740 \ub2e4\uc74c\uacfc \uac19\ub2e4.<\/p>\n
1. 2\uac1c \uc774\uc0c1\uc758 \uba54\ub274\ub85c \uc774\ub8e8\uc5b4\uc838\uc57c\ud568.<\/p>\n
2. 2\uba85 \uc774\uc0c1\uc758 \uc190\ub2d8\uc774 \uc8fc\ubb38\ud55c \uba54\ub274\uc5ec\uc57c\ud568<\/p>\n
3. \uac01 \ucf54\uc2a4\uc694\ub9ac \ubcc4\ub85c \uac00\uc7a5 \ub9ce\uc774 \uc8fc\ubb38\ub41c \uba54\ub274 \uad6c\uc131\uc744 \uc0ac\uc804\uc21c\uc73c\ub85c \ucd9c\ub825 (\ub9cc\uc57d \uac19\ub2e4\uba74 \ubaa8\ub450 \ucd9c\ub825)<\/p>\n
 <\/p>\n
\uc774\ub97c \uc704\ud574 \uc5ed\uc2dc \uac00\uc7a5 \uba3c\uc800 \uc0dd\uac01\ub09c \ubc29\ubc95\uc740 \uc870\ud569\uc774\ub2e4. orders\uc640 course\uc758 \ubc30\uc5f4 \ud06c\uae30\uac00 \uc791\uc544 \ubaa8\ub4e0 \uc870\ud569\uc744 \ucc3e\uc744 \uc218 \uc788\ub2e4\ub294 \uc0dd\uac01\uc774 \ub4e4\uc5c8\ub2e4. \uac01 \uc8fc\ubb38\ub4e4\uc744 \uc21c\ud68c\ud558\uba70 \uc8fc\uc5b4\uc9c4 \ucf54\uc2a4\uc694\ub9ac\uc758 \uac1c\uc218\ub9cc\ud07c \ubaa8\ub4e0 \uc870\ud569\uc744 \ub9cc\ub4e4\uace0, \ud574\uc2dc\ub9f5\uc73c\ub85c \uad00\ub9ac\ud558\uba74\uc11c \uc774\ubbf8 \uc874\uc7ac\ud55c\ub2e4\uba74 \ub098\uc628 \uc218\ub97c \uc62c\ub824\uc8fc\uace0 \uc5c6\ub2e4\uba74 \ucd94\uac00\ud574\uc8fc\ub294 \ubc29\uc2dd\uc73c\ub85c \ud480\uc774\ud558\uc600\ub2e4.<\/p>\n
\ub0b4 \ucf54\ub4dc<\/b><\/h2>\n
from collections import Counter\nfrom itertools import combinations\n  \ndef solution(orders, course):\n    # \uae38\uc774 i \ucf54\uc2a4\uc694\ub9ac\uc758 \uc885\ub958\uc640 \ube48\ub3c4\n    counts = {i: Counter() for i in course}\n\n    # \uac1c\uc218 \uc138\uae30 (\uae38\uc774\uc5d0 \ub530\ub978 \ubaa8\ub4e0 \uc870\ud569)\n    for i in orders:        \n        for j in course:\n            if len(i) >= j:\n                for comb in combinations(i, j):\n                    counts[j][''.join(sorted(comb))] += 1   # WX, XW \ucc98\ub7fc \uac19\uc740 \ud0a4\uac00 \ubd84\ub9ac\ub418\ub294 \uacbd\uc6b0\n\n    ans = []\n    for i in course:\n        if not counts[i]: continue\n        \n        # \uae38\uc774 i\uc758 \ucf54\uc2a4\uc694\ub9ac\uc758 \uc885\ub958\uc5d0\uc11c 2\uba85 \uc774\uc0c1\uc774 \uc2dc\ud0a8 \uc870\ud569\ub4e4 \uc911 \ube48\ub3c4\uac00 \ucd5c\ub313\uac12 \uc870\ud569\ub9cc ans\uc5d0 \ucd94\uac00\n        max_cnt = max(counts[i].values())\n        if max_cnt >= 2:\n            ans += [k for k, v in counts[i].items() if v == max_cnt]\n        \n    return sorted(ans)<\/code><\/pre>\n
\ucc98\uc74c\uc5d4 counts \ud574\uc2dc\ub9f5\uc5d0 \ud0a4\ub97c \uc815\ub82c\ud558\uc9c0 \uc54a\uace0 \ub123\uc5b4\uc8fc\uc5c8\ub354\ub2c8 WX, XW\uc640 \uac19\uc740 \uacbd\uc6b0\ub97c \uc7a1\uc9c0 \ubabb\ud574 \uc62c\ubc14\ub978 \ud574\ub97c \ub3c4\ucd9c\ud574\uc8fc\uc9c0 \ubabb\ud588\ub2e4. \ucd94\uac00\uc801\uc73c\ub85c \ud0a4\ub97c \ub123\uc744 \ub54c \uc815\ub82c\ud574\uc8fc\uc5b4 \ud574\uacb0\ud574\uc8fc\uc5c8\ub2e4. \uc9c0\uae08 \uc0dd\uac01\ud574\ubcf4\ub2c8 \uadf8\ub0e5 order\ub97c \uc21c\ud68c\ud560 \ub54c i\ub97c \uc815\ub82c\ud574\uc8fc\uc5b4\ub3c4 \ub418\uc5c8\ub294\ub370 \uc65c \uc774\ub807\uac8c \ud588\uc744\uae4c... <\/p>\n
\uc774\ub807\uac8c \ub9cc\ub4e4\uc5b4\uc900 \uba54\ub274 \uae38\uc774 \ubcc4 \ucf54\uc2a4\uc694\ub9ac\uc758 \ubaa8\ub4e0 \uc870\ud569\ub4e4\uc744 \uc21c\ud68c\ud558\uba70 \uac00\uc7a5 \ube48\ub3c4\uac00 \ub9ce\uc740 \uc870\ud569\ub9cc ans\uc5d0 \ucd94\uac00\ud574\uc8fc\uc5b4 \ud480\uc774\ud588\ub2e4.<\/p>","category":["Computer Science\/Problem Solving","\uba54\ub274 \ub9ac\ub274\uc5bc","\ud504\ub85c\uadf8\ub798\uba38\uc2a4"],"author":"hojoo","guid":"https:\/\/bird-j.tistory.com\/100","comments":"https:\/\/bird-j.tistory.com\/100#entry100comment","pubDate":"Sun, 16 Nov 2025 02:31:32 +0900"},{"title":"\ud504\ub85c\uadf8\ub798\uba38\uc2a4 - \uc11c\ubc84 \uc99d\uc124 \ud69f\uc218","link":"https:\/\/bird-j.tistory.com\/99","description":"
\ubb38\uc81c \uc124\uba85<\/b><\/h2>\n
<\/span><\/figure>\n<\/p>\n
\uc81c\ud55c\uc0ac\ud56d \ubc0f \uc785\ucd9c\ub825<\/b><\/h2>\n
<\/span><\/figure>\n
<\/span><\/figure>\n<\/p>\n
\ud480\uc774<\/b><\/h2>\n
\ubcc4\ub2e4\ub978 \uc54c\uace0\ub9ac\uc998\uc801 \uc0ac\uace0\uac00 \ud544\uc694\ud558\ub2e4\uae30\ubcf4\ub2e8 \uad6c\ud604\uc744 \ud655\uc778\ud558\ub294 \ubb38\uc81c\uc778 \uac83 \uac19\ub2e4. \ud604\uc7ac \ud65c\uc131\ud654\ub41c \uc11c\ubc84\ub97c \ud2b8\ub798\ud0b9\ud558\uace0 \ud544\uc694\ud55c\ub9cc\ud07c \ucd94\uac00\ud574\uc11c 24\uc2dc\uac04 \ub0b4\uc5d0 \uba87 \ubc88\uc774\ub098 \uc99d\uc124\ub418\uc5c8\ub294\uc9c0 \uad6c\ud574\uc8fc\uc5c8\ub2e4.<\/p>\n
\ub0b4 \ucf54\ub4dc<\/b><\/h2>\n
def solution(players, m, k):\n    n = len(players)\n\n    diff = [0] * (n + k + 1)\n    active = 0\n    ans = 0\n    for t, p in enumerate(players):\n        # \ub9cc\ub8cc \ucc98\ub9ac (\uc774\uc804\uae4c\uc9c0\uc758 \uc99d\uc124 \uc911 \uc774\ubc88 \uc2dc\uc810\uc5d0 \ub9cc\ub8cc\ub418\ub294 \uc11c\ubc84 \ubc18\uc601)\n        active += diff[t]\n\n        needed = p \/\/ m\n        if needed > active:\n            add = needed - active\n            ans += add\n            active += add\n            diff[t + k] -= add\n\n    return ans<\/code><\/pre>\n
\uc5b8\uc81c \ub9cc\ub8cc\ub418\ub294\uc9c0 \ud655\uc778\uc774 \ud544\uc694\ud55c \ubb38\uc81c\ub294 \ub204\uc801\ud569\ucc98\ub7fc \ubc30\uc5f4\ub85c \ub05d\ub098\ub294 \uc778\ub371\uc2a4\uc5d0 \ub9c8\ud0b9\ud574\uc8fc\uc5b4 \ucc98\ub9ac\ud574\uc8fc\uba74 \uc880 \ub354 \uac04\ud3b8\ud558\uac8c \ucc98\ub9ac\ud560 \uc218 \uc788\ub2e4. diff \ubc30\uc5f4\uc744 \uc0ac\uc6a9\ud558\uc5ec \ud604\uc7ac \ucd94\uac00\ud55c \uc11c\ubc84\uac00 \uc5b8\uc81c \ube60\uc9c0\ub294\uc9c0 \uccb4\ud06c\ud574\uc8fc\uc5b4 \ud604\uc7ac \ud65c\uc131\ud654\ub41c \uc11c\ubc84\uc758 \uac1c\uc218\ub97c \ud2b8\ub798\ud0b9\ud574\uc8fc\uc5c8\ub2e4.<\/p>\n
 <\/p>","category":["Computer Science\/Problem Solving","\uc11c\ubc84 \uc99d\uc124 \ud69f\uc218","\ud504\ub85c\uadf8\ub798\uba38\uc2a4"],"author":"hojoo","guid":"https:\/\/bird-j.tistory.com\/99","comments":"https:\/\/bird-j.tistory.com\/99#entry99comment","pubDate":"Sat, 15 Nov 2025 11:01:24 +0900"},{"title":"\ud504\ub85c\uadf8\ub798\uba38\uc2a4 - \ub4f1\uad63\uae38","link":"https:\/\/bird-j.tistory.com\/95","description":"
\ubb38\uc81c \uc124\uba85<\/b><\/h2>\n
<\/span><\/figure>\n<\/p>\n
\uc81c\ud55c\uc0ac\ud56d \ubc0f \uc785\ucd9c\ub825<\/b><\/h2>\n
<\/span><\/figure>\n<\/p>\n
\ud480\uc774<\/b><\/h2>\n
\uc815\ub9d0 \uc815\uc11d\uc801\uc778 DP \ubb38\uc81c\uc774\ub2e4. \ucd94\uac00\uc801\uc73c\ub85c \uac00\uc9c0 \ubabb\ud558\ub294 \ud0c0\uc77c\ub9cc \uace0\ub824\ud574\uc8fc\uba74 \ub41c\ub2e4.<\/p>\n
 <\/p>\n
dp[i][j] = [0, 0]\uc5d0\uc11c [i, j]\uae4c\uc9c0 \ub3c4\ub2ec\ud560 \uc218 \uc788\ub294 \ubc29\ubc95\uc758 \uc218<\/p>\n
\ub0b4 \ucf54\ub4dc<\/b><\/h2>\n
MOD = 10**9 + 7\n\ndef solution(m, n, puddles):\n    dp = [[0] * m for _ in range(n)]\n    for x, y in puddles:\n        dp[y-1][x-1] = -1\n        \n    for i in range(m):\n        if dp[0][i] == -1: break\n        dp[0][i] = 1\n    for i in range(n):\n        if dp[i][0] == -1: break\n        dp[i][0] = 1\n    \n    for i in range(1, n):\n        for j in range(1, m):\n            if dp[i][j] == -1: continue\n            \n            dp[i][j] = max(dp[i-1][j], 0) + max(dp[i][j-1], 0)\n    \n    return dp[-1][-1] % MOD<\/code><\/pre>\n
 <\/p>\n
\uba3c\uc800 \uccab \ubc88\uc9f8 \ud589\uacfc \uc5f4\uc744 1\ub85c \ucd08\uae30\ud654\ud574\uc8fc\uba74\uc11c \uc911\uac04\uc5d0 \uac00\uc9c0 \ubabb\ud558\ub294 \ud0c0\uc77c\uc744 \ub9cc\ub098\uba74 \uc911\ub2e8\ud574\uc8fc\uc5c8\ub2e4.<\/p>\n
\uac00\uc9c0 \ubabb\ud558\ub294 \ud0c0\uc77c\uc744 -1\ub85c \ucd08\uae30\ud654\ud574\uc8fc\uc5c8\uae30 \ub54c\ubb38\uc5d0 \uc774\ud6c4 <\/span><\/span>0\uacfc \ube44\uad50\ud574\uc8fc\uba74\uc11c \uc0c1\ud0dc\uc804\uc774\ud574\uc8fc\uc5c8\ub2e4.<\/p>\n
 <\/p>\n
\uc2dc\uac04 \ubcf5\uc7a1\ub3c4: O(n*m) - \ubaa8\ub4e0 \uaca9\uc790 \ud0d0\uc0c9<\/b><\/p>\n
\uace0\ucc30<\/b><\/h2>\n
1\ucc28\uc6d0 dp\ub85c \uc555\ucd95\ud560 \uc218 \uc788\ub2e4. \ubc30\ub0ad\ubb38\uc81c\ub3c4 \uadf8\ub807\uace0 dp \ubb38\uc81c\ub4e4\uc740 \ucc28\uc6d0\uc744 \uc904\uc774\uba74\uc11c \ucd5c\uc801\ud654\ud558\ub294\uac8c \uc7ac\ubc0c\ub294 \uac83 \uac19\ub2e4. \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 \ub3d9\uc77c\ud558\uc9c0\ub9cc \uacf5\uac04 \ubcf5\uc7a1\ub3c4\uac00 \uc904\uc5c8\ub2e4.<\/p>\n
 <\/p>\n
dp \ud14c\uc774\ube14 \uc815\uc758\ub294 \ub2e4\uc74c\uacfc \uac19\ub2e4.<\/p>\n
dp[x] = \ud604\uc7ac y\ud589\uc5d0\uc11c [x, y]\uae4c\uc9c0 \uc624\ub294 \uacbd\uc6b0\uc758 \uc218<\/b><\/p>\n
 <\/p>\n
\uc774\uc911 for\ubb38\uc5d0\uc11c \ubc14\uae65\ucabd \ubc18\ubcf5\ubb38\uc740 \uc704\uc5d0\uc11c \uc544\ub798\ub85c \ud55c \uc904\uc529 \ub0b4\ub824\uc624\ub294 \ubc18\ubcf5\uc774\ub2e4. [x, y]\ub97c \ucc98\ub9ac\ud560 \ub54c dp[x]\uc5d0\ub294 \uc704 \uce78\uae4c\uc9c0\uc758 \uacbd\ub85c \uc218\uac00 \uc800\uc7a5\ub418\uc5b4\uc788\uace0, dp[x-1]\uc5d0\ub294 \uc67c\ucabd \uce78\uae4c\uc9c0\uc758 \uacbd\ub85c \uc218\uac00 \uc800\uc7a5<\/b>\ub418\uc5b4 \uc788\ub2e4.<\/p>\n
MOD = 10**9 + 7\n\ndef solution(m, n, puddles):\n    blocked = {(x - 1, y - 1) for x, y in puddles}\n\n    dp = [0] * m\n    dp[0] = 1\n\n    for y in range(n):\n        for x in range(m):\n            if (x, y) in blocked:\n                dp[x] = 0\n            elif x > 0:\n                dp[x] = (dp[x] + dp[x - 1]) % MOD\n            # x == 0\uc774\uba74 \uc704\uc5d0\uc11c \ub0b4\ub824\uc624\ub294 \uac12(dp[0])\ub9cc \uc720\uc9c0\n\n    return dp[-1] % MOD<\/code><\/pre>\n
 <\/p>","category":"Computer Science\/Problem Solving","author":"hojoo","guid":"https:\/\/bird-j.tistory.com\/95","comments":"https:\/\/bird-j.tistory.com\/95#entry95comment","pubDate":"Wed, 5 Nov 2025 20:05:25 +0900"},{"title":"\ud504\ub85c\uadf8\ub798\uba38\uc2a4 - k\uc9c4\uc218\uc5d0\uc11c \uc18c\uc218 \uac1c\uc218 \uad6c\ud558\uae30","link":"https:\/\/bird-j.tistory.com\/94","description":"
\ubb38\uc81c \uc124\uba85<\/b><\/h2>\n
<\/span><\/figure>\n<\/p>\n
\uc81c\ud55c\uc0ac\ud56d \ubc0f \uc785\ucd9c\ub825<\/b><\/h2>\n
<\/span><\/figure>\n<\/p>\n
\ud480\uc774<\/b><\/h2>\n
\uce74\uce74\uc624 \ubb38\uc81c\ub2f5\uac8c \uc124\uba85\uc774 \uce5c\uc808\ud558\ub2e4. \uae00\uc774 \ub9ce\uc544 \uc870\uae08 \ubcf5\uc7a1\ud574\ubcf4\uc774\uc9c0\ub9cc \uc8fc\uc5b4\uc9c4 \uc22b\uc790 n\uc744 k\uc9c4\uc218\ub85c \ubc14\uafb8\uace0 0\uc73c\ub85c split\ud55c \ud6c4 \ub098\uc628 \uc22b\uc790\ub4e4\uc774 \uc18c\uc218\uc778\uc9c0 \ud310\ubcc4\ud558\ub294 \ubb38\uc81c\uc774\ub2e4.<\/p>\n
\ubcc4\ub2e4\ub978 \uc54c\uace0\ub9ac\uc998\uc774 \uc788\ub294 \uac83 \uac19\uc9c0\ub294 \uc54a\uace0 \uadf8\ub0e5 \uad6c\ud604 \ubb38\uc81c\uac19\ub2e4.<\/p>\n
\ub0b4 \ucf54\ub4dc<\/b><\/h2>\n
def convert_to_k(n, k):\n    if n == 0:\n        return \"0\"\n    \n    ret = []\n    while n > 0:\n        ret.append(str(n % k))\n        n \/\/= k\n        \n    return \"\".join(reversed(ret))\n\ndef is_prime(x):\n    if x < 2:\n        return False\n    \n    for i in range(2, int(x**0.5)+1):\n        if x % i == 0:\n            return False\n        \n    return True\n\ndef solution(n, k):\n    k_num = convert_to_k(n, k)\n    \n    # \"\", \"1\" \uc81c\uac70 \ud6c4 int\ub85c \ubcc0\ud658\n    num = list(map(int, filter(lambda x: x not in (\"\", \"1\"), k_num.split(\"0\"))))\n    \n    return sum(is_prime(i) for i in num)<\/code><\/pre>\n
n\uc744 k\uc9c4\uc218\ub85c \ubcc0\ud658\ud55c \uc218\uc5d0\uc11c 0\uc73c\ub85c split\ud588\uc744 \ub54c \ub098\uc62c \uc218 \uc788\ub294 \uc218\ub4e4\uc744 \uac01\uac01 \uc18c\uc218 \ud310\ubcc4\ud558\uae30 \ub54c\ubb38\uc5d0<\/p>\n
\uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(n^0.5 * log_k(n)) \uc774\ub2e4.<\/b><\/p>","category":"Computer Science\/Problem Solving","author":"hojoo","guid":"https:\/\/bird-j.tistory.com\/94","comments":"https:\/\/bird-j.tistory.com\/94#entry94comment","pubDate":"Wed, 5 Nov 2025 00:26:44 +0900"},{"title":"\ud504\ub85c\uadf8\ub798\uba38\uc2a4 - n^2 \ubc30\uc5f4 \uc790\ub974\uae30","link":"https:\/\/bird-j.tistory.com\/93","description":"
\ubb38\uc81c \uc124\uba85<\/b><\/h2>\n
<\/span><\/figure>\n<\/p>\n
\uc81c\ud55c\uc0ac\ud56d \ubc0f \uc785\ucd9c\ub825<\/b><\/h2>\n
<\/span><\/figure>\n<\/p>\n
\ud480\uc774<\/b><\/h2>\n
\uc815\ub9d0 \uad34\ub784\ud55c \uc81c\ud55c\uc0ac\ud56d\uc744 \uac00\uc9c0\uace0 \uc788\ub2e4. \ub9cc\uc57d \uc8fc\uc5b4\uc9c4\ub300\ub85c 2\ucc28\uc6d0 \ubc30\uc5f4\uc744 \ub9cc\ub4e4\uc5b4\uc11c \uc2ac\ub77c\uc774\uc2f1\ud55c\ub2e4\uba74 n^2\uc774 \uac78\ub9ac\uac8c \ub41c\ub2e4. 10^7^2 = 10^14\uc774\ubbc0\ub85c \ud0dd\ub3c4 \uc5c6\ub2e4.<\/p>\n
\uc0ac\uc2e4 \uadf8\ub0e5 \ub2e8\uc21c\ud788 2\ucc28\uc6d0 \ubc30\uc5f4\uc744 1\ucc28\uc6d0 \ubc30\uc5f4\ub85c \ub9e4\ud551\ud574\uc8fc\uba74 \ub41c\ub2e4. \uc5f0\uc18d\ub41c \uad6c\uac04\uc774\uae30 \ub54c\ubb38\uc5d0 \ubb38\uc81c\uc5c6\uc774 \ub9e4\ud551\ud574\uc904 \uc218 \uc788\ub2e4.<\/p>\n
 <\/p>\n
(\ud589, \uc5f4) \uae30\uc900\uc73c\ub85c<\/p>\n
1\ucc28\uc6d0 -> 2\ucc28\uc6d0: [(i \/\/ n), (i % n)]<\/p>\n
2\ucc28\uc6d0 -> 1\ucc28\uc6d0: row * n + col % n<\/p>\n
\uc73c\ub85c \uc778\ub371\uc2a4\ub97c \ub9e4\ud551\ud560 \uc218 \uc788\ub2e4.<\/p>\n
\ub0b4 \ucf54\ub4dc<\/b><\/h2>\n
def solution(n, left, right):\n    ans = []\n    for i in range(left, right + 1):\n        row = i \/\/ n\n        col = i % n\n        ans.append(max(row, col) + 1)\n        \n    return ans<\/code><\/pre>\n
\uace0\ucc30<\/b><\/h2>\n
\ub2e4\ub978 \ud480\uc774\ubc95\uc740 \uc0dd\uac01\ub098\uc9c0 \uc54a\ub294\ub2e4...<\/p>","category":["Computer Science\/Problem Solving","n^2 \ubc30\uc5f4 \uc790\ub974\uae30","\ud504\ub85c\uadf8\ub798\uba38\uc2a4"],"author":"hojoo","guid":"https:\/\/bird-j.tistory.com\/93","comments":"https:\/\/bird-j.tistory.com\/93#entry93comment","pubDate":"Tue, 4 Nov 2025 03:05:16 +0900"},{"title":"\ud504\ub85c\uadf8\ub798\uba38\uc2a4 - \ub124\ud2b8\uc6cc\ud06c","link":"https:\/\/bird-j.tistory.com\/92","description":"
\ubb38\uc81c \uc124\uba85<\/b><\/h2>\n
<\/span><\/figure>\n<\/p>\n
\uc81c\ud55c\uc0ac\ud56d \ubc0f \uc785\ucd9c\ub825<\/b><\/h2>\n
<\/span><\/figure>\n<\/p>\n
\ud480\uc774<\/b><\/h2>\n
\ubd84\ub9ac\ub418\uc5b4\uc788\ub294 \uadf8\ub798\ud504\uac00 \uba87 \uac1c\uc778\uc9c0 \ucc3e\ub294 \uc804\ud615\uc801\uc778 \uadf8\ub798\ud504 \ud0d0\uc0c9 \ubb38\uc81c\uc774\ub2e4.<\/p>\n
\uccab \ubc88\uc9f8 \ub178\ub4dc\ubd80\ud130 bfs\ub97c \ub3cc\ub824\uc11c \uc774\ubbf8 \ubc29\ubb38\ud55c \ub178\ub4dc\uc5d0 \ub300\ud574\uc11c\ub294 visited\ub97c \uccb4\ud06c\ud558\uace0 \ud55c \ubc88\uc758 \uadf8\ub798\ud504 \ud0d0\uc0c9\uc774 \ub05d\ub0a0 \ub54c\ub9c8\ub2e4 ans\ub97c \uc62c\ub824\uc11c \ud480\uc774\ud574\uc8fc\uc5c8\ub2e4.<\/p>\n
\ub0b4 \ucf54\ub4dc<\/b><\/h2>\n
from collections import deque\n    \ndef solution(n, computers):\n    # visited\uc640 ans\ub97c \uc804\uc5ed\uc5d0\uc11c \uad00\ub9ac\n    visited = [False] * n\n    ans = 0\n    \n    def bfs(graph, visited, start):\n        nonlocal ans\n        queue = deque([start])\n        visited[start] = True\n\n        while queue:\n            x = queue.popleft()\n            \n            # nx = \ub178\ub4dc \ubc88\ud638, e = \uac04\uc120\uc758 \uc720\ubb34\n            for nx, e in enumerate(graph[x]):\n                if e and not visited[nx]:\n                    queue.append(nx)\n                    visited[nx] = True\n                    \n        # \ud55c \ubc88\uc758 bfs(\ub124\ud2b8\uc6cc\ud06c \ud0d0\uc0c9)\uc774 \ub05d\ub098\uba74 ans += 1\n        ans += 1\n\n        return visited\n    \n    for i in range(n):\n        if not visited[i]:\n            visited = bfs(computers, visited, i)\n    \n    return ans<\/code><\/pre>\n
visited\ub97c \uc804\uc5ed \ubc30\uc5f4\ub85c \ub450\uc5b4\uc11c \ud55c \ubc88 \ubc29\ubb38\ud55c \ub178\ub4dc\ub294 \ub2e4\uc2dc \ud0d0\uc0c9\ud558\uc9c0 \uc54a\ub294 \uac83\uc774 \ud3ec\uc778\ud2b8\uc778 \uac83 \uac19\ub2e4.<\/p>\n
 <\/p>\n
\uc2dc\uac04 \ubcf5\uc7a1\ub3c4: \uadf8\ub798\ud504\uac00 \uc778\uc811\ud589\ub82c\ub85c \uc8fc\uc5b4\uc9c0\uae30 \ub54c\ubb38\uc5d0 O(n^2)\uc774\ub2e4. \uc778\uc811 \ub9ac\uc2a4\ud2b8\ub85c \uc8fc\uc5b4\uc9c4\ub2e4\uba74 \uc5f0\uacb0\ub418\uc5b4\uc788\ub294 \ub178\ub4dc\ub9cc \ud0d0\uc0c9\ud560 \uc218 \uc788\uae30 \ub54c\ubb38\uc5d0 O(v + e)\uac00 \ub418\uc5c8\uaca0\uc9c0\ub9cc \uc5ec\uae30\uc11c\ub294 \uc778\uc811 \ud589\ub82c\ub85c \uc8fc\uc5b4\uc838\uc11c \ubaa8\ub4e0 \ub178\ub4dc\ub97c \ud0d0\uc0c9\ud574\uc57c\ud55c\ub2e4.<\/p>\n
\uace0\ucc30<\/b><\/h2>\n
union-find\ub97c \uc0ac\uc6a9\ud574\uc11c \ud480\uc774\ud560 \uc218\ub3c4 \uc788\ub2e4.<\/p>\n
def solution(n, computers):\n    # parent[i] = \ub178\ub4dc i\uc758 \ubd80\ubaa8 \ub178\ub4dc (\ucd08\uae30\uac12\uc740 \ubcf8\uc778)\n    parent = list(range(n))\n    rank = [0] * n\n\n    # \ubd80\ubaa8 \ub178\ub4dc \ucc3e\uae30\n    def find(x):\n        if parent[x] != x:\n            parent[x] = find(parent[x])\n        return parent[x]\n\n    # \ub178\ub4dc\ub97c \ud558\ub098\uc758 \ub124\ud2b8\uc6cc\ud06c\ub85c \ud569\uce58\uae30\n    def union(a, b):\n        ra, rb = find(a), find(b)\n        if ra == rb:\n            return\n        \n        if rank[ra] < rank[rb]:\n            parent[ra] = rb\n        elif rank[ra] > rank[rb]:\n            parent[rb] = ra\n        else:\n            parent[rb] = ra\n            rank[ra] += 1\n    \n    # \ub450 \ub178\ub4dc\uac00 \uc5f0\uacb0\ub418\uc5b4\uc788\ub2e4\uba74 union \uc5f0\uc0b0\uc73c\ub85c \ud569\uce68\n    for i in range(n):\n        for j in range(i + 1, n):\n            if computers[i][j] == 1:\n                union(i, j)\n\n    # \uac19\uc740 \ub124\ud2b8\uc6cc\ud06c\ub77c\uba74 find(i)\uc758 \uac12\uc774 \uac19\uc73c\ubbc0\ub85c \uc9d1\ud569\uc73c\ub85c \uc911\ubcf5 \uc81c\uac70 \ud6c4 \uae38\uc774 \ubc18\ud658 = \uc11c\ub85c \ub2e4\ub978 \ub124\ud2b8\uc6cc\ud06c\uc758 \uc218\n    return len({find(i) for i in range(n)})<\/code><\/pre>\n
\uc560\ucd08\uc5d0 \uc774\ub984 \uc790\uccb4\uac00 \ubd84\ub9ac \uc9d1\ud569\uc778 \uce5c\uad6c\uc774\uae30 \ub54c\ubb38\uc5d0,,, \uc774\ub7f0 \ubb38\uc81c\ub97c \ubcf4\uba74 union-find\uac00 \uaf2d \uac19\uc774 \uc0dd\uac01\ub098\ub294 \uac83 \uac19\ub2e4. <\/p>\n
\uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 \uacb0\uad6d \ubaa8\ub4e0 \ub178\ub4dc\uc5d0 \ub300\ud574\uc11c \uc5f0\uacb0\ub418\uc5b4\uc788\ub294\uc9c0 \ucc3e\uc544\uc57c\ud558\uae30 \ub54c\ubb38\uc5d0 O(n^2)\uc73c\ub85c \ub3d9\uc77c<\/b>\ud558\ub2e4.<\/p>","category":["Computer Science\/Problem Solving","\ub124\ud2b8\uc6cc\ud06c","\ud504\ub85c\uadf8\ub798\uba38\uc2a4"],"author":"hojoo","guid":"https:\/\/bird-j.tistory.com\/92","comments":"https:\/\/bird-j.tistory.com\/92#entry92comment","pubDate":"Mon, 3 Nov 2025 22:33:23 +0900"}]}}