본문 바로가기

개발/알고리즘

 (64)
[백준 / Python] 연구소_14502 틀렸던 내 풀이 from _collections import deque from copy import deepcopy n, m = map(int, input().split()) data = [list(map(int, input().split())) for _ in range(n)] dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] result = [] # 바이러스 퍼뜨리기 def bfs(deep_copy): map = deepcopy(deep_copy) q = deque() virus = find_virus(map) visited = [[False for _ in range(m)] for _ in range(n)] for i in virus: x, y = i q.append((x, y)..
[ 백준 / Python ] 피보나치의 수 DP를 사용하여 푼 풀이 def solved(num): dp = [0 for _ in range(46)] dp[0] = 0 dp[1] = 1 for i in range(2, num+1): dp[i] = dp[i-1] + dp[i-2] return dp[num] print(solved(int(input()))) 재귀로 풀기 위해 시도한 코드들 틀린 코드 - 시간 초과 def recursive(num): if num == 0: return 0 if num == 1: return 1 return recursive(num - 1) + recursive(num - 2) n = int(input()) print(recursive(n)) 시간 초과가 난 이유가 뭘까? 위 코드는 그림을 보면 알 수 있듯이, 같은 작업..
[알고리즘] 시간 복잡도 Big-O 시간 복잡도란? 입력데이터가 n개 있을 떄, 최악의 경우의 연산 횟수를 n의 함수로 나타낸 것. 왜 입력데이터가 n개일 때인가? 알고리즘 A, B가 있을 때 두 가지 상황을 가정하자. 1. 입력 데이터가 다른 상황 A는 3초가 소요되는 알고리즘이고, B는 7초가 소요되는 알고리즘이다. 하지만 그렇다고 A가 더 빠른 알고리즘이라고 할 수 없다. 두 알고리즘에 대한 입력 값이 서로 다를 수 있기 때문이다. 2. 입력 데이터가 같아도 상황에 따라 다를 수 있다. 예를 들어, 10개의 데이터에 한해서는 A가 B보다 빠를 수 있지만, 10000개의 데이터에 한해서는 B가 더 빠를 수 있다. 결론: 그렇기 때문에 입력 데이터가 n개 일때, 최악의 경우의 연산 횟수를 n의 함수로 나타낸 것이 시간 복잡도 Big-O로..
[ 삼성 기출 / Python ] 청소년 상어 처음 틀린 풀이 from copy import deepcopy dx = [(0, 0), (-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1)] shark = int(1e9) def solved(): fish_pos = [[0, 0] for _ in range(17)] data = [[[0, 0] for _ in range(4)] for _ in range(4)] for i in range(4): value = list(map(int, input().split())) cnt = 0 for j in range(0, 7, 2): fish_pos[value[j]][0], fish_pos[value[j]][1] = i, cnt data[i][c..
[백준 / Python] 음악프로그램_2623 제출 코드 from _collections import deque n, m = map(int, input().split()) data = [[] for _ in range(n + 1)] indegree = [0 for _ in range(n + 1)] flag = True for _ in range(m): pd_data = list(map(int, input().split())) for i in range(1, len(pd_data) - 1): data[pd_data[i]].append(pd_data[i + 1]) indegree[pd_data[i + 1]] += 1 result = [] def topology_sort(): q = deque() for i in range(1, n + 1): if ind..
[백준 / Python] 게임 개발_1516 정답 풀이 from _collections import deque n = int(input()) data = [[] for _ in range(n + 1)] indegree = [0 for _ in range(n + 1)] time = [0 for _ in range(n + 1)] for i in range(1, n + 1): detail_data = list(map(int, input().split())) detail_data = detail_data[:len(detail_data) - 1] time[i] = detail_data[0] for j in range(1, len(detail_data)): data[detail_data[j]].append(i) indegree[i] += 1 def topol..
[백준 / Python] 줄 세우기_2252 내 풀이 from _collections import deque n, m = map(int, input().split()) data = [[] for _ in range(n + 1)] indegree = [0 for _ in range(n + 1)] for _ in range(m): a, b = map(int, input().split()) data[a].append(b) indegree[b] += 1 def topology_sort(): q = deque() for i in range(1, n + 1): if indegree[i] == 0: q.append(i) result = [] while q: node = q.popleft() result.append(node) for i in data[node]..
[백준 / Python] 네트워크 연결_1922 내 풀이 n = int(input()) m = int(input()) parent = [i for i in range(n + 1)] def find(parent, x): if parent[x] != x: parent[x] = find(parent, parent[x]) return parent[x] def union(parent, a, b): a = find(parent, a) b = find(parent, b) if a b: parent[a] = b data = [] for _ in range(m): a, b, c = map(int, input().split()) data.append((c, a, b)) data.sort() def solved(): result = 0 for i in data: cost..

티스토리툴바