[백준 파이썬] 1261 알고스팟

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 해당 지점으로 이동할 때 가장 적게 벽을 부수는 경우를 구하는 문제이다 아이디어 최단거리를 탐색하는 문제이기 때문에 다익스트라를 이용하였다. 풀이 def dijkstra(): q = [] heapq.heappush(q, (0, 0, 0)) #cost, x, y distance[0][0] = 0 while q: cost, x, y = heapq.heappop(q) if ..

• format_list_bulleted 알고리즘
• · 2023. 12. 27.
• textsms

[백준 파이썬] 15686 치킨 배달

15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 "치킨거리"값이 가장 큰 값이 되도록 폐업시킬 치킨집을 적절히 고르는 문제이다. 아이디어 N값이 최대 50이고 시간제한은 1초이기 때문에 n3으로 모든 경우를 탐색해도 시간에 걸리지 않는다고 생각했다. 따라서 브루투포스로 문제를 해결하였다. 풀이 N, M = map(int, input().split()) city = list(list(map(int, input().split())) for _ in range(N)) result = sys..

• format_list_bulleted 알고리즘
• · 2023. 12. 18.
• textsms

[백준 파이썬] 11581 구호물자

11581번: 구호물자 서기 2050년 엄청나게 강력한 폭풍이 인천을 강타했다. 강력한 폭풍의 영향으로 모든 사람은 대피소로 대피하였으며, 많은 도로가 유실되었다. 그나마 남아있는 도로도 모든 표지판과 가로등이 www.acmicpc.net 문제 그래프에서 시작 정점으로 다시 돌아오는 경우를 판단하는 문제이다. 아이디어 DFS를 이용해서 방문여부를 판단하며 문제를 풀 수 있을거라 생각했다. 하지만 플로이드를 연습할 겸 플로이드 워셜로 문제를 풀어보았다. 플로이드 워셜은 모든 정점의 경로를 탐색하기때문에 시작지점으로 다시 돌아올 경우를 판단할 수 있다. 풀이 N = int(input()) graph = [[0] * (N+1) for _ in range(N+1)] for i in range(1, N): tem..

• format_list_bulleted 알고리즘
• · 2023. 12. 15.
• textsms

[백준 파이썬] 11404 플로이드

11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 풀이 그래프의 모든 지점에 대해 최소비용을 구하는 문제이므로 플로이드를 사용하였다. 플로이드의 구현 코드는 아래와 같다. for k in range(1, n + 1): for i in range(1, n + 1): for j in range(1, n + 1): graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]) 그래프의 두 지점에 대해 두 지점을 거쳐가는 모든 경우의 최소값을 구해준다. 코드 import s..

• format_list_bulleted 알고리즘
• · 2023. 12. 13.
• textsms

[백준 파이썬] 9251 LCS

12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 풀이 평범한 배낭과 거의 동일하게 문제를 해결하였다. 캐시 배열을 만들어 단어를 하나씩 비교하면서 LCS값을 누적시킨다. 이 때 비교하는 방법은 다음과 같다. 1. 두 알파벳이 같을경우 두 알파벳이 같을 경우에는 두 알파벳을 모두 추가하기 전의 최대값에서 +1을 하면 된다. 배열상에는 cache[i-1][j-1]과 같다. 이를 코드로 표현하면 다음과 같다. if A[i-1] == B[j-1]:..

• format_list_bulleted 알고리즘
• · 2023. 12. 11.
• textsms

[백준 파이썬] 1865 웜홀

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 문제  그래프 정보가 주어진다. 임의의 경로를 정해서 해당 경로를 지나 다시 처음 지점으로 왔을 때 시간이 줄어드는 경우를 체크하는 문제이다. 아이디어 포인트는 시간이 줄어든다는 점이다. 그래프 알고리즘에서 간선이 음수일 경우에도 거리를 구할 수 있는 알고리즘에는 벨만-포드 알고리즘이 있으므로 해당 알고리즘을 사용하면 되겠다고 생각했다. 벨만-포드 알고리즘 벨만-포드 알고리즘은 한..

• format_list_bulleted 알고리즘
• · 2023. 12. 8.
• textsms