알고리즘/BOJ
-
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 함수는 플러드 필을 다하고 벽 좌표에 출력할 값을 구하는 함수이다. ..
-
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..