말감로그

오늘은 건강상의 이슈로.. 공부를 하지 못하였습니다. 저녁 쯤엔 좀 괜찮아져서 어제 공부했던 BFS 3문제라도 풀었다.그리구 올림픽 때문에 공부에 집중을 하지 못하고 있슴...대한민국 화이팅..ㅜㅜ알고리즘수업- 너비우선탐색2 이 문제는 어제 풀었던 알고리즘수업 - 너비우선탐색1 문제와 똑같다. 다른 점은 인접 정점은 내림차순으로 방문한다는 점밖에 없다. 그래서 sort(reverse=True) 를 사용하여 graph를 내림차순으로 정렬해주었다.import sysfrom collections import dequeinput = sys.stdin.readlineN,M,R = map(int,input().split())graph = [[] for _ in range(N+1)]visited_bfs = [0] *..

1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개..

1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 문제 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야" “그럼 8179로 해” “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐..

에라토스테네스의 체 다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘이다. 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다. 동작 과정 1. 2부터 N까지의 모든 자연수를 나열한다. 2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다. 3. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다.) 4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다. 에라토스테네스의 체 알고리즘 (파이썬) import math n = 100 #2부터 100까지의 모든 수에 대하여 소수 판별 prime = [True for i in range(n+1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화 for i in r..