전체 카테고리

[Algorithm] 0-1 BFS

0-1 BFS : 가중치가 0과 1만 있는 그래프에서 작동하는 알고리즘 0-1 bfs는 시간 복잡도 O(V+ E)로 다익스트라 알고리즘의 O(ElogE) 또는 O(VlogV) 보다 빠릅니다. 가중치가 0인 정점이 존재하기 때문에 정점의 방문 횟수가 더 많더라도 가중치가 더 낮은 경우를 고려해야 합니다. 결괏값이 방문 횟수가 아니라 가중치의 최소를 구하는 문제에서는 가중치가 낮은 경로부터 찾아야 합니다. 정점 1에서 2로 이동 = 방문 횟수 1, 가중치 1 정점 1에서 3, 4를 거쳐 2로 이동 = 방문 횟수 4, 가중치 0 탐색을 할때 가중치가 낮은 노드를 먼저 돌아야 하므로 가중치가 낮은 노드는 큐의 앞(front)에 삽입합니다. 파이썬의 우선순위 큐에서는 리스트의 앞에 삽입하는 기능이 없으므로 deq..

[백준] 11724: 연결 요소의 개수

11724번: 연결 요소의 개수 import sysn, m = map(int, input().split())graph = [ [] for _ in range(n+1) ]for _ in range(m): a, b = map(int, sys.stdin.readline().split()) graph[a].append(b) graph[b].append(a)cnt = 0visit = [False] * (n+1)def dfs(v): visit[v] = True for i in graph[v]: if not visit[i]: dfs(i)for i in range(1, n+1): if not visit[i]: dfs(i) cnt ..

[Python] 파이썬 max, min 함수 - max(map(max, graph))

파이썬 기본내장 함수에는 max함수와 min함수가 있습니다.  이번 포스팅에서는 사용법에 대해 알아보도록 하겠습니다.  기본적으로 max(리스트 or 튜플 or 요소), min(리스트 or 튜플 or 요소) 형태로 사용합니다.  number = [ 2, 5, 1, -19, 100, 200, -99 ]print(max(number))print(min(number))  결과)200-99  print(max(-10, 100))print(min(2, 9))  결과)1002  map 함수와의 응용 - 2차원 배열number = [ [ 2, 5, 1, -19, 100, 200, -99 ], [ 4, 2, 1, -20, 300, 150, 400 ], [ -1, -2, -10, -1..

[Python] 파이썬 ord함수, chr함수 차이점

1. ord() 함수 하나의 "문자"를 인자로 받고 해당 문자에 해당하는 유니코드를 반환하는 함수입니다. 알파벳 소문자 'a'~'z'는 97~122를 유니코드로 가집니다. print(ord('a')) print(ord('z')) 결과) 97 122 print(type(ord('a'))) 결과) ord 함수로 변환된 정수는 타입으로 int형을 가지게 됩니다. print(ord('ㄱ')) print(ord('ㅎ')) 결과) 12593 12622 ord() 함수는 아스키코드를 확장한 유니코드를 지원하므로 한글도 지원합니다. 2. chr() 함수 하나의 '정수'를 인자로 받고 그에 맞는 유니코드 문자를 반환합니다. 범위는 10진번과 16진법 입니다. print(chr(97)) print(chr(122)) pri..

[Python] Counter 모듈 사용법

데이터의 개수를 셀때 사용하는 Counter 모듈에 대해 알아보도록 하겠습니다. Counter 모듈은 collections에 있어서 다음 코드를 입력해야 합니다. from collections import Counter Counter 모듈은 dict()의 기능을 그대로 구현해 줍니다. hash처럼이요. 데이터의 개수를 세어 dict()처럼 key와 value로 구분해 주는 most_common() 함수가 있습니다. from collections import Counter print(Counter('SamSung').most_common()) 결과) [('S', 1), ('a', 1), ('m', 1), ('s', 1), ('u', 1), ('n', 1), ('g', 1)] 대문자 먼저 정렬해주고 그 이후..

[백준] 1929 파이썬(python) : 소수 구하기 - (에라토스테네스의 체)

보호되어 있는 글입니다.