문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다. 입력의 마지막 줄에는 0이 두 개 주어진다. 출력 각 테스트 케이스에 대해서, 섬의 개수를 출력한다..
문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다. 출력 첫째 줄부터 V개의 줄..
문제 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 출력 입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 ..
문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보..
문제 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라. 입력 : height = [0,1,0,2,1,0,1,3,2,1,2,1] 출력 : 6 입력 : height = [4,2,0,3,2,5] 출력 : 9 코드 from typing import List class Solution: def trapTwoPointer(self, height: List[int]) -> int: if not height: return 0 volume = 0 left, right = 0, len(height) - 1 left_max, right_max = height[left], height[right] while left < right: left_max, right_max = max(left_max, heig..
문제 당신은 전문털이범이다. 어느 집에서든 돈을 훔쳐올 수 있지만 경보 시스템 때문에 바로 옆집은 훔칠 수 없고 한 칸 이상 떨어진 집만 가능하다. 각 집에는 훔칠 수 있는 돈의 액수가 입력 값으로 표기되어 있다. 훔칠 수 있는 가장 큰 금액을 출력하라. 입력 : [1, 2, 3, 1] 출력: 4 설명 첫 번째 집에서 1, 세번째 집에서 3, 따라서 1 + 3 = 4 입력 : [2, 7, 9, 3, 1] 출력 : 12 설명 첫 번째 집에서 2, 세 번째 집에서 9, 다섯 번째 집에서 1, 따라서 2 + 9 + 1 = 12이다. 코드 """ fixme. https://leetcode.com/problems/house-robber/ fixme. Q88. 집도둑 fixme. 당신은 전문털이범이다. 어느 집에서..
0-1 배낭 문제 분할 가능 배낭 문제와 달리 짐을 쪼갤 수 없는 0-1 배낭 문제를 풀이해 보자. 이 문제는 '탐욕 선택 속성'이 있는 문제가 아니며 '중복된 하위 문제들' 속성을 갖고 있으므로 다이나믹 프로그래밍으로는 풀 수 있다. 단가 순으로 그리디하게 배치해서 풀이했던 분할 가능 배낭 문제와 달리, 0-1 배낭 문제는 짐을 쪼갤 수 없다. 이 경우 모든 경우의 수를 계산해야 한다. 먼저, 입력값으로 짐을 정의하고 zero_one_knapsack() 풀이 함수를 호출한다. cargo = [ (4, 12), (2, 1), (10, 4), (1, 1), (2, 2), ] print(zero_one_knapsack(cargo)) zero_one_knapsack() 함수는 다음과 같이 정의한다. def z..
문제 피보나치 수를 구하라. F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), for n > 1. 입력 : n = 2 출력 : 1 입력 : n = 3 출력 : 2 입력 : n = 4 출력 : 3 코드 """ fixme. https://leetcode.com/problems/fibonacci-number/ fixme. Q85. 피보나치 수 fixme. 피보나치 수를 구하라. fixme. 입력 : n = 2 fixme. 출력 : 1 """ import collections import numpy as np class Solution: def fib(self, N: int) -> int: if N int: if N int: self.dp[1] = 1 for i in range..
문제 숫자와 연산자를 입력 받아 가능한 모든 조합의 결과를 출력하라. 입력 : "2 - 1 - 1" 출력 : [0, 2] 설명 ((2 - 1) - 1) = 0 (2 - (1 - 1)) = 2 입력 : "2 * 3 - 4 * 5" 출력 : [-34, -14, -10, -10, 10] 설명 (2 * (3 - (4 * 5))) = -34 ((2 * 3) - (4 * 5)) = -14 ((2 * (3 - 4)) * 5) = -10 (2 * ((3 - 4) * 5)) = -10 (((2 * 3) - 4) * 5) = 10 코드 """ fixme. https://leetcode.com/problems/different-ways-to-add-parentheses/ fixme. Q84. 괄호를 삽입하는 여러 가지 방법..
문제 원형으로 경로가 연결된 주유소 목록이 있다. 각 주유소는 gas[i] 만큼의 기름을 갖고 있으며, 다음 주유소로 이동하는데 cost[i]가 필요하다. 기름이 부족하면 이동할 수 없다고 할 때 모든 주유소를 방문할 수 있는 출발점의 인덱스를 출력하라. 출발점이 존재하지 않을 경우 -1을 리턴하며, 출발점은 유일하다. 입력 : gas = [1,2,3,4,5], cost = [3,4,5,1,2] 출력 : 3 설명 3번 인덱스(기름을 4만큼 충전할 수 있는)에서 출발할 경우는 다음과 같다. 3번 → 4번 -1 fuel 3 4번 → 0번 -1 fuel 6 0번 → 1번 -1 fuel 4 1번 → 2번 -1 fuel 2 2번 → 3번 -1 fuel 0 정확하게 기름이 0까지 소모되며, 모든 주유소를 방문할 수..
문제 문자열 S와 T를 입력받아 O(n)에 T의 모든 문자가 포함된 S의 최소 윈도우를 찾아라. 입력 : S = "AD0BEC0DEBANC", T = "ABC" 출력 : "BANC" 코드 """ fixme. https://leetcode.com/problems/minimum-window-substring/ fixme. Q76. 부분 문자열이 포함된 최소 윈도우 fixme. 문자열 S와 T를 입력받아 O(n)에 T의 모든 문자가 포함된 S의 최소 윈도우를 찾아라. fixme. 입력 : S = "AD0BEC0DEBANC", T = "ABC" fixme. 출력 : "BANC" """ import collections class Solution: def minWindowPointer(self, s: str, t..
문제 단어 리스트에서 words[i] + words[j]가 펠린드롬이 되는 모든 인덱스 조합(i, j)를 구하라. 입력 ["abcd","dcba","lls","s","sssll"] 출력 [[0,1],[1,0],[3,2],[2,4]] ["dcbaabcd","abcddcba","slls","llssssll"]이 팰린드롬이다. 입력 ["bat","tab","cat"] 출력 [[0,1],[1,0]] ["battab","tabbat"]이 팰린드롬이다. 코드 import collections from typing import List # 트라이 저장용 노드. class TrieNode: def __init__(self): self.children = collections.defaultdict(TrieNode) se..
문제 트리의 전위, 중위 순회 결과를 입력값으로 받아 이진 트리를 구축하라. 전위 순회 결과: [3,9,20,15,7] 중위 순회 결과: [9,3,15,20,7] 결과는 밑의 그림과 같은 이진 트리가 된다. 코드 from typing import List class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: if inorder: # 전위 순회 결과는 중위 순회 분할 인덱스 index = ino..
문제 두 노드 간 값의 차이가 가장 작은 노드의 값의 차이를 출력하라. 입력 root = [4, 2, 6, 1, 3, null, null] 출력 1 노드 3과 노드 4의 값의 차이는 1이다. 입력 root = [10, 4, 15, 1, 8, null, null] 출력 2 이 경우 노드 간 값의 차이가 가장 작은 노드는 8과 10이다. 1과 4는 거리의 차이가 3이고, 4와 8은 차이가 4이지만 8과 10의 차이는 2로 최솟값이다. 코드 재귀 구조로 중위 순회 import sys class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solut..
문제 동일한 값을 지닌 가장 긴 경로를 찾아라. 입력 출력 2 입력 출력 2 코드 class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right class Solution: result: int = 0 def longestUnivaluePath(self, root: TreeNode): def dfs(node: TreeNode): if node is None: return 0 left = dfs(node.left) right = dfs(node.right) if node.left and node.left.val == node.val: left += 1 else: l..
문제 이진 트리에서 두 노드 간 가장 긴 경로의 길이를 출력하라. 다음과 같은 이진 트리가 주어졌을 때, 1 2 3 4 5 가장 긴 경로는 4 → 2 → 1 → 3 또는 5 → 2 → 1 → 3으로 3이다. 코드 class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: longest: int = 0 def diameterOfBinaryTree(self, root: TreeNode) -> int: def dfs(node: TreeNode) -> int: # 리프노드의 left, right 노드를 None으로 초기화하므로 거기까지..
트리 트리는 재귀로 정의된 자기 참조 자료구조이다. 쉽게 말하면, 트리는 자식도 트리고 또 그 자식도 트리다. 즉 여러 개의 트리가 쌓아 올려져 큰 트리가 된다. 흔히 서브트리로 구성된다고 표현한다. 트리의 각 명칭 트리는 항상 루트에서부터 시작된다. 루트는 자식 노드를 가지며, 간선으로 연결되어 있다. 자식 노드의 개수는 차수라고 하며, 크기는 자신을 포함한 모든 자식 노드의 개수다. 높이는 현재 위치에서부터 리프까지의 거리, 깊이는 루트에서부터 현재 노드까지의 거리다. 트리는 그 자식도 트리인 서브 트리 구성을 띈다. 레벨은 0에서부터 시작한다. 트리는 항상 단방향이기 때문에 간선의 화살표는 생략 가능하다. 일반적으로 간선의 방향은 위에서 아래로 향한다. 그래프 vs 트리 트리는 순환 구조를 갖지 않..
문제 K부터 출발해 모든 노드가 신호를 받을 수 있는 시간을 계산하라. 불가능할 경우 -1을 리턴한다. 입력값 (u, v, w)는 각각 출발지, 도착지, 소요시간으로 구성되며, 전체 노드의 개수는 N으로 입력받는다. 입력 times = [[2,1,1], [2,3,1], [3,4,1]], N = 4, K = 2 출력 2 코드 from typing import List import collections, heapq class Solution: def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int: graph = collections.defaultdict(list) for u, v, w in times: graph[u].append..
문제 입력 2, [[1,0]] 출력 True 입력 2, [[1,0],[0,1]] 출력 False 코드 visited 없을 때 from typing import List import collections class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: graph = collections.defaultdict(list) for x, y in prerequisites: graph[x].append(y) traced = set() def dfs(i): if i in traced: return False traced.add(i) for y in graph[i]: if not dfs(y): ret..
문제 [from, to]로 구성된 항공권 목록을 이용해 JFK에서 출발하는 여행 일정을 구성하라. 여러 일정이 있는 경우 사전 어휘순으로 방문한다. 입력 [["MUC", "LHR"], ["JFK", "MUC"], ["SF0", "SJC"], ["LHR", "SF0"]] 출력 ["JFK", "MUC", "SF0", "SJC"] 입력 [["JFK", "SF0"], ["JFK", "ATL"], ["SF0", "ATL"], ["ATL", "JFK"], ["ATL", "SF0"]] 출력 ["JFK", "ATL", "JFK", "SF0", "ATL", "SF0"] 코드 DFS from typing import List import collections class Solution: def findItinerary(s..
문제 서로 다른 정수를 입력 받아 가능한 모든 순열을 리턴하라. 입력 [1,2,3] 출력 [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 코드 재귀 함수 from typing import List class Solution: def permute(self, nums: List[int]) -> List[List[int]]: results = [] prev_elements = [] def dfs(elements): if len(elements) == 0: results.append(prev_elements[:]) for e in elements: next_elements = elements[:] next_elements.remove(e) prev_elem..
문제 전체의 수 n을 입력받아 k개의 조합을 리턴하라. 입력 : n = 4, k = 2 출력 [ [1,2], [1,3], [1,4], [2,3], [2,4], [3,4] ] 코드 dfs from typing import List class Solution: def combine(self, n: int, k: int) -> List[List[int]]: results = [] def dfs(elements, start: int, k:int): if k == 0: results.append(elements[:]) for i in range(start, n+1): elements.append(i) dfs(elements, i+1, k-1) elements.pop() dfs([], 1, k) return res..
객체 복사 파이썬의 중요한 특징 중 하나는 모든 것이 객체라는 점이다. 심지어 숫자, 문자까지도 모두 객체다. 숫자, 문자가 리스트, 딕셔너리 같은 객체와의 차이점이라면 불변 객체라는 차이뿐이다. 그러다 보니 별도로 값을 복사하지 않는 한, 변수에 값을 할당하는 모든 행위는 값 객체에 대한 참조가 된다. 이 말은 참조가 가리키는 원래의 값을 변경하면 모든 참조, 즉 모든 변수의 값 또한 함께 변경된다는 말이기도 하다. 그렇다면 참조가 되지 않도록 값 자체를 복사하려면 어떻게 해야 할까? 가장 간단한 방법은 [:]로 처리하는 방법이다. >>> a = [1,2,3] >>> b = a >>> c = a[:] >>> id(a), id(b), id(c) (4362781552, 4362781552, 43615800..
전화 번호 문자 조합 문제 2에서 9까지 숫자가 주어졌을 때 전화 번호로 조합 가능한 모든 문자를 출력하라. 입력 : "23" 출력 : ["ad","ae","af","bd","be","bf","cd","ce","cf"] 코드 from typing import List class Solution: def letterCombinations(self, digits: str) -> List[str]: def dfs(index, path): if len(path) == len(digits): result.append(path) return for i in range(index, len(digits)): for j in dic[digits[i]]: dfs(i + 1, path + j) if not digits: r..
중첩함수 중첩 함수(Nested Function)란 함수 내에 위치한 또 다른 함수로, 바깥에 위치한 함수들과 달리 부모 함수의 변수를 자유롭게 읽을 수 있다는 장점이 있다. 중첩 함수가 부모 함수의 변수를 공유하는 예제는 다음과 같다. def outer_function(t: str): test: str = t def inner_function(): print(text) inner_function( outer_function("Hello!') ----- Hello! 여기서 outer_function()은 inner_functuion()을 호출했고, 아무런 파라미터도 남기지 않았지만 부모 함수의 text 변수를 자유롭게 읽어들여 그 값인 Hello!를 출력했다. 이처럼 매번 파라미터를 전달하지 않아..
지금으로부터 300여 년 전 프로이센 공국의 쾨니히스베르크에는 프레겔 강이 흐르고 있었다. 프레겔 강에는 2개의 큰 섬이 있었고, 섬과 도시를 연결하는 7개의 다리가 놓여 있었다. 어느날 도시의 시민 한 명이 "이 7개 다리를 한 번씩만 건너서 모두 지나갈 수 있을까?"라는 흥미로운 문제를 냈다. 그러나 쉽게 풀릴 것처럼 보였던 이 문제를 풀 수 있는 이는 아무도 없었다. '수학의 모차르트'라 불리는 레온하르트 오일러가 '쾨니히스베르크의 다리 문제'를 조사하기 시작했다. 오일러는 이 문제가 도형 문제처럼 보이지만, 당시까지 알려진 기하학으로는 풀 수 없음을 알았다. 그리고 미지의 영역에 그 해법이 있다는 사실을 처재적인 직관으로 간파했다. 이것이 바로 '그래프 이론&#..
파이썬에서 언팩킹과 팩킹 zip()의 파라미터는 1개가 될 수도 있고, 2개가 될 수도, 10개가 될 수도 있다. 밑의 실험을 보면 알 수 있다. >>> a = ['a1', 'a2'] >>> b = ['b1', 'b2'] >>> c = ['c1', 'c2'] >>> d = ['d1', 'd2'] >>> list(zip(a)) [('a1',), ('a2',)] >>>list(zip(a, b)) [('a1', 'b1'), ('a2', 'b2')] >>> list(zip(a, b, c)) [('a1', 'b1', 'c1'), ('a2', 'b2', 'c2')] 여기에는 아스테리스크(Asterisk) 혹은 흔히 별표라고 부르는 *를 활용한다. 파이썬에서 *는 언팩(Unpack)이다. 시퀀스 언패킹 연산자(Seq..
해시란? 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말한다. 충돌 아무리 좋은 해시 함수라도 밑의 그림과 같이 충돌은 발생하게 된다. 이 그림에서 윤아와 서현은 해시 값이 2로 같은 값이 되어 충돌이 발생했다. 이처럼 충돌이 발생할 경우 어떤 식으로 처리하게 되는지 살펴보자. 개별 체이닝 입력 값을 밑의 표와 같이 정해보자. 해시는 키를 해싱한 결과며, '윤아'와 '서현'을 해싱한 결과는 충돌한다고 가정한다. 이 표를 개별 체이닝(Separate Chaining) 방식으로 구현하면 밑의 그림과 같다. 해시 테이블의 기본 방식이기도 한 개별 체이닝은 충돌 발생 시 이 그림과 같이 연결 리스트로 연결하는 방식이다. 충돌이 발생한 '..
k개 정렬 리스트 병합 문제 k개의 정렬된 리스트를 1개의 정렬 리스트로 병합하라 입력 [1 → 4 → 5, 1 → 3 → 4, 2 → 6] 출력 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6 코드 from typing import List import heapq class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: root = result = ListNode(None) heap = [] for i in range(len(lists)): if lists[i]: heapq.heappush(heap, ..
내부 함수 명명 규칙 내부에서 사용한다는 의미로 PEP8 명명 규칙 기준에 따라 밑줄(_) 하나로 시작하도록 메소드 명을 정한다. class MycircularDeque: """ skip.... """ def _add(self, node: ListNode, new: ListNode): n = node.right node.right = new new.left, new.right = node, n n.left = new def insertFront(self, value: int) -> bool: if self.len == self.k: return False self.len += 1 self._add(self.head, ListNode(value)) return True 출처 파이썬 알고리즘 인터뷰 (글 :..