알고리즘
-
BOJ 16933 벽 부수고 이동하기 3(Python 3)알고리즘/BOJ 2019. 2. 18. 01:02
https://www.acmicpc.net/problem/16933 밤에만 벽을 부술 수 있는 점에 주의하면 됩니다.파이썬은 heapq로 하면 시간 초과가 나옵니다.deque를 이용해서 다익스트라 비슷하게 풀면 됩니다. 큐에 5개의 값을 넣어주는데 n, m, k, S[n][m][k], 낮/밤 입니다.Python3으로 제출하면 시간 초과가 나오니 Pypy3으로 제출하면 됩니다. 코드 확인 1234567891011121314151617181920212223242526from collections import dequeinput=__import__('sys').stdin.readlinen,m,k=map(int,input().split())D=[input() for _ in range(n)]q=deque([(0..
-
BOJ 14442 벽 부수고 이동하기 2(Python 3)알고리즘/BOJ 2019. 2. 18. 00:50
https://www.acmicpc.net/problem/14442 벽 부수고 이동하기 1 과 다른 점은 배열 설정 말고는 없다.dist[n][m][2]를 dist[n][m][k] 로 바꿔서 풀면 된다.Python 3으로 제출하면 느리기 때문에 Pypy 3으로 제출해야한다. 코드 확인 1234567891011121314151617181920212223from collections import dequen,m,k=map(int,input().split())D=[list(map(int,[*input()])) for _ in range(n)]S=[[[-1]*(k+1) for _ in range(m)] for __ in range(n)]S[0][0][0]=1q=deque([(0,0,0)])dx,dy=[0,0,1..
-
BOJ 2206 벽 부수고 이동하기(Python 3)알고리즘/BOJ 2019. 2. 18. 00:45
https://www.acmicpc.net/problem/2206 단순 BFS문제이다.배열을 3차원 배열 dist[n][m][2]로 만들어 주면 풀기 쉽다.마지막 [2]는 벽을 부숴본 적이 없을 때/벽을 부숴본 적이 있을 때로 나눈 것이다. 코드 확인 12345678910111213141516171819202122from collections import dequen,m=map(int,input().split())S=[list(map(int,[*input()])) for k in range(n)]D= [[[-1]*2 for j in range(m)] for i in range(n)]D[0][0][0]=1q=deque()q.append((0,0,0))dx,dy=[0,0,1,-1],[1,-1,0,0]whil..
-
BOJ 10217 KCM Travel(Python 3)알고리즘/BOJ 2019. 2. 17. 01:33
https://www.acmicpc.net/problem/10217 총 24번 제출을 하였다... (통과하기전)(C언어로 통과했을 때)(파이썬으로 통과했을 때) 파이썬으로 다익스트라+DP를 구현하는데 자꾸 시간 초과,메모리 초과,틀렸습니다가 떴다. 12345678910111213141516171819202122from heapq import *input=__import__('sys').stdin.readlinefor __ in range(int(input())): n,m,k=map(int,input().split()) D=[[] for _ in range(n+1)] for i in range(k): u,v,c,d=map(int,input().split()) D[u].append((v,c,d)) S=[[f..
-
BOJ 16681 등산(Python 3)알고리즘/BOJ 2019. 2. 15. 15:47
https://www.acmicpc.net/problem/16681 엄청나게 고통 받은 문제다.. heapq로 풀면 시간 초과,,, deque로 풀면 메모리 초과,,,메모리 초과는 암만 생각해봐도 잘못된 풀이 방법이기에 heapq에 집중하기로 했다. 다익스트라를 따로 공부한게 아니라 heapq로 저런 알고리즘을 구현 할 수 있다는 생각으로 문제를 풀기 시작했기 때문에 개념에 구멍이 숭숭 뚫려있는 상태였는데, 이 문제를 풀고 완벽하게 다익스트라를 구현 할 수 있게 되었다.그동안 풀은 다익스트라 문제는 간선의 수가 작아서 운 좋게 통과한 듯 싶다. (heappop에서 리스트의 값이랑 일치하지 않는 값이 나오면 continue를 해야하는데, 나는 이걸 모른 상태로 풀어왔다) 간단하게 1에서부터 n까지의 최소 ..
-
BOJ 4184 Ocean Currents(Python 3)알고리즘/BOJ 2019. 2. 14. 22:11
https://www.acmicpc.net/problem/4184 이 문제 때문에 굉장히 오랜 시간을 날려 먹었다. 다익스트라로 구현했는데 왜 시간 초과가 나오는 것일까?문제 분류에 나오는데로 충실히 구현했는데 ㅠㅠ오전 10시쯤에 도전했는데 오후 9시쯤이 되서야 풀었다....가중치가 0,1이면 무조건 deque를 써야 정신건강에 이롭다는 교훈을 얻었다. heappush와 heappop의 시간 복잡도가 얼마인지는 모르겠지만 O(1)보다는 무조건 더 걸린다. 만약 이동하는 곳이랑 맵의 숫자와 같다면 appendleft로 큐의 왼쪽에 넣어주고, 아니라면 append로 큐의 오른쪽에 넣어주면 된다.최악의 경우에는 입력 값이 매우 많이 들어오기 때문에 sys.stdin.readline으로 값을 받아내고, pypy..
-
BOJ 9505 엔터프라이즈호 탈출(Python 3)알고리즘/BOJ 2019. 2. 14. 19:53
https://www.acmicpc.net/problem/9505 일반 BFS로 풀면 python, pypy로는 시간 초과가 나오는 문제이다.그래서 heapq를 이용한 다이젝스트라로 문제를 풀었다. 그동안 다익스트라로 풀어야할 문제를 전부 bfs, deque로 풀어내서(...) heapq를 이용해 직접 풀은 문제는 이번이 처음이다.저번에 숨바꼭질 질문 글을 통해 heapq의 존재를 처음 알게 되었는데 자주 써먹을 수 있을 것 같다. 다이젝스트라는 BFS와 상당히 유사하지만, BFS와의 차이점은 heapq를 이용하기 때문에 q에서 뱉어내는 좌표중에서 가장자리 좌표를 제일 먼저 뱉어내는 값이 최소값이라는 것이다.K는 dict,defaultdict,list 셋중에서 뭘 하든 상관 없어 보인다. 아래 코드는 l..
-
BOJ 13903 출근(Python 3)알고리즘/BOJ 2019. 1. 30. 17:54
https://www.acmicpc.net/problem/13903 푸는 방법은 간단합니다.1. 1행에 있는 C개의 열을 전부 큐에 집어 넣고, BFS를 돌립니다.2. BFS를 다 돌린 후, R행에서 최솟값을 구합니다. 파이썬은 까딱하면 시간 초과가 나오니까 Pypy3으로 제출하는게 좋습니다. 코드확인 1234567891011121314151617181920212223242526from collections import dequen,m=map(int,input().split())D=[list(map(int,input().split())) for _ in range(n)]S=[[-1]*m for _ in range(n)]k=int(input())dx,dy=[0]*k,[0]*kfor i in range(k)..