archives

https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems 정리. 위 문서는 아래에 적을 슬라이딩 윈도우 알고리즘 템플릿으로 여러가지 문자열 안의 문자열 문제들을 풀 수 있다는걸 알려줌. 파이썬으로 설명. https://leetcode.com/problems/minimum-window-substring/ 문제의 해답임. 기본적으로 two pointer 알고리즘에서 만든 템플릿이다. 문제는 S와 T가 있는데 S안에 T단어 전체가 들어가는 가장 작은 윈도우의 길이를 리턴하는 문제이다. class Solution(object)..

ssh를 사용해서 서버로 접속시 일반적으로 비밀번호를 요구한다. 근데 아래와 같은 과정을 거치면 비밀번호를 요구하지 않는다. 현재 내 컴퓨터, 서버 이렇게 총 두대가 있고 내 컴퓨터에서 서버로 들어가는 경우로 한다. 1. 서버의 키를 가져와서 ssh접속시 사용. pem파일을 생성, 받은 후 ssh -i ~~~.pem 계정@주소 2. 내 퍼블릭 키를 서버에 등록. 내 컴퓨터의 ~/.ssh/id_rsa.pub안의 값을 서버 컴퓨터 안의 ~/.ssh/authorized에 복붙해놓으면 ssh접속시 비밀번호를 묻지 않는다. 참고https://serverfault.com/questions/706336/how-to-get-a-pem-file-from-ssh-key-pair https://opentutorials.or..

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

배경 : 현재 access key와 secret key가 그냥 평문으로 박혀있습니다. 그런데 이게 보안적으로 위험해서 내가 필요한 권한을 가진 iam role을 가진 ec2에서 임시 credential을 가져와서 동작하도록 하고자 합니다. 대충 구성도를 그리면 이렇습니다. 1. 1번 ec2 즉 s3로 업로드할 수 있는 iam role을 가진 ec2를 생성합니다. 권한 가져오기 전용이므로 인스턴스는 가장 작은거로 적당하게 만듭니다. 2. 1번 ec2의 메타데이터를 가져와서 2번 ec2에서 사용해야 합니다. 1번 ec2에 인스턴스 메타데이터 서비스 구성을 해줘야 합니다. aws cli로 아래 구문을 실행해줍니다. instance-id는 1번 ec2의 instance-id로 설정합니다. 참고로 아래 aws콘솔..

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에 있는 흥미로운 구현 방법들을 더 적어본다. ..

데이터 직군 관련해서 기술 스택 등등 너무 깔끔하게 정리해주셔서 링크 걸어놓음. https://github.com/Team-Neighborhood/I-want-to-study-Data-Science/wiki/%EB%8D%B0%EC%9D%B4%ED%84%B0-%EB%B6%84%EC%95%BC%EC%9D%98-%EC%A7%81%EA%B5%B0-%EC%86%8C%EA%B0%9C 글 하나하나가 유용한게 많습니다. 취준생때는 데이터 직군에 관해서 정말 뭘 해야할지 검색해도 잘 안나오거나 말로만 뭐라뭐라 풀어쓴 글만 있는데 이런 구체적으로 기술 스택 등을 나열해놓은 블로그를 참조하면 좋을듯 싶네요. 실제 제가 하고 있는 업무나 기술스택이 거의 동일합니다.

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