archives

994 https://leetcode.com/problems/rotting-oranges/ 쉬어가는 bfs 비슷한문제. class Solution(object): def orangesRotting(self, grid): visited = set() def bfs(rotten_index_list): queue = rotten_index_list while queue: pop = queue.pop(0) for m in [[-1, 0], [0, 1], [0, -1], [1, 0]]: popx, popy = pop[0] + m[0], pop[1] + m[1] if popx len(grid)-1 or \ popy > len(grid[0])-1 or (popx, pop..

75 https://leetcode.com/problems/sort-colors/ 정렬을 구현하는 문제이다. 라이브러리 함수를 쓰면 안 되고, 되도록 constant한 공간만 사용하고 in-place로 입력으로 주어진 배열 자체를 바꾸라고 한다. counting sort로도 해보라고 한다. class Solution(object): def sortColors(self, n): n0,n1,n2 = 0,0,0 for nn in n: if nn == 0: n0 += 1 elif nn == 1: n1 += 1 else: n2 += 1 n[:n0] = [0]*n0 n[n0:n0+n1] = [1]*n1 n[n0+n1:n0+n1+n2] = [2]*n2 discussion에 있는 흥미로운 구현 방법들을 더 적어본다. ..

978 https://leetcode.com/problems/longest-turbulent-subarray/ 이거 푸는데 한참걸렸다.. turbulent는 내부의 값들이 올라갔다 내려가는 것들의 부분집합이다. 이후에는 길이가 2 이상인 것들만을 처리하기 위해 일단 맨 앞에서 길이가 1인것들과 2인것들을 미리 처리해준다. 그리고 [100, 100, 100]은 길이가 3 이상임에도 답은 1이 나와야하니 이런것들도 걸러준다. 최소 len(set(arr))으로 뽑았을때 두개 이상이 나와야 turbulent가 만들어진다. [1, 0, 1, 0, 1]같이 두개로도 만들어질수 있다. 그러니 예외케이스를 걸러주고.. 계산을 해야하는데 복잡하게 앞이 > i+1 i+2로 조건을 걸어놓으..

198 https://leetcode.com/problems/house-robber/ n>=3일때 n의 최대값은 max(n-2번째집까지의 최대값 or n-3번째집까지의 최대값) + 현재집이다. 이렇게 만들고 풀어준다. class Solution(object): def rob(self, nums): if not nums: return 0 elif len(nums)

이걸 왜 정리를 안해놨었는지 모르겠다. http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220795165570 역시 이분 블로그에 깔끔하게 정리와 설명이 너무 잘되있어서 내가 보고 추가할부분이 없다. two pointer라는 이름 그대로 두개의 시작점을 잡아놓고 조건에 맞도록 두개의 포인터를 좁혀주면 된다고 기억해놓자.

338 https://leetcode.com/problems/counting-bits/ 비트의 갯수를 리턴하는 dp문제이다. 처음에 문제가 이해 안갔는데 예제의 2 -> [0,1,1]의 경우 0 0 1 -> 001 -> 1 2 -> 010 -> 13 -> 011 -> 2 4 -> 100 -> 15 -> 101 -> 26 -> 110 -> 27 -> 111 -> 32의 거듭제곱갯수를 주기로 f(n) = f(n-1) + (f(n-1)의 각각의 원소+1)가 성립된다. 4,5,6,7의 1,2,2,3의 경우 이전 주기 2,3-> (1,2) + ((1,2)의 각각의원소 + 1 == (2,3))인 1,2,2,3이 성립된다. 이걸 이용한다. class Solution(object): def countBits(self,..

67 https://leetcode.com/problems/add-binary/, 415 https://leetcode.com/problems/add-strings/ 1. 작은 자리의 수를 큰 자리의 수와 길이가 맞게 0으로 채워준다.2. 더하면서 carry가 생기면 다음에 추가해준다. 415는 아래 코드에서 10진수 개념으로만 보고 조금만 바꿔주면되어서 따로 안적는다 class Solution(object): def addBinary(self, a, b): if len(b) > len(a): a,b = b,a for i in xrange(len(a)-len(b)): b = '0' + b ret = '' carry = 0 for i in xrange(len(a)-1, -1, -1): s = carry +..

https://leetcode.com/problems/sum-of-two-integers/discuss/84278/A-summary%3A-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently 의 글을 정리함. 파이썬 버전. 1. 숫자를 이진수로 변경했을때 1의 갯수 세기. def count_one(n): count = 0 while n: n = n&(n-1) count += 1 return count print count_one(3) 2.1 어떤 수가 2의 거듭제곱인지 판단. 2의 거듭제곱들은 이진수로 아래와 같다.1, 10, 100, 1000, 10000 .... 그리고 이것들보다 1 작은수의 이진수는 아래와 같다.0, 01, 011..

565 https://leetcode.com/problems/array-nesting/ S는 A로 만들수 있는 서브배열개념이고.. S를 만드는 방법은 A[i] -> A[A[i]] -> A[A[A[i]]] 이런식으로 위치를 찾아가면서 만들수 있다. 이중 가장 긴 S를 구하는거다. i일때의 그룹을 만들면서 사용한 인덱스들을 set에 저장해둔다. 그리고 그룹이 끝나면 그룹의 길이로 정답을 대체하고 다음거로 넘어간다. class Solution: def arrayNesting(self, nums: List[int]) -> int: i = 0 used = set() ret = [] while i < len(nums): if nums[i] in used: # nums[i]가 이미 이전의 숫자의 그룹을 만들면서 사용..

62 https://leetcode.com/problems/unique-paths/ 기초적인 dp문제이다. 0행과 0열은 전부 경우의 가지수가 1이고, n행 m열 = n-1행 m열의 경우의수 + n행 m-1열의 경우의수이다. class Solution(object): def uniquePaths(self, m, n): dp = [[1 for j in xrange(m)] for i in xrange(n)] for i in xrange(1, n): for j in xrange(1, m): dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[n-1][m-1] 63 https://leetcode.com/problems/unique-paths-ii/submissions/ 위에랑 비슷한..

373 https://leetcode.com/problems/find-k-pairs-with-smallest-sums/ 단순히 O(n^2)으로 돌면서 힙에 넣은후 힙에서 k를 빼내는식으로 하면 메모리 초과가 난다. 메모리 초과를 피하기 위해 가장 가능성이 높은 인자들만 저장해두고 그중에 빼와서 답을 낸다. 모두 정렬된 상태이므로 첫번째로 가능한건 인덱스로 0,0이다.(nums1의 인덱스 0, nums2의 인덱스 0) 그리고 그다음으로 가능성 있는건 0,1이나 1,0일거다. 이런식으로 확장해나가면 되는데 항상 현재좌표의 (y,x+1), (y+1, x)처럼 확장하면서 이미 방문한 좌표인지 확인이 필요하다. from heapq import * class Solution: def kSmallestPairs(se..

141 https://leetcode.com/problems/linked-list-cycle/ https://qkqhxla1.tistory.com/1043에 이론을 정리해놨다. class Solution(object): def hasCycle(self, head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False 142 https://leetcode.com/problems/linked-list-cycle-ii/ linked list의 순환이 시작되는 첫번째 위치를 찾는 문제. 한번 만난 후에 fast는 놔두고, slow만 처음으로..

https://leetcode.com/problems/linked-list-cycle/ 문제로 설명함. 설명 : https://leetcode.com/problems/linked-list-cycle/discuss/44539/AC-Python-76ms-Floyd-loop-detection-in-7-lines 코드는 위에꺼 그대로 가져옴. def hasCycle(self, head): slow = fast = head while fast and fast.next: # fast는 두칸 뒤로 가고, slow는 한칸만 뒤로 감. # cycle이 없으면 while fast and fast.next에서 False가 나와서 루프가 끝날 것이고, # cycle이 있으면 fast가 속도가 더 빠르므로 slow를 결국에는 ..

48 https://leetcode.com/problems/rotate-image/ 이거 몰랐다.... 답을 보고나서야 이런 방법이 있는지 알았다. n x n의 행렬을 시계방향, 반시계로 돌리는 방법.https://leetcode.com/problems/rotate-image/discuss/18872/A-common-method-to-rotate-the-image class Solution(object): def rotate(self, matrix): n = len(matrix) for i in xrange(n/2): matrix[i],matrix[n-1-i] = matrix[n-1-i], matrix[i] for i in xrange(n): for j in xrange(i+1, n): matrix[i]..

https://leetcode.com/problems/rotate-image/discuss/18872/A-common-method-to-rotate-the-image 되게 일반적인 문제인데 여태까지 이걸 몰랐다...;코드를 그대로 가져온다. /* * clockwise rotate * first reverse up to down, then swap the symmetry * 1 2 3 7 8 9 7 4 1 * 4 5 6 => 4 5 6 => 8 5 2 * 7 8 9 1 2 3 9 6 3 */ /* matrix의 길이를 n이라고 하면 0행과 n-1행을 변경, 1행과 n-2행을 변경, 등등등 반복 후 반복으로 돌면서 스왑해준다.*/ void rotate(vector &matrix) { reverse(matri..

122 https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/ 오랫만에 보는 기초적인 그리디 문제이다. class Solution(object): def maxProfit(self, prices): if not prices: return 0 p = 0 for i in xrange(1, len(prices)): if prices[i] > prices[i-1]: p += prices[i] - prices[i-1] return p 121 https://leetcode.com/problems/best-time-to-buy-and-sell-stock/ O(n)으로 풀어야 시간초과가 안 걸린다. class Solution(object): def maxP..

283 https://leetcode.com/problems/move-zeroes/ 모든 0을 리스트의 끝부분으로 보내는 문제이다. easy인데 기발한 답이 많았다. 생각해보다 0이면 해당 원소를 pop하고.. 0을 끝에 넣는식으로 짰다. 근데 아래에는 기발한 답 리스트이다. 1. 0의 위치를 기록해두고, 0이 아닌 원소들이 나오면 0과 자리를 바꿔줌. https://leetcode.com/problems/move-zeroes/discuss/72012/Python-short-in-place-solution-with-comments. # in-place def moveZeroes(self, nums): zero = 0 # records the position of "0" for i in xrange(len..

206번. https://leetcode.com/problems/reverse-linked-list/ 노드, pre 노드 등을 따로 만들어서 처리하는게 더 복잡해서 이렇게 리스트에 넣고 리스트의 특성을 이용했다. class Solution(object): def reverseList(self, head): if not head: return None if not head.next: return head linked_list = [] while head: linked_list.append(head) head = head.next for i in xrange(len(linked_list)-1, 0, -1): linked_list[i].next = linked_list[i-1] linked_list[0].ne..

230번. https://leetcode.com/problems/kth-smallest-element-in-a-bst/submissions/ pre, in, post중 아무거나 순회한 다음에 원소들을 정렬후 k번째 작은 값을 리턴한다. class Solution(object): def kthSmallest(self, root, k): stack = [root] tree = [] while stack: node = stack.pop() tree.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return sorted(tree)[k-1] 22번. https://leetcode.com/pr..

1379번. https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/ 트리 순환 문제이다. 왜 굳이 original과 cloned을 따로 나눴는지 모르겠다. pre order던 post order던 순회하면서 해당 val이 있으면 return하도록 하면 문제는 풀린다. 아래는 일반적인 dfs식 트리순회. class Solution(object): def getTargetCopy(self, original, cloned, target): stack = [cloned] while stack: pop = stack.pop() if pop.val == target.val: return pop i..

http://www.secmem.org/blog/2019/03/09/rope/ Rope는 긴 문자열들에 대한 연산(자르기, 붙여넣기, 끼워넣기 등)을 효율적으로 처리하기 위해 고안된 자료구조입니다. 알아두면 유용할것 같아서 링크 저장해둠.

https://leetcode.com/problems/find-and-replace-pattern/ 이 문제는 사실 별거없다. 단어들을 패턴화시킨후 그 패턴에 맞는 단어를 찾는 문제이다. 난 별생각없이 패턴화시키는 로직이 딱히 안떠올라서 'cee'같은 문자의 경우 첫번째 나오는 c는 a로, 두번째 나오는 단어 e는 b로.. 이런식으로 패턴화를 했다. 코드를 짜긴 했지만 별로 만족스럽진 못했다. 별로 좋은 답은 아니니 일단 접어둠.class Solution(object): def findAndReplacePattern(self, words, pattern): """ :type words: List[str] :type pattern: str :rtype: List[str] """ pattern_dict = ..

https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/ inorder 로 탐색하는데 오른쪽 자식부터 탐색한다. class Solution(object): def bstToGst(self, root): """ :type root: TreeNode :rtype: TreeNode """ def inorder(node, val): if not node: return val node.val += inorder(node.right, val) return inorder(node.left, node.val) inorder(root, 0) return root https://leetcode.com/problems/insert-into-a-binary-..

음 여태까지 코드를 이해하지 못하고 짰었는데 이번에 leetcode의 bfs를 공부하다가 조금 깨달음을 얻었다. 나혼자서 코드를 짤수 있을것같다는 깨달음이라 그래야하나. 지금까지 백준에서 '정형화된' bfs문제만을 풀다보니, bfs문제는 대충 나름의 그런 특징이 있었다. 예를 들면 'n x n 크기의 맵에서, 상하좌우로 뻗어나가는 설정' 이런게 있으면 bfs소스코드를 찾아서 이리저리 기워맞추면 문제가 어느정도 풀렸고, 실제로 이런 문제가 많았다.(아니면 다른 문제도 있는데 내가 실력이 낮아서 몰랐거나, 못 깨달았거나이다.)bfs코드를 짤 때는, 일반적으로 아래와 같은 포맷을 따랐다. def bfs(x): visited = [0 for 0 in range(n)] q = [(x, 0)] while q: ~~..

https://leetcode.com/explore/learn/card/data-structure-tree/ 에서 푼 내용을 정리했습니다. 물론 go to dicuss가면 사람들이 솔루션을 다 써놨는데 몇몇 개념이나 방법론 등을 까먹지 않으려고 이 페이지에 정리해두려고 합니다. preorder, inorder, postorderdef preorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ ret = [] stack = [root] while stack: parent = stack.pop() if parent: ret.append(parent.val) stack.append(parent.right) stack.append(..

자세한 내용은 네이버 개발자 센터에 있다. : http://d2.naver.com/helloworld/711301 요약.유니크한 값이 어떤 자료구조 안에 있는지 정확하게 판단하려면 해쉬 셋 등을 만들어 모든 값을 넣어두고, 값을 가져와서 비교한 후 판단할수 있다. 하지만 이러한 방법은 메모리가 엄청 많이 먹게 된다.(모든 자료를 저장해야하므로) 정확한 값을 얻는데 드는 비용이 너무 크다면 비용을 월등하게 줄이는 대신 오차가 조금 있는 방법이 더 유용할 수도 있다. 이게 hyperloglog이다. 위 네이버 링크에 셰익스피어 작품에 나오는 유니크한 단어 수를 셀때, 자바의 hash set과 hyperloglog를 사용할때의 비교이다. (출처 위의 네이버 개발자 도구. 문제있을시 삭제하겠습니다.)hyperl..

백준 온라인 저지 파이썬 랭킹 2위. 이제 안풀거같은데 마지막으로 그냥 남겨두고 싶었다. 그리고 현재 99위. 60대까지 올라갔을때도있었는데 아직 1페이지일때 찍어둬야지... ㅎ

https://www.acmicpc.net/problem/13565 DFS나 BFS로 풀면 된다. 검색해서 가장 먼저 보이는 소스가 BFS여서 BFS로품 def bfs(y,x): visited = [[0 for j in xrange(n)] for i in xrange(m)] q = Queue.Queue() q.put([y,x]) visited[y][x] = 1 while not q.empty(): p = q.get() if p[0]==m-1: return True for i in xrange(3): ty,tx = p[0]+[1,0,0,-1][i],p[1]+[0,-1,1,0][i] if tyn-1: continue if visited[ty][tx]==0 and arr[ty][tx]==0: q.put([ty..

https://www.acmicpc.net/problem/1918 후위표기식으로 만들자. # -*- encoding: cp949 -*- s=raw_input() stack = [] answer = '' for c in s: if c.isalpha(): answer += c else: if len(stack)==0: stack.append(c) else: while stack: if stack[-1] in ['*','/'] and c not in ['(',')']: answer += stack.pop() elif stack[-1] in ['+','-'] and c in ['+','-']: answer += stack.pop() else: break if c!=')': stack.append(c) if c=..

https://www.acmicpc.net/problem/2805 이분 탐색으로 찾는다. n,m=map(int,raw_input().split()) tree = map(int,raw_input().split()) l,h = 0,1000000000 while l mid: s += tree[i]-mid if s >= m: l = mid else: h = mid if bl==l and bh==h: break print lhttps://www.acmicpc.net/problem/9184 괜찮은 문제 중 하나라고 생각한다. 재귀함수가 있을때 이것을 메모이제이션 하는 방법을 묻는 문제이다. ..