Scribbling

class Solution: def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]: m, n = len(mat), len(mat[0]) starting_points = [(0, i) for i in range(n)] + [(i, 0) for i in range(1, m)] for starting_point in starting_points: array = [] y, x = starting_point while y

DFS로 쉽게 풀 수 있다. class Solution: def minReorder(self, n: int, connections: List[List[int]]) -> int: self.graph = [[] for _ in range(n)] self.connections_set = set() for u, v in connections: self.graph[u].append(v) self.graph[v].append(u) self.connections_set.add((u, v)) visited = [False] * n self.ret = 0 self.dfs(0, visited) return self.ret def dfs(self, node, visited): visited[node] = True for v..

데이터 분석 방법의 기초, 두번째 포스트 Kaggle 타이타닉 예제를 다룬다. https://www.kaggle.com/c/titanic 1. 데이터 살펴보기 아래 명령어로 pandas display 옵션을 설정 가능하다. pd.set_option("display.max_columns", 50) pd.set_option("display.max_rows", 50) 데이터 타입 train_df.dtypes 기초 통계량 train_df.describe() Null 확인 train_df.isnull().sum() 2. 개별 특성 분석하기 특성 갯수 세기 train_df['Cabin'].value_counts() all_df.Pclass.value_counts().plot.bar() 개별 특성과 목적 변수 관계 ..

이 포스트에서는 캐글 주택 가격 예측 예제를 풀어보며, 데이터 분석 방법의 기초를 다져보고자 한다. 캐글 주택 가격 예측 예제 링크 https://www.kaggle.com/c/house-prices-advanced-regression-techniques 1. 데이터 불러오기 및 데이터 살펴보기 필자는 구글 코랩을 사용하며, 구글 드라이브에서 데이터를 불러온다. from google.colab import drive drive.mount('/content/drive') 데이터 파일 종류 및 경로는 아래와 같다. data_dir = "/content/drive/MyDrive/Colab Notebooks/kaggle/house_prices/data/" submit_dir = "/content/drive/My..

직선 찾기 문제 핵심은... 1) 실수 처리를 회피하기 위한 slope의 처리 2) map의 활용 from collections import defaultdict import math class Solution: def maxPoints(self, points: List[List[int]]) -> int: ret = 1 for i in range(len(points)): p1 = points[i] lineDict = defaultdict(lambda: 1) for j in range(len(points)): if i == j: continue p2 = points[j] dx = p2[0] - p1[0] dy = p2[1] - p1[1] if dx == 0: slope = (0, 1) elif dy == ..

Recursion을 이용한 방법 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reorderList(self, head: Optional[ListNode]) -> None: """ Do not return anything, modify head in-place instead. """ cur = head count = 0 while cur != None: count += 1 cur = cur.next new_head, _ = self.helper(head, count) return ne..

class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> List[str]: self.wordDict = set(wordDict) self.ret = [] self.dfs(s, []) return self.ret def dfs(self, s, path): if not s: self.ret.append(' '.join(path)) return for word in self.wordDict: k = len(word) if s[:k] == word: self.dfs(s[k:], path+[word])

단어를 분해하거나 단어에서 단어를 찾는 문제를 다룰 때 가장 먼저 해볼만한 접근은, 분해 대상 단어를 한글짜 단위로 확인해가면서 완전탐색하는 것이다. 아래는 완전 탐색 코드이다. class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: self.wordDict = set(wordDict) return self.dfs(s) def dfs(self, s): if not s: return True for i in range(1, len(s)+1): if s[:i] in self.wordDict: if self.dfs(s[i:]): return True return False 제출해보면...? 타임 아웃이다. 생각해보면 dfs의 변수로 ..

O(N) Time, O(N) Memory """ # Definition for a Node. class Node: def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None): self.val = int(x) self.next = next self.random = random """ class Solution: def copyRandomList(self, head: 'Node') -> 'Node': if not head: return cur, dic = head, {} while cur: dic[cur] = Node(x=cur.val) cur = cur.next cur = head while cur: if cur.next: dic[cur]..

면접 형식의 문제여서 문제를 맞추는 것은 어렵지 않다. 다만 어느정도로 효율적인 알고리즘(시간 및 메모리 측면)을 구현하는지가 관건이다. 가장 간단한 방법은 모든 숫자를 저장하고, 중앙값 search시마다 정렬하는 방법이다. add: O(1) find: O(nlogn) 위의 이유로 비효율적이다. class MedianFinder: def __init__(self): self.arr = [] self.count = 0 def addNum(self, num: int) -> None: self.arr.append(num) self.count += 1 def findMedian(self) -> float: self.arr.sort() if self.count % 2 == 0: return (self.arr[se..