[알고리즘] 플로이드 워셜, 그것이 알고싶다

최단 경로 알고리즘,마지막으로 플로이드 워셜 알고리즘을 알아봅시다!  # 플로이드 워셜 알고리즘이란?모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용하는 최단 경로 알고리즘입니다.  다익스트라 알고리즘과의 비교다익스트라단계마다 최단 거리를 가지는 노드를 하나씩 선택해서, 경로를 확인하며 최단 거리 테이블을 갱신그리디 알고리즘플로이드 워셜단계마다 거쳐 가는 노드를 기준으로 알고리즘 실행DP 알고리즘즉, 플로이드 워셜은 최단 거리를 갖는 노드를 찾는 게 아니라, 거쳐가는 노드를 확인합니다.   # 플로이드 워셜 알고리즘의 시간 복잡도노드의 갯수가 N개 일 때, N번의 단계를 수행하며,단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려하므로총 시간 복잡도는 ..

• format_list_bulleted 교육/SSAFYcial
• · 2024. 1. 31.
• textsms

[알고리즘] 알고리즘과 시간 복잡도

알고리즘이란? 문제 해결을 위한 절차나 방법 좋은 알고리즘이란 무엇인가 정확성: 얼마나 정확한지 작업량: 얼마나 적은 연산으로 결과를 내는지 메모리 사용량: 얼마나 적은 메모리를 사용하는지 단순성: 얼마나 단순한지 최적성: 개선할 여지가 없는지 시간 복잡도 실제 걸리는 시간을 측정, 실행되는 명령문의 개수를 계산해서 얻어낼 수 있음 빅 - 오 표기법 시간 복잡도 함수 중에서 가장 큰 영향을 주는 n에 대한 항만을 표시한 것 계수는 생략함 예: O(n) = O(3n)

• format_list_bulleted 알고리즘
• · 2023. 10. 5.
• textsms

[SWEA] 창용 마을 무리의 개수

# Union-Find #DFS 문제 창용 마을에는 N명의 사람이 살고 있다. 사람은 편의상 1번부터 N번 사람까지 번호가 붙어져 있다고 가정한다. 두 사람은 서로를 알고 있는 관계일 수 있고, 아닐 수도 있다. 두 사람이 서로 아는 관계이거나 몇 사람을 거쳐서 알 수 있는 관계라면, 모두 묶어서 하나의 무리라고 한다. 창용 마을에 몇 개의 무리가 존재하는지 계산하는 프로그램을 작성하라. 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 각각 창용 마을에 사는 사람의 수와 서로를 알고 있는 사람의 관계 수를 나타내는 두 정수 N, M(1 ≤ N ≤ 100, 0 ≤ M ≤ N(N-1)/2) 이 공백 하나로 구분되어 주어진다. 이후 M개의 줄에 걸쳐서 서로를 알고 있는 두..

• format_list_bulleted 알고리즘/문제풀이
• · 2023. 9. 23.
• textsms

[SWEA]Ugly Number - 파이썬

문제 Ugly Number란 소인수분해 했을 때, 2 / 3 / 5 로만 이루어진 수를 의미한다. 예외로 숫자 1은 첫번째 Ugly Number로 정의한다. Ugly Number를 순서대로 나열하면 다음과 같다. 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, .... 이때, 숫자 K를 입력받으면, 'K번째' Ugly Number를 출력하시오. 첫줄에는 문제의 개수 Q(1

• format_list_bulleted 알고리즘/문제풀이
• · 2023. 8. 22.
• textsms