Algorithm23 [Algorithm] 음료수 얼려 먹기 (python 파이썬) DFS [이것이 코딩 테스트다 with python] DFS & BFS 기초 문제 https://www.youtube.com/watch?v=e7_H8SLZlHY&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=21 음료수 얼려 먹기 python 문제 N X M 크기의 얼음 틀이 있습니다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시됩니다. 구멍이 뚫려있는 부분끼리 상,하,좌,우로 붙어있는 경우 서로 연결되어 있는 것으로 간주합니다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하세요. 다음의 4 X 5 얼음 틀 예시에서는 아이스크림 총 3개 생성됩니다. 연결 요소 찾기 문제라고도 볼 수 있다. 문제 조건 문제 해.. 2023. 4. 19. [BOJ] 백준 11404 플로이드 (python 파이썬) https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 풀이에 앞서 백준 11404 플로이드 문제는 플로이드-워셜 알고리즘을 이용한 문제이므로 플로이드-워셜 알고리즘을 이해하고 있으면 좋습니다! 플로이드-워셜 알고리즘 관련해서 제가 최근에 정리해둔 글도 있으니 참고해주시면 이해가 더 쉬우실 거에요! https://zerozero909.tistory.com/41 [Algorithm] 플로이드-워셜 (Floyd-Warshall) 알고리즘 플로이드 워.. 2023. 4. 18. [Algorithm] 플로이드-워셜 (Floyd-Warshall) 알고리즘 플로이드 워셜 알고리즘 그래프에서 최단 거리를 구하는 알고리즘 기능 특징 시간 복잡도 (노드 수:V) 모든 노드 간에 최단 경로 탐색 - 음수 가중치 에지가 있어도 수행할 수 있음. -동적 계획법의 원리를 이용해 알고리즘에 접 O(V^3) (V의 세제곱) 핵심 이론 플로이드-워셜 알고리즘은 도출하는 가장 핵심적인 원리는 A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것이다. 색칠된 에지 경로가 1-> 5 최단 경로라면 1->4 최단 경로와 4->5 최단 경로 역시 색칠된 에지로 이뤄질 수 밖에 없다. 즉, 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이뤄진다는 뜻이 된다. 이 원리로 다음과 같은 .. 2023. 4. 18. [BOJ] 백준 11657 타임머신 (파이썬 python) https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 음수 간선이 있을 수 있으므로 벨만포드 알고리즘을 사용해야한다. 출력 부분에서 "시간을 무한히 오래 전으로 되돌릴 수 있다면" = 음수사이클이 있다면 Step1 문제 분석하기 시작점 및 다른 노드와 관련된 최단 거리를 구하는 문제지만, 특이한 점은 에지에 해당하는 이동하는 시간이 양수가 아닌 0 또는 음수가 가능하다는 것이다. 이렇게 시.. 2023. 4. 15. 이전 1 2 3 4 5 6 다음
