본문 바로가기

전체 글118

백준 - 10159번 저울 python 문제풀이 [Hellfer] https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 🔷 알고리즘 분류 - 플로이드-워셜, 난이도 - 골드 4 🔶문제 풀이 - 플로이드-워셜을 이용한 풀이 플로이드 워셜이란? 플로이드 워셜(Floyd-Warshall) 알고리즘은 그래프에서 모든 노드 간의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 '모든 노드'를 '중간에 거치는 노드'로 삼아 '모든 노드 쌍'에 대한 최단 경로를 계산합니다. 본질적으로 플로이드 워셜 알.. 2023. 11. 16.
백준 - 11403번 경로 찾기 python 문제풀이 [Hellfer] https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 🔷 알고리즘 분류 - 플로이드-워셜, 난이도 - 실버 1 🔶문제 풀이 - 플로이드-워셜을 이용한 풀이 플로이드 워셜이란? 플로이드 워셜(Floyd-Warshall) 알고리즘은 그래프에서 모든 노드 간의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 '모든 노드'를 '중간에 거치는 노드'로 삼아 '모든 노드 쌍'에 대한 최단 경로를 계산합니다. 본질적으로 플로이드 워셜 알고리즘은 다이내믹 프로그래밍 기법을 사용합니다. 그래프.. 2023. 11. 15.
백준 - 11404번 플로이드 python 문제풀이 [Hellfer] https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 🔷 알고리즘 분류 - 플로이드-워셜, 난이도 - 골드 5 🔶문제 풀이 - 플로이드-워셜을 이용한 풀이 플로이드 워셜이란? 플로이드 워셜(Floyd-Warshall) 알고리즘은 그래프에서 모든 노드 간의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 '모든 노드'를 '중간에 거치는 노드'로 삼아 '모든 노드 쌍'에 대한 최단 경로를 계산합니다. 본질적으로 플로이드 워셜 알고리즘은 다이내믹 프로그래.. 2023. 11. 15.
백준 - 2178번 미로 탐색 python 문제풀이 [Hellfer] https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 🔷 알고리즘 분류 - BFS(너비우선탐색), 난이도 - 실버 1 너비 우선 탐색(Breadth-First Search, BFS) 알고리즘은 그래프 또는 트리를 탐색하는 방법 중 하나로, 시작 노드에서 가장 가까운 노드부터 탐색하는 방법입니다. BFS는 '레벨(level)'이 같은 노드들을 모두 탐색한 후에 다음 레벨의 노드들을 탐색하게 됩니다. BFS는 큐(Queue) 자료구조를 이용해서 구현됩니다. 큐는 '선입선출(FIFO, .. 2023. 11. 15.
백준 - 1012번 유기농 배추 python 문제풀이 [Hellfer] https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 🔷 알고리즘 분류 - BFS(너비우선탐색), 난이도 - 실버 2 너비 우선 탐색(Breadth-First Search, BFS) 알고리즘은 그래프 또는 트리를 탐색하는 방법 중 하나로, 시작 노드에서 가장 가까운 노드부터 탐색하는 방법입니다. BFS는 '레벨(level)'이 같은 노드들을 모두 탐색한 후에 다음 레벨의 노드들을 탐색하게 됩니다. BFS는 큐(Queue) 자료구조를 이용해서 구현됩니다. 큐는 '.. 2023. 11. 15.
백준 - 1260번 DFS와 BFS python 문제풀이 [Hellfer] https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 🔷 알고리즘 분류 - 너비우선탐색, 깊이우선탐색 난이도 - 실버 2 너비 우선 탐색(Breadth-First Search, BFS) 알고리즘은 그래프 또는 트리를 탐색하는 방법 중 하나로, 시작 노드에서 가장 가까운 노드부터 탐색하는 방법입니다. BFS는 '레벨(level)'이 같은 노드들을 모두 탐색한 후에 다음 레벨의 노드들을 탐색하게 됩니다. BFS는 큐.. 2023. 11. 15.
백준 - 15652번 N과 M (4) python 문제풀이 [Hellfer] https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 🔷 알고리즘 분류 - 백트래킹, 난이도 - 실버 3 백트래킹(Backtracking) 알고리즘은 결정해야 하는 여러 개의 선택지가 있고, 이 중에서 최적의 해결책을 찾아내야 하는 문제들에 대해 사용됩니다. 이 알고리즘은 모든 가능한 경로를 탐색하되, 어떤 경로가 해결책으로 이어질 것 같지 않으면 그 경로를 더 이상 탐색하지 않고 다른 경로를 탐색하는 방식으로 동작합니다. 이런 방식을 통해 불필요.. 2023. 11. 14.
백준 - 1600번 말이되고 싶은 원숭이 python 문제풀이 [Hellfer] https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 🔷 알고리즘 분류 - BFS(너비우선탐색), 난이도 - 골드 3 🔶문제 풀이 - BFS(너비우선탐색)을 이용한 풀이 from collections import deque # 말처럼 움직일 때 이동하는 방향 dx1 = [-2, -1, 1, 2, 2, 1, -1, -2] dy1 = [1, 2, 2, 1, -1, -2, -2, -1] # 평범하게 움직일 때 이동하는 방향 dx2 = [-.. 2023. 11. 14.

티스토리툴바