Scribbling

이와 유사한 문제를 이미 풀어보았다. * for문 안에서 삭제할때는 항상 주의하자. https://focalpoint.tistory.com/101 LeetCode: 126. Word Ladder II - 시바견의 끄적임 개인적으로 어려웠던 문제... A. 내가 푼 방법 일단 내가 푼 방법은 아래와 같다. 1) 모든 word에 대해 graph를 그린다. (word간 글자가 1개만 차이나는 경우 연결) 2) 다익스트라 알고리즘으로 최단 경 focalpoint.tistory.com from collections import deque def solution(begin, target, words): if target not in words: return 0 words = set(words) words.disca..

1. 입출력 시스템 1.1 입출력장치 컴퓨터는 CPU와 메인메모리, 주변장치인 입출력장치와 저장장치로 구성되며, 각 장치는 메인보드의 버스로 연결된다. 주변장치는 데이터 전송 속도에 따라 저속 주변장치와 고속 주변장치로 나뉜다. - 저속 주변 장치: 데이터 전송률이 낮은 장치로, 키보드나 마우스가 해당된다. - 고속 주변 장치: 대용량의 데이터가 오고가는 장치이다. 출력장치인 그래픽카드나 하드디스크가 해당된다. 1.2 입출력 버스의 구조 초기 컴퓨터는 모든 장치가 하나의 버스로 연결된 일괄작업 시스템으로, CPU가 작업을 진행하다가 입출력 또한 직접 수행하였다. 이를 폴링(Polling) 방식이라고 한다. 그러나 주변장치는 CPU나 메인메모리보다 매우 느리다. 그래서 폴링 방식처럼 CPU가 직접 입출력을..

그래프의 서로소 판별 문제이다. 아래 알고리즘을 그대로 사용한다. https://focalpoint.tistory.com/12 서로소 집합 알고리즘 v, e = map(int, input().split()) edges = [] for _ in range(e): edges.append(list(map(int, input().split()))) parent = [0] * (v+1) for i in range(v+1): parent[i] = i def find_parent(parent, a): if pa.. focalpoint.tistory.com def solution(n, computers): edges = [] for i in range(n): for j in range(i+1, n): if comput..

완전탐색이다. 어떻게 구현하냐가 핵심인데, 모든 숫자를 다 사용한다는 점을 이용하면, O(2**N)으로 풀 수 있다. answer = 0 def solution(numbers, target): global answer dfs(numbers, target) return answer def dfs(numbers, target): if not numbers: if target == 0: global answer answer += 1 return number = numbers[0] dfs(numbers[1:], target-number) dfs(numbers[1:], target+number)

Python Class 관련하여 잘 몰랐던 부분을 정리해둔다. 1. 비공개 속성 및 메서드 속성이나 메서드에 "__"를 붙이면 클래스 외부에서 접근할 수 없다. class person: def __init__(self, name, nickname): self.name = name self.__nickname = nickname def __tease(self): print(self.__nickname) 2. 클래스 속성 클래스 속성은 아래처럼 선언가능하며, 클래스명으로 접근하는 것이 가독성에 좋다. class Person: all_names = [] def __init__(self, name): Person.all_names.append(name) self.name = name 3. 정적 메서드 (Stat..

클로저는 간단히 말해 함수 안에 함수를 만드는 것이다. 클로저를 사용하는 이유는 크게 두가지이다. 1) 코드와 지역 변수를 묶어서 사용 가능하다. 2) 지역 변수를 숨기고 싶을 때 사용한다. 아래는 클로저의 예시이다. - 함수가 종료되어도 a, b 값이 유지되는 것을 확인할 수 있다. - nonlocal keyword를 이용하여 지역 변수의 변경이 가능하다. def line(a, b): total = 0 def get_value(x): nonlocal total total += a * x + b print('현재 누적 합: ' + str(total)) return a * x + b return get_value c = line(1, 2) print(c(1)) print(c(2)) print(c(3)) c..

1. 완전탐색 완전탐색으로 짜잔하고 풀리면 hard일리가 없지. 역시 Time Out class Solution: def numDistinct(self, s: str, t: str) -> int: self.answer = 0 self.dfs(s, t) return self.answer def dfs(self, s, t): if not t: self.answer += 1 return target = t[0] for i, char in enumerate(s): if char == target: self.dfs(s[i+1:], t[1:]) 2. DP 문자열을 탐색 혹은 비교하는 문제는 대부분 DP인 경우가 많다. 말그대로 dp다. 문제는 이것도 Time Out class Solution: def numDist..

DFS Solution # 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 pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]: if not root: return [] self.ret = [] self.dfs(root, [], 0, targetSum) return self.ret def dfs(self, node, path, tempSum, targ..

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next # 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 sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]: if not head:..

연이은 값을 선택할 수 없는 문제는 전형적인 DP 문제로 많이 접해보았을 것이다. 다만 이 문제는 첫 번째 값과 마지막 값을 동시에 선택할 수 없다는 조건이 추가되어있다. 이에 따라, 첫 번째 값을 선택가능한 case와 마지막 값을 선택 가능한 case로 나누어 그 중 최댓값을 return한다. 1) 0th idx ~ (n-1)th idx 2) 1th idx ~ (n)th idx def solution(money): dp1 = [0] * (len(money) - 1) dp1[0] = money[0] dp1[1] = max(money[0], money[1]) for i in range(2, len(money)-1): dp1[i] = max(dp1[i-2]+money[i], dp1[i-1]) dp2 = [0..