전체 글
[백준1939&파이썬] 이진탐색 BFS에 응용하기, 이진탐색 경계값 설정에 주의하자.
# 문제 백준1939 중량제한 파이썬 풀이 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net # 코드 ''' - 노드간 여러개 엣지가 존재 할 수 있다. - 양방향 다리이다. - DFS + 백트래킹을 활용해서 길의 최대값을 구한다 -> 시간초과 or 메모리 초과 - 모든 경우의 수를 구하고 거기서 최대값을 구한다 -> 시간초과 or 메모리 초과 - 이분탐색 시간복잡도 -> O(logN) - 0 ~ 10억의 경우의 수에서 해당 값을 경로가 넘어버리는지 아..
[백준16236&파이썬] BFS을 작은단위로 쪼개 생각하자. 종료조건과 탐색조건을 잘 생각하자.
# 문제 백준 16236 아기상어 파이썬 풀이 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net # 코드 ''' - BFS 단위를 잘 쪼개자. BFS를 소규모 단위로 쪼개서 끝내버릴 수록 코드짜기가 수월한거 같다. - BFS 에서 상태단위를 관리하기 위해서는, 큐에 담아서 뽑아서 계속 유지하고 업데이트 해야한다. - 이동한 경로를 0으로 표기해주자 - 최소값 단위로 뽑아쓴다면 heap을 쓰면 더 빠를거 같다. 물고기 관리하는 fish배열을 heap으로 관리해볼까? ''' import sys from col..
[백준6497&파이썬] 크루스칼은 최소신장트리를 구할 수 있다.
# 문제 백준 6497 전력난 파이썬 풀이 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net # 코드 import sys from heapq import * # m : 집의 수 # n : 길의 수 def find(p,node) : if p[node] == node : return node p[node] = find(p,p[node]) return p[node] def union(p,r,nodeA,nodeB) : a = find(p,nodeA) b = find(p,nodeB) if a==b : return if r[a] <..
[백준1647&파이썬] 크루스칼 알고리즘을 이용한다면 최소신장트리(MST)를 찾을 수 있다.
# 문제 백준 1647 도시분할 계획 파이썬 풀이 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net # 코드 ''' - 마을을 두개로 분리해야한다. - 마을을 두개로 분리할때, MST로 만들고 간선 하나를 떼버리면 마을이 두개로 분리된다. - 그렇다면 가장 큰 값을 가진 간선을 떼버리면 되지 않을까 ''' import sys from heapq import * N, M = map(int, sys.stdin.readline().split()) # N : 집의 개수, M : 길..
[백준1956&파이썬] 플로이드-와샬을 이용해 왕복 최단거리를 찾아보자
# 문제 백준 1956 운동 파이썬 풀이 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net # 코드 ''' # 플로이드 와샬로 전체 경로 구하고, a->b , b->a의 값으로 사이클여부 판단과 동시에 최단경로 출력이 가능해보이는 문제 ''' import sys V,E = map(int,sys.stdin.readline().split()) distance = [[float('inf')] * (V+1) for _ in range(V+1)] for _ in range(E) : a,..