본문 바로가기

Algorithm48

[List] append VS. extend s = list(range(3)) s.append(10) print(s) s = list(range(3)) s.append([10]) print(s) s = list(range(3)) s.extend([10]) print(s) output [0, 1, 2, 10] [0, 1, 2, [10]] [0, 1, 2, 10] 2021. 4. 19.
[Bit Operation] 비트연산 NOT 연산은 각 자릿수의 값을 반대로 바꾸는 연산이다. NOT 0111 = 1000 OR 연산은 두 값의 각 자릿수를 비교해, 둘 중 하나라도 1이 있다면 1을, 아니면 0을 계산한다. 0101 OR 0011 = 0111 XOR 연산은 두 값의 각 자릿수를 비교해, 값이 같으면 0, 다르면 1을 계산한다. 0101 XOR 0011 = 0110 AND 연산은 두 값의 각 자릿수를 비교해, 두 값 모두에 1이 있을 때에만 1을, 나머지 경우에는 0을 계산한다. 0101 AND 0011 = 0001 XOR 연산을 많이 봤는데 XOR 연산이 0으로만 된 bit를 return 한다면 같은 숫자(?)라는 것을 의미하고 아니라면 다르다는 것을 알 수 있다. [LeetCode] Find the Difference 문.. 2021. 4. 14.
[프로그래머스] 여행경로 파이썬(DFS) from collections import defaultdict def solution(tickets): # 특정 티켓의 인접 리스트를 구하는 함수 def init_graph(): routes = defaultdict(list) for key, value in tickets: routes[key].append(value) return routes # 스택을 사용한 DFS def dfs(): stack = ["ICN"] path = [] # 가려고하는 경로를 저장하는 변수 while len(stack) > 0: # stack이 비어있을 때까지 top = stack[-1] # 특정 공항에서 출발하는 표가 없다면 또는 있지만 티켓을 다 써버린 경우 if top not in routes or len(routes.. 2021. 3. 17.
[프로그래머스] 네트워크 파이썬 (BFS) from collections import deque def solution(n, computers): answer = 0 bfs = deque() visited = [0]*n while 0 in visited:# visited 리스트의 모든 값에 방문 표시가 되어있을 때까지 반복 bfs.append(0) visited[0] = 1 while bfs: node = bfs.popleft() for i in range(n): if visited[i] == 0 and computers[node][i] == 1: bfs.append(i) visited[i] = 1 answer += 1# 한 네트워크의 탐색을 마치면 개수 추가 return answer 출처: cocojelly.github.io/algorithm/.. 2021. 3. 17.
[프로그래머스] 단어 변환 파이썬 (BFS/DFS) 고급 from collections import deque as queue transistable = lambda a,b: sum((1 if x!=y else 0) for x,y in zip(a,b)) == 1 def solution(begin,target,words): q, d = queue(), dict() q.append((begin, 0)) d[begin] = set(filter(lambda x:transistable(x,begin), words)) for w in words: d[w] = set(filter(lambda x:transistable(x,w), words)) while q: cur, level = q.popleft() if level > len(words): return 0 for .. 2021. 3. 17.
[프로그래머스] 2 x n 타일 파이썬 (DP) def solution(n): dp = [0]*(n+1) dp[1] = 1 dp[2] = 2 for i in range(3, n+1): dp[i] = (dp[i-1] + dp[i-2])% 1000000007 return dp[n] def solution(n): dp = [0]*(n+1) dp[1] = 1 dp[2] = 2 for i in range(3, n+1): dp[i] = (dp[i-1] + dp[i-2])% 1000000007 return dp[n] 출처: it-garden.tistory.com/410 2021. 3. 16.
[프로그래머스] 예상 대진표 파이썬 (DP) def solution(n,a,b): answer = 0 while a != b: answer += 1 a, b = (a+1)//2, (b+1)//2 return answer 2021. 3. 16.
[프로그래머스] 짝지어 제거하기 파이썬 (stack, pop) 다른 사람의 풀이 def solution(s): stack = [] stack.append(s[0]) for i in s: if len(stack) == 0: # 최초에 stack이 비었더라도 loop진행중 stack이 비워지면 다시 채워넣기 stack.append(i) elif stack[-1] == i: stack.pop() else: stack.append(i) if len(stack) == 0: return 1 pair 로 하는 문제는 괄호같은 경우도 그렇고 stack으로 pop [프로그래머스] 올바른 괄호 파이썬 ygseo.tistory.com/163 2021. 3. 16.
[프로그래머스] N개의 최소공배수 파이썬 from math import gcd def lcm(x,y): return x*y // gcd(x,y) def solution(arr): while True: arr.append(lcm(arr.pop(), arr.pop())) if len(arr) == 1: return arr[0] 최대공약수, 최소공배수를 활용해서 N개의 최소공배수를 구한다. list에서 2개의 원소를 꺼내 최대공약수를 구한뒤 다시 list에 삽입 출처: brownbears.tistory.com/454 2021. 3. 16.

티스토리툴바