얄루의 개발일기🥑

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다. 😎문제 : https://leetcode.com/problems/combination-sum/submissions/ 숫자 집합 candidates를 조합하여 합이 target이 되는 원소를 나열하라 각 원소는 중복으로 나열 가능하다. class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: result = [] def DFS(csum, index, path): #목표값 초과한 경우 탐색 종료 if csum < 0: return if csum == 0: result.append(path) return for i ..

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다. 😎문제 : https://leetcode.com/problems/combinations/ 전체 수 n을 입력 받아 k개의 조합을 리턴하라 [DFS로 k개 조합 생성] class Solution: def combine(self, n: int, k: int) -> List[List[int]]: result = [] def DFS(elements, start:int, k:int): if k == 0: result.append(elements[:]) return #자신 이외의 모든 값을 고정하여 재귀 호출 for i in range(start, n+1): elements.append(i) DFS(elements, i+1, k -1)..

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다. 😎문제 : https://leetcode.com/problems/permutations/ 서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라 [DFS를 활용한 순열 생성] class Solution: def permute(self, nums: List[int]) -> List[List[int]]: result = [] prev_elements = [] def DFS(elements): #리프 노드일 때 결과 추가 if len(elements) == 0: result.append(prev_elements[:]) for e in elements: next_elements = elements[:] next_elements.re..

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다. 😎문제 : https://leetcode.com/problems/letter-combinations-of-a-phone-number/ 2에서 9까지 숫자가 주어졌을 때 전화 번호로 조합 가능한 모든 문자를 출력하라. class Solution: def letterCombinations(self, digits: str) -> List[str]: def dfs(index, path): if len(path) == len(digits): result.append(path) return for i in range(index, len(digits)): #해당 키를 가진(숫자의) 문자열을 모두 돈다. for j in dic[digits..

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다. 😎문제 : https://leetcode.com/problems/number-of-islands/submissions/ 1을 육지로, 0을 물로 가정한 2D 그리드 맵이 주어졌을 때, 섬의 개수를 계산하라(연결되어 있는 1의 덩어리 개수를 구하라) [DFS로 그래프 탐색] class Solution: def numIslands(self, grid: List[List[str]]) -> int: def dfs(i,j): if i = len(grid) or j = len(grid[0]) or grid[i][j] != '1': return grid[i][j] = '0' dfs(i+1, j) dfs..

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다. [비선형 자료구조란?] 순차적(Sequential)으로 또는 선형으로 배열되지 않는 자료구조를 비선형 자려구라고 한다. 비선형 자료구조는 선형과 달리 멀티 레벨로 구성된다. 이는 트리나 그래프(그래프의 범주에 있는 트리)를 떠올리면 쉽다. [그래프 순회] 그래프 순회란 그래프 탐색(Search)라고도 불리우며 그래프의 각 정점을 방문하는 과정을 이야기 한다. [그래프 순회의 종류] 깊이 우선 탐색(Breadth-First Search BFS) 주로 큐(Queue)를 사용해서 구현한다. 그래프의 최단 경로를 구하는 문제에서 사용한다. 너비 우선 탐색(Depth-First Search DFS) 대부분의 코딩테스트에서의 그래프 탐..

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다. 😎문제 : 상위 K번 이상 등장하는 요소를 추출하라 [Counter를 이용한 음수 순 추출] import collections import heapq class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: freqs = collections.Counter(nums) heap = [] for i in freqs: heapq.heappush(heap, (-freqs[i],i)) topk = list() for _ in range(k): topk.append(heapq.heappop(heap)[1]) return topk [파이썬 다운 방식] im..

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다. 😎문제 : https://leetcode.com/problems/longest-substring-without-repeating-characters/submissions/ 중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴하라 [슬라이딩 윈도우와 투 포인터로 사이즈 조절] class Solution: def lengthOfLongestSubstring(self, s: str) -> int: used ={} max_length = start = 0 for i, char in enumerate(s): #이미 등장한 문자라면 start 갱신 if char in used and start

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다. 😎문제 : https://leetcode.com/problems/jewels-and-stones/submissions/ J는 보석이며, S는 갖고 있는 돌이다. S에(돌에) 보석이 몇 개나 있을까? 대문자 소문자는 구분 한다. [보석과 돌] class Solution: def numJewelsInStones(self, jewels: str, stones: str) -> int: freqs = {} cnt = 0 for i in stones: if i not in freqs: freqs[i] = 1 else: freqs[i] += 1 #갯수 합산 for i in jewels: if i in freqs: cnt += freqs[..

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다. 😎문제 : https://leetcode.com/problems/design-hashmap/submissions/ 다음의 기능을 제공하는 해시맵을 디자인하라 [해시] 임의 크기의 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수를 해시라고 한다. 해시 테이블의 핵심은 해시 함수고 이때 해시 함수를 사용하는 것을 해싱이라고 한다. 파이썬의 경우 딕셔너리를 사용해서 해시 테이블을 구현한다. 파이썬은 해시 테이블 충돌 시 오픈 어드레싱을 사용해서 대처하고 이 이유는 malloc으로 메모리 할당하는 오버헤드가 높아 오픈 어드레싱을 택했다. (자바나 C++은 개별 체이닝 방식을 사용하여 해시테이블 충돌 시 대처한다.) [개별..