본문 바로가기

Algorithm101

[LeetCode] 191 | Number of 1 Bits 191 | Number of 1 Bits https://leetcode.com/problems/number-of-1-bits/ 작성 코드 class Solution: def hammingWeight(self, n: int) -> int: return(bin(n).count("1")) bin 을 통해 n 을 문자열로 변환하여 "1" count bin(n) >>> 1011 bin() - 10진수 숫자를 이진수 문자열로 바꾸는 함수 bin(n) 을 통해 앞의 0은 절삭됨 이상 코드 class Solution: def hammingWeight(self, n: int) -> int: num_of_1s = 0 for _ in range(32): num_of_1s += (n & 1) n = n >> 1 return .. 2022. 3. 10.
[해시 테이블] 보석과 돌 771 | Jewels and Stones https://leetcode.com/problems/jewels-and-stones/ 작성 코드 문자열 class Solution: def numJewelsInStones(self, jewels: str, stones: str) -> int: answer = [stone for stone in stones if stone in jewels] return len(answer) Time: 31 ms (88.27%), Space: 14 MB (41.27%) stones for 문을 돌면서 jewels에 stone이 있는지 체크 문자열의 in 연산은 O(n)이므로 총 O(m*n) set 연산 이용 class Solution: def numJewelsInStones(s.. 2022. 3. 10.
[그래프] K 경유지 내 가장 저렴한 항공권 787 | Cheapest Flights Within K Stops https://leetcode.com/problems/cheapest-flights-within-k-stops/ 작성 코드 (30분 제한) class Solution: def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: graph = collections.defaultdict(list) for f, t, p in flights: graph[f].append((t, p)) Q = [(0, src, k)] dist = collections.defaultdict(int) answers = [] while Q: price,.. 2022. 3. 8.
[최단 경로 문제] 네트워크 딜레이 타임 743 | Network Delay Time https://leetcode.com/problems/network-delay-time/ 작성 코드 class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: def bfs(time, visited_net, next_net): visit = visited_net[-1] if not next_net[visit] or len(visited_net) == n: times.append(time - sum(times)) return for e, w in next_net[visit]: if e not in visited_net: next_net_temp = copy.d.. 2022. 3. 7.
파이썬 알고리즘 인터뷰 | 최단 경로 문제 다익스트라 알고리즘 pg. 372 항상 노드 주변의 최단 경로만을 택하는 대표적인 그리디 알고리즘 단순하면서 빠른 실행 속도 BFS를 이용하는 대표적인 알고리즘 2022. 3. 6.
[그래프] 코스 스케줄 207 | Course Schedule https://leetcode.com/problems/course-schedule/ 이상 코드 DFS로 순환 구조 판별 class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: graph = collections.defaultdict(list) # 그래프 구성 for x, y in prerequisites: graph[x].append(y) traced = set() def dfs(i): # 순환 구조이면 False if i in traced: return False traced.add(i) for y in graph[i]: if not dfs(y): re.. 2022. 3. 4.
반응형

티스토리툴바