알고리즘
-
BOJ 17135 캐슬 디펜스(Python 3)알고리즘/BOJ 2019. 4. 8. 23:22
https://www.acmicpc.net/problem/17135 일단 먼저 필요한 것이 combinations, deepcopy, deque, Max입니다. combinations는 궁수가 어디에 위치하고 있는지 모르기 때문에 모든 경우의 수를 구하기 위해 불러왔습니다. deepcopy는 원본 맵을 복사 하여 각 경우의 수마다 시뮬레이션을 돌려야 하기 때문에 맵의 수정이 필요하므로 불러왔습니다. deque는 몬스터의 좌표를 저장할 때 쓰입니다. Max는 공격할 수 있는 적이 여러 명일 때, 가장 왼쪽에 있는 적을 공격하기 위해서 만들었습니다. 이건 설정 안 해도 됩니다. 1 2 3 4 from itertools import combinations from copy import deepcopy from..
-
BOJ 13905 세부(Python 3)알고리즘/BOJ 2019. 3. 12. 14:48
https://www.acmicpc.net/problem/13905 -크루스칼 알고리즘을 사용함-재귀함수 깊이를 설정 안해주면 런타임 에러가 나옴 주의할 점은 다른 MST문제와 다르게, 매 탐색마다 출발점이랑 도착점이랑 같은 연합인지 확인해봐야 함그래야 가져갈 수 있는 최대한의 빼빼로를 출력할 수 있음 코드확인 1234567891011121314151617181920212223def F(x): if S[x]==x:return x S[x]=F(S[x]) return S[x] import syssys.setrecursionlimit(100000)input=__import__('sys').stdin.readlinen,m=map(int,input().split())s,e=map(int,input().split(..
-
BOJ 1738 골목길(Python 3)알고리즘/BOJ 2019. 3. 7. 18:03
https://www.acmicpc.net/problem/1738 이 문제는 오민식의 고민과 비슷한 문제이다. 음수 싸이클이 있을 경우 큐에 싸이클을 도는 정점을 모두 넣어주고, 큐에 있는 정점들이 코레스코 콘도까지 갈 수 있는지 없는지 확인해준다.(BFS) 만약 음수 싸이클에서 코레스코 콘도로 갈 수 있으면 -1을 출력 시작점에서 코레스코 콘도까지 갈 수 없으면 -1을 출력 갈 수 있으면 경로 리스트를 출력하면 된다. 경로 리스트는 리스트에 넣어둔 좌표를 역추적을 하여 출력하였다. 벨만포드 + BFS로 풀음 코드 확인 123456789101112131415161718192021222324252627282930313233343536from collections import dequeinput=__impo..
-
BOJ 6497 전력난(Python 3)알고리즘 2019. 2. 27. 01:27
https://www.acmicpc.net/problem/6497 간단한 MST 문제이다.돈이 가장 많이 드는 방법은 가로등을 전부 켜는 것돈이 가장 적게 드는 방법은 MST를 이용하는 것둘의 차를 출력하면 끝 입력의 끝에서 0 0에 나오므로 while문을 이용해 풀어야 한다.질문 글에 나와 같은 사람이 있어서 다행이었다.없었으면 맞왜틀 외치면서 내가 질문 글을 썼을 듯 Python3, Pypy3 둘다 sys.stdin.readline 을 써야하며, Python3은 재귀함수 깊이를 따로 설정해주지 않으면 런타임 에러가 난다.그리고 cnt라는 변수를 이용해 cnt=n-1이 되면 for문을 빠져나오게 만들어야 한다. 안그러면 시간 초과가 나온다. 코드 확인 1234567891011121314151617181..
-
BOJ 1613 역사(Python 3)알고리즘/BOJ 2019. 2. 23. 22:02
https://www.acmicpc.net/problem/1613 플로이드 와샬 알고리즘은 단 4줄이기 때문에 외우기 굉장히 쉽다.for k for i for j , ij, ikj 이렇게만 외우면 끝 플로이드를 돌린 후서로 다른 두 사건의 번호가 주어질 때(만약 a,b라고 주어질 때) D[a][b] != INF 이면 -1D[b][a] != INF 이면 1D[a][b] == INF 이면 0을 출력하면 된다. Python으로 제출하면 시간 초과가 나기 때문에 Pypy로 제출 해야 한다. 코드 확인 123456789101112131415n,m=map(int,input().split())Max=float('inf')S=[[Max]*(n+1) for _ in range(n+1)]for i in range(m): ..
-
-
BOJ 16562 친구비(Python 3)알고리즘/BOJ 2019. 2. 20. 14:18
https://www.acmicpc.net/problem/16562 유니온 파인드를 공부하다가 정리할 필요가 있어서 글을 쓰게 되었다. 내 풀이 방법은 v,w의 값을 입력 받을 때 v의 친구비가 더 높으면 v의 루트를 w의 루트로 해두고, w의 친구비가 더 높으면 w의 루트를 v의 루트로 해두었다. 이렇게 해두면 1차적으로 값들이 끼리끼리 모이게 되고, 이 상태에서 for문을 이용해 각 학생의 루트를 다시 구해준다. 이러면 어떤 학생한테 돈을 줘야하는지 알 수 있으니 ans에 값을 더하면 된다. 코드 확인 12345678910111213141516171819202122232425def Find(x): if x==P[x]:return x P[x]=f(P[x]) return P[x]n,m,k=map(int,..
-
BOJ 16946 벽 부수고 이동하기 4(Python 3)알고리즘/BOJ 2019. 2. 18. 01:20
https://www.acmicpc.net/problem/16946 플러드 필 + BFS 문제이다.일단 먼저 말해두자면 (x, y)좌표가 1일 때마다 bfs를 돌리면 시간 초과가 나온다. 그래서 0끼리 뭉쳐있는 곳끼리 값을 설정 해줘야 한다.다 설정했으면 그때 for문을 다시 돌려 벽이 있는 곳이 나온다면 리스트를 하나 만든다음, 상하좌우에 0이 있다면 플러드필을 이용해 저장한 값을 리스트에 저장해준다.그다음 set을 이용해 중복 제거 해주고 값을 더해주면 끝난다. 코드가 너무 길어서 메인 코드 가독성을 해치기 때문에 따로 함수 2개를 구현하였다.bfs 함수는 0끼리 뭉쳐있는 곳을 묶어준 후 리스트에 넓이를 저장해주는 함수이고, Sum 함수는 플러드 필을 다하고 벽 좌표에 출력할 값을 구하는 함수이다. ..