전체 글
-
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)..
-
BOJ 12886 돌 그룹(Python 3)알고리즘/BOJ 2019. 1. 29. 17:13
https://www.acmicpc.net/problem/12886 물통이랑 비슷한 문제입니다. A,B,C 중복 체크를 확인해주는 것만 생각하면 되는 문제입니다.A,B의 값을 알고 있다면 C를 구할 수 있으니 2차원 배열로 나타낼 수 있습니다.(2차원 배열 중복 확인은 A,B를 하든, B,C를 하든 입맛에 맞게 하면 됩니다.)저는 최솟값, 최댓값으로 중복 체크를 했습니다. 그리고 제 코드는 BFS를 돌리기 전에 A+B+C가 3의 배수가 아니면 0을 출력하고 종료하는 것으로 만들었는데, 이 부분은 BFS 돌리면서 A,B,C의 값이 같을 때 처리해도 무방합니다. 코드확인 123456789101112131415161718192021222324252627from collections import dequea,b..
-
BOJ 14497 주난의 난(難)(Python 3)알고리즘/BOJ 2019. 1. 25. 13:44
https://www.acmicpc.net/problem/14497 숨바꼭질3과 비슷한 문제이다. 주난이 상하좌우로 이동할 수 있다고 가정할 때, 친구가 있는 곳으로 이동하는데 1초가 걸리고, 빈 공간이 있는 곳으로 이동하는데 0초가 걸린다고 생각하면 된다. 빈 공간으로 이동할 때는 appendleft로 큐의 맨 왼쪽에 넣어주고, 친구가 있는 곳으로 이동할 때는 append를 이용해 큐의 오른쪽에 넣어준다. 숨바꼭질3을 푸는 방법처럼 heapq를 이용해서 풀어도 풀 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 from collections import deque n,m=map(int,input().split()) x1,y1,x2,y2=map(..
-
BOJ 7569 토마토(Python 3)알고리즘/BOJ 2019. 1. 25. 13:22
https://www.acmicpc.net/problem/7569 바로 이전 글에 있는 토마토 문제의 3차원 버전 문제이다. 여기에서 주의할 점은 M,N,H로 주어지는 값이 배열에서는 List[H][N][M] 이다. 이 부분만 유의해서 만든다면 2차원 토마토와 똑같은 문제이다. 코드확인 1234567891011121314151617181920212223242526from collections import dequem,n,h=map(int,input().split())D=[list(list(map(int,[*map(int,input().split())])) for _ in range(n)) for k in range(h)]dx,dy,dz=[0,0,0,0,1,-1],[0,0,1,-1,0,0],[-1,1,0,..
-
BOJ 7576 토마토(Python 3)알고리즘/BOJ 2019. 1. 25. 13:06
https://www.acmicpc.net/problem/7576 재미있는 BFS문제이다. 완전 탐색으로 1이 들어간 값을 전부 큐에 저장한 뒤에 BFS 돌리면 된다.이 문제에서 질문 글이 쏟아지는데 파이썬은 최댓값을 제대로 잡았는지, 방문 체크 리스트를 만들어서 이미 방문한 곳인지 아닌지 확인하면 된다. 코드확인 12345678910111213141516171819202122232425from collections import dequedx,dy=[0,0,1,-1],[1,-1,0,0]m,n=map(int,input().split())D=[[*map(int,input().split())] for _ in range(n)]a=[[-1]*m for _ in range(n)]q=deque()for i in r..