archives

1114 https://leetcode.com/problems/print-in-order/ 쓰레드 환경에서의 lock관련된 실행 순서를 구현하는 문제이다. 반드시 first, second, third순으로 실행되게 하려면 lock으로 잠궜다 풀었다를 잘 해야 한다. lock.acquire()을 했을 경우 lock.release()를 호출해서 그 락을 풀어주기 전까지는 재차 lock.acquire()을 호출할수 없는점을 이용한다. first에는 아무런 제한 없이 출력하고 풀어준다. second에는 first에서의 락을 acquire()함으로써 first에서 release()가 호출될때까지 기다려야함으로써 first -> second호출순서가 유지된다. third도 마찬가지이다. from threading ..

랜쳐 쿠버네티스에서 젠킨스 앱을 만들어서 젠킨스를 쓰고있다. 최근에 어떠한 이유로 젠킨스를 처음부터 새로 세팅해야 했다. 일반적인 메모리 설정이라던지.. 계정 설정이라던지 등의 일반적인 설정 말고 쿠버네티스와 관련된 설정을 적는다. 1. RBAC. 젠킨스에서 쿠버네티스의 자원에 접근이 필요할 경우 권한이 필요하다.(젠킨스가 쿠버네티스 안에서 설치된거지만 권한 필요.)예로 젠킨스 안에서 kubectl을 설치한 후에 kubectl을 사용해서 자원(pod이라던가.)을 가져오거나 service의 scale을 컨트롤 하는 코드가 있는 경우에 해당한다. 권한이 없는 경우 이런식으로 에러메시지가 뜬다. ----------------------------------------------------------------..

733 https://leetcode.com/problems/flood-fill/ bfs문제이다. from collections import deque class Solution(object): def floodFill(self, image, sr, sc, newColor): original_color = image[sr][sc] q = deque([[sr, sc]]) visited = set() while q: x,y = q.popleft() image[x][y] = newColor for _x, _y in [[-1, 0], [0, -1], [0, 1], [1, 0]]: next_x, next_y = x + _x, y + _y if (next_x, next_y) not in visited and 0

45 https://leetcode.com/problems/jump-game-ii/ 설명은 코드에 적는다. dp문제이다. class Solution: def jump(self, nums: List[int]) -> int: dp = [99999999]*len(nums) dp[0] = 0 # 인덱스 0에서 시작함. cur_max = 0 for i in range(len(nums)): if i+nums[i] > cur_max: # 현재 갈수 있는 최대거리 이상으로 갈수있을때만 루프를 돈다. cur_max = i+nums[i] # 현재 갈수 있는 최대거리 갱신 for j in range(i+1, min(i+1+nums[i], len(nums))): # 현 위치에서 갈수있는곳들의 값을 업데이트시켜줌. dp[j] ..

134 https://leetcode.com/problems/gas-station/ 일단 포인트를 잡으면 이동은 무조건 i에서 i+1로 가고 cost[i]만큼 든다. 충전할수 있는 gas보다 드는 비용인 cost가 더 많으면 돌아올수 없으므로 종료를 시켜주고 시작한다. 마을을 순회하면서 충전되는 양보다 드는 비용이 더 많을 경우 0 ~ 현재위치까지는 시작해봐야 -가 되어서 못 간다는 의미이니 시작점을 다음으로 초기화시켜준다. class Solution(object): def canCompleteCircuit(self, gas, cost): if sum(gas) < sum(cost): return -1 start, gas_left = 0, 0 for i in xrange(len(gas)): gas_left..

442 https://leetcode.com/problems/find-all-duplicates-in-an-array/ 이전에 https://qkqhxla1.tistory.com/1044 요글의 leetcode 287번에서 중복되는 숫자 1개를 찾는 문제를 링크드 리스트에 사이클이 있다고 생각하여 사이클의 시작점을 찾는거로 풀수 있었는데, 같은 조건의 중복되는 숫자가 2개 이상일 경우에는 cycle sort라는게 있다. class Solution: def findDuplicates(self, nums: List[int]) -> List[int]: self.cyclicSort(nums) output = [] for i in range(len(nums)): if nums[i] != i+1: output.ap..

https://youngmind.tistory.com/entry/CentOS-%EA%B0%95%EC%A2%8C-PART-1-8-%EC%8A%A4%ED%86%A0%EB%A6%AC%EC%A7%80-%EA%B4%80%EB%A6%AC-%E3%85%A3%E3%85%8D 의 사진을 가져옴.(문제있을시 글 비공개로 돌리겠습니다!) 일단 LVM에 관해 적는이유는 aws ec2에 새로 몽고디비를 설치하려고 하는데 환경에 문제가 있어서, aws에서 도커로 몽고를 띄울수가 없다. 그래서 온프레미스같이, idc에 설치하듯이 서버에 직접 설치를 해야하는데, 이 경우 완전 새로 만들어진 ec2는 말 그대로 우분투에 디스크를 새로 꼽은 상태이다. 그래서 이 디스크들을 어쩌구저쩌구 가공해주고 마운트해줘야 우리가 쓸수 있는 환경이 나..

1. '파일명'을 찾을때 find명령어를 많이 쓴다. find를 사용하면 경로를 입력한 파일 내에서 폴더가 있으면 재귀적으로 들어가면서 파일명들을 조건에 맞게 검색이 가능하다. ex) 모든 경로에서 na가 들어간 모든 파일 이름을 찾자 -> find / -name *na* 2>/dev/null 그러면 파일에 쓰여있는 내용들을 현재 파일 내에서 재귀적으로 들어가면서 검색을 하려면 어떻게 해야 할까??grep을 사용하면 현 경로에서 recursive하게 파일 내용들을 검색해볼수 있다. 맥 기준.https://apple.stackexchange.com/questions/275373/how-to-make-grep-work-like-in-ubuntu/275379 를 참조한다. grep -R '검색할 내용' 검색할..

647 https://leetcode.com/problems/palindromic-substrings/ 이전에 https://qkqhxla1.tistory.com/1059 에서 leetcode 5번 문제에 대한 풀이를 적었었는데 같은 문제다. class Solution: def countSubstrings(self, s: str) -> int: ret = 0 for i in range(len(s)): l,r = i, i while 0 int: dp = [[0]*(len(word2)+1) for i in range(len(word1)+1)] for i in range(len(word1)): for j in range(len(word2)): if word1[i] == word2[j]: dp[i+1][j+1]..

24 https://leetcode.com/problems/swap-nodes-in-pairs/ 가져와서 구현해준다. https://leetcode.com/problems/swap-nodes-in-pairs/discuss/œ/Python-or-Dummynode에 좋은 풀이가 있다. 내 답은 드러워서 안적음 class Solution: def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: dummy = p = ListNode(0) dummy.next = head while head and head.next: tmp = head.next head.next = tmp.next tmp.next = head p.next = tmp head = ..

208 https://leetcode.com/problems/implement-trie-prefix-tree/ https://qkqhxla1.tistory.com/1081?category=685988 에서 만든 코드를 갖다 쓴다. class Trie(object): def __init__(self): self.trie={} def insert(self, word): trie=self.trie for c in word: if c not in trie: trie[c]={} trie=trie[c] trie['#']='#' def search(self, word): stack = deque([[word, self.trie]]) while stack: word, trie = stack.pop() if not wo..

https://qkqhxla1.tistory.com/700 그림을 다시 가져옴.아주 예전에 정리했었는데 c++이고.. 좀 복잡해서 지나면 잊어버린다. 파이썬 딕셔너리로 쉽게 구현한 버전이 있어서 가져왔다. MyPrettyPrinter클래스는 디버깅용이니 무시하고 Trie클래스만 보자. 소스 출처 : https://leetcode.com/problems/add-and-search-word-data-structure-design/discuss/59700/Python-trie-solution-search-using-dfs 여기서 가져와서 보기좋게 가공했다. addWord로 단어가 추가되면 트라이를 구성하는데, 단어가 어떻게 구성되는지는 아래에 print MyPrettyPrinter().pformat(t.tri..

863 https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/ 1. 그래프 개념으로 어떤 한 노드에 연결된 모든 노드를 찾는다. 연결된 노드는 [부모, 왼쪽 자식, 오른쪽 자식]이다. 이것들을 node_list에 저장해놓는다. 2. 저장한 후에는 target을 시작점으로 [부모, 왼쪽 자식, 오른쪽 자식]을 돌면서 거리가 K인 노드들을 dfs로 탐색한다. from collections import deque class Solution(object): def distanceK(self, root, target, K): node_list = {} queue = deque([[root, None]]) # node, parent while queu..

97 https://leetcode.com/problems/interleaving-string/ dfs로 푼다. from collections import deque class Solution(object): def isInterleave(self, s1, s2, s3): s1_len, s2_len, s3_len = len(s1), len(s2), len(s3) if s1_len + s2_len != s3_len: return False stack = deque([[0, 0]]) visited = set() visited.add((0, 0)) while stack: p = stack.pop() if p[0] + p[1] == s3_len: return True if p[0] < s1_len and s1[..

79 https://leetcode.com/problems/word-search/ dfs로 푼다. from collections import deque class Solution(object): def exist(self, board, word): #board = [["A","B","C","E"], # ["S","F","E","S"], # ["A","D","E","E"]] #word = "ABCESEEEFS" #board = [["A","B","C","E"], # ["S","F","C","S"], # ["A","D","E","E"]] #word = "ABCB" queue = deque() row_len = len(board) col_len = len(board[0]) for i in xrange(row_..

224 https://leetcode.com/problems/basic-calculator/ 코드가 너무 더럽고 효율도 낮다.. ㅠㅠ 접어놓음.from collections import deque class Solution(object): def calculate(self, s): #s = "(5-(1+(5)))" stack = deque() len_s = len(s) i = 0 while i 1 and stack[-2] in ['-', '+'] and (stack[-1].isdigit() or (stack[-1][0] == '-' and stack[-1][1:].isdigit())): cur_int = int(stack.pop()) sign = stack.p..

953 https://leetcode.com/problems/verifying-an-alien-dictionary/ 시키는대로 구현한다. class Solution: def isAlienSorted(self, words: List[str], order: str) -> bool: d = {o: i for i, o in enumerate(order)} words = [[d[w] for w in word] for word in words] for i in range(max(len(w) for w in words)): check = [word[i] if len(word) > i else -1 for word in words] check = list(zip(check, check[1:])) if all(a < b..

139 https://leetcode.com/problems/word-break/ bfs로 풀었다. from collections import deque class Solution(object): def wordBreak(self, s, wordDict): #s = "catsanddog" #wordDict = ["cats", "dog", "sand", "and", "cat"] visited = set() wordDict = set(wordDict) queue = deque() for i in xrange(len(s)+1): if s[:i] in wordDict: visited.add(s[i:]) queue.append(s[i:]) #print 'queue =',queue while queue: p = q..

https://leetcode.com/problems/next-permutation/discuss/13867/C%2B%2B-from-Wikipedia 의 댓글에 아주 잘 설명되어있다. 정리함. next permutation을 구하는 방법. 2,3,6,5,4,1로 알고리즘의 예를 듬. 1. 오른쪽에서 왼쪽으로 순회하면서 수가 증가하지 않는 부분을 찾는다. 2,3,6,5,4,1에서는 3 이다. 2-1. 수가 증가하지 않는 부분이 없으면 이 뜻은 permutation의 맨 마지막이라는 뜻이다. 이경우 맨 마지막의 다음은 맨 처음이므로 그냥 순서를 거꾸로 해주면 된다. 예로 6,5,4,3,2,1의 경우인데, 이 경우 그냥 거꾸로 순서를 해주면 맨 처음인1,2,3,4,5,6이다. 2-2. 수가 증가하지 않는 부분..

263 https://leetcode.com/problems/ugly-number/ ugly한 숫자란 2,3,5로만 나눴을때 나누어 떨어지는 수이다. ugly한 숫자인지 체크하자. class Solution(object): def isUgly(self, num): if num == 0: return False for p in [2, 3, 5]: while True: if num%p == 0: # num이 2,3,5중 하나로 나누어지면 안 나눠질때까지 계속 나눔. num /= p continue break return num == 1 # 1이 나오면 ugly한 숫자, 아니면 ㄴㄴ 264 https://leetcode.com/problems/ugly-number-ii/ n번째 ugly number를 구하는 ..

773 https://leetcode.com/problems/sliding-puzzle/ bfs로 모델링해서 푼다. 어려운 버전. from collections import deque class Solution(object): def slidingPuzzle(self, board): def bfs(x, y, board): queue = deque([[x, y, board[:], 0]]) visited = set([''.join(map(str, board))]) while queue: _x, _y, board, count = queue.popleft() _str = ''.join(map(str, board)) if _str == '123450': return count for __x, __y in [[-1..

es에 데이터를 넣으려고 하는데 u'error': {u'reason': u'blocked by: [FORBIDDEN/12/index read-only / allow delete (api)];', u'type': u'cluster_block_exception'} 요런 메시지가 뜨면서 데이터가 es로 들어가지 않는다. 구글링해보니 https://dev-yeon.tistory.com/12 에서 디스크가 거의 차서 발생하는 에러라고 한다. 디스크가 찼으면.. 인덱스를 좀 지워주면 되겠네? 하고 지우려했더니 read only라고 에러가 뜬다.저 블로그에서 나온것처럼 read only모드를 풀어주자. PUT _all/_settings { "index": { "blocks": { "read_only_allow_del..

560 https://leetcode.com/problems/subarray-sum-equals-k/ 딕셔너리에 https://leetcode.com/problems/two-sum/ 문제를 풀때처럼 이전까지의 합을 저장해놓는다. 그리고 현재까지의 총합 - k가 딕셔너리에 있으면 이 값은 이전 어디선가 만들어질수 있다는 뜻이므로 그만큼 +를 해준다. 그게 아니면 해당 수가 만들어질 경우의 수를 딕셔너리에 저장해준다. class Solution(object): def subarraySum(self, nums, k): d = {} d[0] = 1 total = 0 ret = 0 for i in xrange(len(nums)): total += nums[i] if total - k in d: ret += d[t..

297 https://leetcode.com/problems/serialize-and-deserialize-binary-tree/449 https://leetcode.com/problems/serialize-and-deserialize-bst/ 똑같은 문제라서 같이 올림. 문자열로 인코딩하고 디코딩해주는 문제이다. from collections import deque class Codec: def serialize(self, root): if not root: return '' ret = deque() queue = deque([root]) while queue: p = queue.popleft() if not p: ret.append('null') continue ret.append(p.val) for..

33 https://leetcode.com/problems/search-in-rotated-sorted-array/ [4,5,6,7,0,1,2] 처럼 sorted된 리스트가 두개가 있다고 생각한다. 그리고 그중에 target을 log(n)의 시간복잡도로 찾아야 한다. log(n) 보자마자 이분 탐색을 떠올려야 하고, 그러면 저렇게 반이 섞여진곳에서 어떻게 이분탐색을 할까? 생각해보자. 난 먼저 값이 변하기 시작하는 부분의 인덱스를 찾았다. (위의 [4,5,6,7,0,1,2]의 경우엔 4) 그리고 target이 변하기 시작하는 부분 전의 안에 있는지 후에 있는지 검사후 low와 high를 정한다. [4,5,6,7,0,1,2]의 경우엔 [4,5,6,7]과 [0,1,2]로 나눠질수 있는데 각각의 리스트들을 정..

322 https://leetcode.com/problems/coin-change/ 문제를 읽어보니 이전에 풀었던 백준 2293번 https://qkqhxla1.tistory.com/683 과 비슷하다. 여기서 코드를 가져와서 변형했다. class Solution(object): def coinChange(self, coins, amount): dp = [999999 for i in xrange(amount+1)] dp[0] = 0 for i in xrange(len(coins)): #모든 동전을 돌아가면서 for j in xrange(1, amount+1): #1원~만들고자하는 k원까지 if j >= coins[i]: #현재 동전으로 j원을 만들수있으면 dp[j] = min(dp[j], dp[j-coi..

271 https://leetcode.com/problems/encode-and-decode-strings/ 인코딩, 디코딩 함수를 구현하는 문제이다. 근데 그냥 인코딩후 디코딩이 제대로 되기만 하면 되니까 아주 간편하다. 원래는 base64같은거로 인코딩하고, 디코딩했을것같은데 여기서는 간편하게 절대 안나타날것같은 구분자인 ' '로 나누고 합쳐주는거로 했다.. class Codec: def encode(self, strs): if strs == []: return None return ' '.join(strs) def decode(self, s): if s is None: return [] return s.split(' ') 696 https://leetcode.com/problems/count-bin..

146 https://leetcode.com/problems/lru-cache/ lru 캐시를 구현하는 문제이다. python 의 ordereddict은 딕셔너리지만 넣은 순서가 보장된다. 이걸 이용한다. 아래처럼 구현하면 모든 연산이 O(1)이다. pop과 popitem이 O(1)연산인가? 궁금해서 찾아봤더니 맞다고 한다. from collections import OrderedDict class LRUCache(object): def __init__(self, capacity): self.cache = OrderedDict() self.c = capacity self.cur_len = 0 def get(self, key): if key not in self.cache: return -1 v = sel..

https://qkqhxla1.tistory.com/1061 에 이론을 정리해두고 아래는 응용 방법들을 정리해둠. 76. https://leetcode.com/problems/minimum-window-substring/S와 T가 있고, T의 모든 문자가 S에 포함되는 S의 가장 짧은 부분문자열의 길이를 구하여라. class Solution(object): def minWindow(self, s, t): if len(t) > len(s): return '' result = [] _dict = {} for tt in t: _dict[tt] = _dict.get(tt, 0) + 1 counter = len(_dict) begin = end = head = 0 _len = 999999999 while end ..

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