관찰과 질문, 그리고 데이터

https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 | 프로그래머스 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 주어진 노드를 토대로 n * n Matrix를 생성할 경우 시간초과가 걸리는 문제. BFS 코드의 효율성보다는 주어진 노드 데이터를 적은 연산비용이 들어가도록 하는 게 관건이었던... 시간초과가 뜨던 코드는 아래와 같았다. from collections import deque, defaultdict def bfs(start, maps, visited): queue = deque() queue.append((start..

https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 www.acmicpc.net 삼성 SW역량테스트 기출문제였다고 한다. BFS와 DFS를 모두 사용하는 문제라고 하는데, Python에서는 '경우의 수'를 뽑아내..

https://programmers.co.kr/learn/courses/30/lessons/17676 코딩테스트 연습 - [1차] 추석 트래픽 | 프로그래머스 입력: [ 2016-09-15 20:59:57.421 0.351s, 2016-09-15 20:59:58.233 1.181s, 2016-09-15 20:59:58.299 0.8s, 2016-09-15 20:59:58.688 1.041s, 2016-09-15 20:59:59.591 1.412s, 2016-09-15 21:00:00.464 1.466s, 2016-09-15 21:00:00.741 1.581s, 2016-09-15 21:00:00.748 2.31 programmers.co.kr datetime 라이브러리를 써본 적은 없어서 찾아보면서 작업..

1. A팀의 최댓값이 B팀의 최댓값보다 크다 = B가 무엇을 내놓아도 이길 수 없다. 포기한다. 2. A팀의 최댓값보다 B팀의 최댓값이 크다 = 이길 수 있다. A팀을 최댓값 -> 최솟값 순서로 정렬하고, B의 최댓값을 빠르게 구할 수 있도록 heapq 라이브러리를 사용한다. import heapq def solution(A, B): # A의 최솟값이 B의 최댓값보다 크면, 이길 방법이 없으므로 0 if min(A) > max(B): return 0 # 최댓값 -> 최솟값 순으로 정렬 A.sort(reverse = True) # 맨 앞에 B의 최댓값이 위치하도록 heapq 자료구조를 사용한다. B = [-i for i in B] heapq.heapify(B) count = 0 for a in A: # 이..

위상 정렬 문제. Python의 heapq 라이브러리를 활용해서 위상정렬을 구현할 수 있다. import heapq n, m = map(int, input().split()) arr = [[] for _ in range(n+1)] precede = [0 for _ in range(n+1)] heap, result = [], [] for _ in range(m): x, y = map(int, input().split()) arr[x].append(y) # 연결된 간선. x번 문제는 y번보다 먼저 풀어야 한다. precede[y] += 1 # 이어진 노드의 진입차수. # (y번 문제는 몇 개의 선행문제와 연결되어 있는지. 진입차수라 보면 된다) for i in range(1, n+1): if precede[..