archives

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)

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 +..

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만 처음으로..

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]..

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..

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(..

백준 온라인 저지 파이썬 랭킹 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 괜찮은 문제 중 하나라고 생각한다. 재귀함수가 있을때 이것을 메모이제이션 하는 방법을 묻는 문제이다. ..

https://www.acmicpc.net/problem/1254 http://qkqhxla1.tistory.com/738의 10942번 문제의 dp테이블이 해당 범위에서 팰린드롬인지 판단하는 함수이다. 1. 팰린드롬인지 판단해놓는다. 끝에 x개의 문자를 덧붙이는것이므로 i~끝까지의 팰린드롬이 가장 긴 범위를 찾는다. i가 2라서 2~끝까지 팰린드롬이다. 그러면 앞의 0,1은 팰린드롬이 아니라는 소리이므로 0,1번 인덱스 문자 두개만 붙여주면 된다 즉 길이 + 2가 답이다 이경우엔. 이런식으로 품 # -*- encoding: utf-8 -*- s=raw_input() dp = [[0 for i in xrange(1002)] for j in xrange(1002)] for i in xrange(len(s)..

https://www.acmicpc.net/problem/2011 # -*- encoding: cp949 -*- import sys sys.setrecursionlimit(10000000) def password(index): if index =0 and 10 0: b = max(eat(1,w-1,ct), eat(1,w-1,ct+1)) temp += max(a,b) dp[p][w][ct] = max(dp[p][w][ct], temp) return dp[p][w][ct] t,w=map(int..

https://www.acmicpc.net/problem/1480 와 미친.. dp 왜이렇게 재밌는지 모르겠다 이 문제는 배낭 문제+비트마스크다. 가장 큰 문제는 가방이 여러개라는거다. 처음에는 가방 1에서 모을수있는만큼 최대한 보석을 모으고 그 목록을 따로 저장 후 다음 가방으로. 이런식이었는데 이렇게 하면 안된다. 각각의 최댓값이 전체 문제의 최댓값이 안 될수도 있기 때문이다. 따라서 모든 경우의 수를 조합해야된다. 보석 수나 가방 용량 등을 봤을때 수가 적어서 모든 수를 조합하고 적당히 메모이제이션 하면 잘 나올거라고 예측 가능하다. # -*- encoding: cp949 -*- import sys sys.setrecursionlimit(1000000) def getmax(m, capacity, j..

https://www.acmicpc.net/problem/2302 일단 문제를 어떻게 풀까 생각해보면 예시대로 4,7번이 고정좌석이라면 1~3번의 경우의수 * 5,6의 경우의수 * 8,9의 경우의수 가 답인걸 알수있다. 그럼 여기서 더 들어가서 1~3번의 경우의 수는 어떻게 구할수 있을까? 노가다 결과 피보나치수임을 깨달았다. 좌석이 1개일경우 경우의수는 1개, 2개는 2개, 3개는 3개, 4개는 5개, ..... 여기까지 생각하면 다 푼거다. # -*- encoding: cp949 -*- dp = [0 for i in xrange(41)] n=input() m=input() m_list=[input() for i in xrange(m)] dp[1] = 1 dp[2] = 2 for i in xrange(..

https://www.acmicpc.net/problem/10164 굳이 설명이 필요없음. # -*- encoding: cp949 -*- n,m,k=map(int,raw_input().split()) dp = [[0 for j in xrange(m)] for i in xrange(n)] dp[0][0] = 1 if k==0: k=n*m row = (k-1)/m col = (k-1)%m #print row,col for i in xrange(n): dp[i][0] = 1 for i in xrange(n): dp[i][col] = 1 for i in xrange(m): dp[0][i] = 1 for i in xrange(m): dp[row][i] = 1 for i in xrange(1,row+1): for ..

https://www.acmicpc.net/problem/1535 배낭 문제. 체력이 0이되면 죽은것이므로 초기 체력을 100이아닌 99로 설정해준다. # -*- encoding: cp949 -*- import sys sys.setrecursionlimit(1000000) def getmax(capacity, index): ret = 0 if index == n: return 0 unselected = getmax(capacity, index+1) selected = 0 if capacity >= weight[index]: selected = getmax(capacity-weight[index], index+1) + value[index] return max(unselected, selected) n=i..

https://www.acmicpc.net/problem/3878 1. n의 점 집합에 대해 볼록 껍질을 만든다.2. m의 점 집합에 대해 볼록 껍질을 만든다.3. 두 볼록 껍질이 교차하는지 검사한다. 교차하면 NO. 교차안하면 YES다.종만북에서 소스를 가져왔다. #include #include #include #include #include #include #include #include using namespace std; const double EPSILON = 1e-8; const double PI = 2.0 * acos(0.0); // 2차원 벡터를 표현한다 struct vector2 { double x, y; explicit vector2(double x_ = 0, double y_ = 0)..

https://www.acmicpc.net/problem/12781 종만북에서 소스를 가져왔다. 벡터로 선분이 평행한지 조사해서 평행하면 0, 아니면 4조각으로 자를 수 있다는 뜻이므로 1을 리턴했다. #include #include #include using namespace std; const double PI = 2.0 * acos(0.0); struct vector2 { double x, y; vector2(double x_ = 0, double y_ = 0) : x(x_), y(y_) {} // 두 벡터가 같은 경우 bool operator == (const vector2& rhs) const { return x == rhs.x && y == rhs.y; } // 벡터의 덧셈과 뺄셈, 단항 연산..

https://www.acmicpc.net/problem/9934 풀긴했는데 그닥 만족스럽지 못한 코드다. 이렇게 하는게 맞는건지... # -*- encoding: cp949 -*- import Queue def bfs(k): q = Queue.Queue() q.put([k,k/2]) while not q.empty(): p = q.get() temp = [] flag = False for e in p[:-1]: temp.append(e-p[-1]-1) temp.append(e+p[-1]+1) if e+p[-1]-1len(n)-1: flag = True print n[e], print if flag: return temp.append(p[-1]/2) q.put(temp) k=input() n = map(..