Scribbling

LRU(Least Recently Used) 알고리즘은 캐시나 메인 메모리에서 '메모리 관리 알고리즘'으로 많이 사용된다. LRU 알고리즘에 대한 자세한 설명은 아래 링크를 참고하라. https://focalpoint.tistory.com/137 쉽게 배우는 운영체제 내용 정리 - Chapter 09 가상 메모리 관리 1. 요구 페이징 1.1 요구 페이징 프로세스가 필요로 하는 데이터를 언제 메모리로 가져올지 결정하는 것이 가져오기 정책이다. 일반적으로 프로세스가 요청할 때 메모리로 가져오는데, 일르 요구 focalpoint.tistory.com 간단히 말하자면, 메모리가 가득차면 가장 사용한지 오래 지난 부분을 버리는 것이다. 여기서 '사용'은 해당 부분에 접근하거나, 수정한 경우를 의미한다. 파이썬은..

고립된 O를 X로 만드는 문제이다. "고립된"은 board의 경계와 이어지지 않는 O들이다. 고로 경계의 O와 이어진 O들을 제외하고, 모두 X 처리해준다. from collections import deque class Solution: def solve(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ dy = [0, 1, 0, -1] dx = [1, 0, -1, 0] island = set() m, n = len(board), len(board[0]) for i in range(m): for j in range(n): if board[i][j] == "O": islan..

DFS로 푼다. # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def sumNumbers(self, root: Optional[TreeNode]) -> int: self.sum = 0 self.dfs(root, '0') return self.sum def dfs(self, node, num: str): if node.left == None and node.right == None: self.sum += int(num + str(nod..

정규 표현식 혹은 정규식은 문자열 매칭에 매우 유용하다. 정규 표현식에 대해 자세히 알고 싶다면 아래 링크를 참고하라. https://wikidocs.net/1642 07-1 정규 표현식 살펴보기 정규 표현식(Regular Expressions)은 복잡한 문자열을 처리할 때 사용하는 기법으로, 파이썬만의 고유 문법이 아니라 문자열을 처리하는 모든 곳에서 사용한다. 정 ... wikidocs.net https://dojang.io/mod/page/view.php?id=2435 파이썬 코딩 도장: 43.1 문자열 판단하기 Unit 43. 정규표현식 사용하기 정규표현식(regular expression)은 일정한 규칙(패턴)을 가진 문자열을 표현하는 방법입니다. 복잡한 문자열 속에서 특정한 규칙으로 된 문자열..

Decorator는 이미 만든 함수를 수정하지 않고, 함수 주변을 감싸는 방식으로 함수에 추가 기능을 구현한다. def trace(func): # wrapper는 아래처럼 가변 인수로 만들 수 있다. # 가변 인수가 아닌 경우, 원래 함수의 parameter 형태와 일치해야 한다. def wrapper(*args, **kwargs): ret = func(*args, **kwargs) print('{0}(args={1}, kwargs={2}) -> {3}'.format(func.__name__, args, kwargs, ret)) # 원래 함수가 return이 필요한 경우에는 wrapper도 return이 필요하다. return ret return wrapper @trace def get_max(*args..

1. Iterator __iter__, __next__를 가진 객체를 iterator protocol을 지원한다고 일컫는다. class Counter: def __init__(self, limit): self.num = 0 self.limit = limit def __iter__(self): return self def __next__(self): if self.num < self.limit: ret = self.num self.num += 1 return ret else: raise StopIteration for i in Counter(10): print(i, end=' ') 클래스에서 __getitem__ 메서드만 구현해도 이터레이터가 된다. class Counter: def __init__(sel..

2019 카카오 코딩 테스트 기출 문제라고 한다. 단순 구현문제다. from collections import defaultdict def solution(record): results = [] record_dict = defaultdict(list) nickname_dict = {} for rec in record: rec = rec.split(' ') if rec[0] == 'Enter': user_id, nickname = rec[1], rec[2] results.append(nickname + "님이 들어왔습니다.") record_dict[user_id].append(len(results) - 1) if user_id not in nickname_dict: nickname_dict[user_id]..

O(N) 알고리즘. class Solution: def longestConsecutive(self, nums: List[int]) -> int: longest = 0 nums = set(nums) for num in nums: if num - 1 not in nums: cnt = 1 while num + 1 in nums: num += 1 cnt += 1 longest = max(longest, cnt) return longest class Solution: def longestConsecutive(self, nums: List[int]) -> int: numSet = set(nums) longest = 0 while nums: cnt = 1 l = r = nums.pop() numSet.discard(..

난이도가 꽤 높은 그래프 문제이다. 방이 만들어지는 조건을 따져야 한다. * 방이 만들어지는 조건 - 재방문한 점이다. - 타고온 edge는 첫 방문이다. 여기까지는 생각하기 쉬운데, 문제는 아래와 같은 케이스다. 현재 알고리즘은 위의 그림에 대해 방을 1개로 파악한다. 이는 가운데 교차점을 정점으로 생각하지 않기 때문이다. 이 문제를 해결할 방법은 여러가지인데, 가장 간단한 방법은 하나의 화살표에 대해 이동을 2번 반복하는 것이다. def solution(arrows): answer = 0 dx = (0, 1, 1, 1, 0, -1, -1, -1) dy = (-1, -1, 0, 1, 1, 1, 0, -1) vertex = set() vertex.add((0, 0)) edge = set() cur = [..

아래 문제와 거의 같다. https://focalpoint.tistory.com/101 LeetCode: 126. Word Ladder II - 시바견의 끄적임 개인적으로 어려웠던 문제... A. 내가 푼 방법 일단 내가 푼 방법은 아래와 같다. 1) 모든 word에 대해 graph를 그린다. (word간 글자가 1개만 차이나는 경우 연결) 2) 다익스트라 알고리즘으로 최단 경 focalpoint.tistory.com class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: wordSet = set(wordList) wordSet.discard(beginWord) if endWord no..