https://www.acmicpc.net/problem/2021 파이썬으로 아래와 같이 구현하였다. import sysfrom collections import dequeinput = sys.stdin.readlinen, l = map(int, input().split())station_visited = [0] * (n + 1) # 각 역의 깊이 저장 (환승 횟수)line_visited = [0] * (l + 1) # 해당 노선을 이용한 적 있나?subway = [list(map(int, input().split())) for _ in range(l)]graph = [[] for _ in range(n + 1)]for i in range(l): for j in subway[i]: if..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작www.acmicpc.net 파이썬으로 아래와 같이 작성했다. import syssys.setrecursionlimit(10**6)input=sys.stdin.readlinen, m = map(int, input().split())# 노드의 부모 노드를 저장하는 배열# 최초 각 노드의 부모는 자기 자신parent = [i for i in range(n+1)]# 각 노드의 랭크를 저장하는 배열..

https://www.acmicpc.net/problem/1753 1753번: 최단경로첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가www.acmicpc.net 파이썬으로 알고리즘 정리하기 위해 아래와 같이 작성했다.import sysimport heapqdef dijkstra(graph, start): n = len(graph) # 최초 거리를 무한으로 설정 dist = [float('inf')] * n # 시작점의 거리는 0 dist[start] = 0 # 시작점을 큐에 추가 he..

한쌍의 시작점, 끝점 목록과 이 목록에 추가할 한쌍의 시작점, 끝점이 주어질때,이를 직선 상에서 연속 될 경우, 하나로 묶는 방법이다. 예를 들어, (1, 5), (8, 10) 과 새로 추가할 점으로 (6, 7) 이 주어진다면,(1, 10) 으로 반환한다. 이를 표현하는 코드를 작성하면, 아래와 같다. from bisect import bisect_leftdef find_connected_lists(point_list, new_point): # 새로 들어온 순서 쌍을 배치할 위치를 찾는다. idx = bisect_left(point_list, new_point) l_merge = False r_merge = False # 앞쪽을 합쳐야 되면 l_merge 를 True 로..

백준 1012번: 유기농 배추 ( https://www.acmicpc.net/problem/1012 ) 파이썬으로 풀이하다가 깨달은 사실이다. 먼저 아래와 같이 구현해 보았다.def bfs(_x, _y): q = deque() q.append((_x, _y)) while q: vx, vy = q.popleft() arr_map[vx][vy] = 0 for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]: nx, ny = vx + dx, vy + dy if 0 BFS 를 구현하기 위해 1. 최초 방문지를 큐에 추가2. 큐에서 방문하지 않은 곳이 있다면, 큐에서 뺀다음 방문처리3. ..

얼마 전 회사에서 코드관련 글 중, 누군가, if a in dict_type.keys(): 블라블라블라~~~ 는 in 연산 시 선형적으로 탐색하므로 시간 복잡도가 O(n) 된다는 글을 보았다.파이썬 위키의 시간 복잡도 관련 글 ( https://wiki.python.org/moin/TimeComplexity )에서도 따로 Keys() 메서드에 관한 내용은 없었다. 정말 일까? 코드로 테스트해 보았다.\ import timeittest_dict = {x:x*2 for x in range(100000)}test_list = list(range(100000))print(type(test_dict.keys()))print(timeit.timeit(lambda: 999999 in test_dict.keys(..