본문 바로가기

Programming [Python]

 (411)
#288 백준 파이썬 [2458] 키 순서 - 플로이드 와샬 https://www.acmicpc.net/problem/2458 SOLUTION 플로이드 와샬 알고리즘과, pypy 컴파일러로 풀 수 있다. 자신이 갈 수 있는 노드들은 자기보다 작은 사람들이며 자신에게 오는 경로가 있는 노드들은 자기보다 큰 사람들이다. 이 둘의 합이 자신을 제외한 N-1인 경우 자신의 순서를 알 수 있는 것이다. 알고리즘 자체의 해결법은 https://claude-u.tistory.com/334 이 곳을 참조하자. PYTHON CODE import sys #입력 N, M = map(int, input().split()) height = [[0 for _ in range(N+1)] for _ in range(N+1)] for _ in range(M): tall, short = map(..
#287 백준 파이썬 [1238] 파티 - 플로이드 와샬 https://www.acmicpc.net/problem/1238 SOLUTION 플로이드 와샬 알고리즘으로 풀 수 있는 문제. 다익스트라 알고리즘으로도 풀 수 있지만, pypy로 컴파일 해가면서 까지기어코 플로이드 와샬로 풀었다. 문제의 풀이 해결 및 코드는 https://claude-u.tistory.com/334 와 같다. 또한 통과를 위해 pypy로 제출하였다. PYTHON CODE import sys #입력 N, M, X = map(int, input().split()) distance = [[M * 100 for _ in range(N+1)] for _ in range(N+1)] for _ in range(M): start, end, time = map(int, sys.stdin.readlin..
#286 백준 파이썬 [1389] 케빈 베이컨의 6단계 법칙 - 플로이드 와샬 https://www.acmicpc.net/problem/1389 SOLUTION 플로이드 와샬로 해결할 수 있는 문제. https://claude-u.tistory.com/334 의 문제와 해결법과 동일하다. 출력부분만 부분 수정해준다. PYTHON CODE #입력 N, M = map(int, input().split()) friend_map = [[N for _ in range(N)] for _ in range(N)] for _ in range(M): friend_A, friend_B = map(int, input().split()) friend_map[friend_A-1][friend_B-1] = 1 friend_map[friend_B-1][friend_A-1] = 1 #플로이드-워셜 알고리즘 fo..
#285 백준 파이썬 [11403] 경로 찾기 - 플로이드 와샬 https://www.acmicpc.net/problem/11403 SOLUTION 플로이드-워셜 문제로 해결하였다. https://claude-u.tistory.com/334 해당 문제 및 풀이와 같다. PYTHON CODE #입력 N = int(input()) graph = [] for _ in range(N): graph.append(list(map(int, input().split()))) #플로이드-워셜 알고리즘 for k in range(N): #경로 for문이 가장 상위 단계여야 누락되지 않는다 for i in range(N): for j in range(N): if graph[i][j] == 1 or (graph[i][k] == 1 and graph[k][j] == 1): graph[i][..
#284 백준 파이썬 [1956] 운동 - 플로이드 와샬 https://www.acmicpc.net/problem/1956 SOLUTION 플로이드 워셜 알고리즘으로 풀 수 있다. https://www.acmicpc.net/problem/11404 문제와 https://claude-u.tistory.com/334 해결법을 참조하자 해당 링크의 풀이법과 distance[i][i]만을 확인해주면 된다. 또한 시간 복잡도 때문에 pypy로 풀어야한다. PYTHON CODE import sys V, E = map(int, input().split()) INF = 10000 * V + 1 #전체 사이클을 돌 경우 최댓값 +1 distance = [[INF for _ in range(V+1)] for _ in range(V+1)] for _ in range(E): sta..
#283 백준 파이썬 [11404] 플로이드 - 플로이드 와샬 https://www.acmicpc.net/problem/11404 SOLUTION 플로이드 워셜 알고리즘을 사용하는 기초적인 문제다. 각각의 지점에서 모든 정점에 관한 최단 경로를 구하는 알고리즘 위키피디아보다 나무위키에서 보다 잘 설명해주고 있다. 설명 패스 (https://namu.wiki/w/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98) 요약하자면 i를 출발해 j로 바로 가는 것보다 i를 출발해 k를 거쳐 j로 가는 게 효율적일 경우(저렴할 경우) 해당 값을 갱신해주는 것이다. 경로 k라 해서 하나의 정점 k만 거치는 것이 아니다. 여러 정점을 거치는 모든 경우의 수가 포함..
#282 백준 파이썬 [2206] 벽 부수고 일어나기 - BFS https://www.acmicpc.net/problem/2206 SOLUTION 기본적으로 BFS를 통한 미로탐색 문제와 성격이 같다. https://www.acmicpc.net/problem/2178 문제와 https://claude-u.tistory.com/212 풀이를 보자 여기에 더하여 한 가지의 벽 알고리즘을 더 추가해준다. 벽 알고리즘 1) distance[N][M] 리스트를 만들어 벽에 도달했을 때 distance를 저장해준다. 2) BFS를 활용했으므로 처음으로 벽에 도달한 순간이 가장 빠르게 도달한 경우이다. 따라서 이후 distance는 필요 없으므로 visited[i][j]에 True를 대입해 더 이상 방문하지 않도록 한다. 3) 미로의 시작 지점인 0,0과 끝 지점인 N,M에서 두..
#281 백준 파이썬 [16680] 안수빈수 https://www.acmicpc.net/problem/16680 SOLUTION N의 배수의 자릿수를 합해서 짝수를 출력하면 되는 문제다. 시간 초과에 유의하며 풀어준다. PYTHON CODE T = int(input()) for _ in range(T): N = int(input()) while N

티스토리툴바