[백준 파이썬] 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

[백준 파이썬] 2644 촌수계산

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 문제 사촌간의 관계가 주어지고 촌수를 계산하는 문제이다. 아이디어 입력값으로 각각의 인원에 대한 정보값이 주어진다. 해당 정보를 바탕으로 그래프를 만든 뒤 깊이 우선탐색으로 해결하면 되겠다고 생각했다. 풀이 먼저 그래프에 관한 정보를 입력받는다 graph = [[] for _ in range(n + 1)] visited = [-1] * (n + 1) result = [] f..

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