CS/Algorithm9 [알고리즘 개념 정리] 플로이드 워셜 (Python) [이것이 코딩 테스트다 with Python] 31강 플로이드 워셜 알고리즘을 듣고 정리한 내용입니다. 플로이드 워셜 알고리즘 - 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산하는 알고리즘이다. - (다익스트라 알고리즘과 마찬가지로) 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 다만, 다익스트라 알고리즘과 달리 매 단계마다 방문하지 않은 노드 중에 최단거리를 갖는 노드를 찾는 과정이 필요하지 않다. - 2차원 테이블에 최단거리 정보를 저장한다. - 다이나믹 프로그래밍 유형에 속하며, 시간 복잡도는 O(n³)이다. - 노드의 갯수가 적은 경우에 사용이 적합하며, 노드와 간선의 갯수가 많은 경우에는 다익스트라 알고리즘을 활용해야하는 경우가 많다. 실제로도 .. 2024. 3. 25. [백준 2573번] 빙산 (Python) 그래프 탐색(DFS, BFS)과 추가적인 구현이 필요한 문제였다. 문제 링크 2573번 빙산 문제 요약 이 문제는 지구 온난화로 인해 북극의 빙산이 녹고 있는 상황을 배경으로 한다. 빙산을 2차원 배열에 양의 정수로 표시하여, 각 부분별 높이 정보를 배열의 각 칸에 저장한다. 빙산이 아닌 바다에 해당되는 칸에는 0이 저장된다. 빙산의 높이는 동서남북 네 방향으로 0이 저장된 칸의 개수만큼 매년 줄어든다. 한 덩어리의 빙산이 주어졌을 때, 이 빙산이 두 덩어리 이상으로 분리되는 시간(년)을 구하는 것이 문제의 목표. 입력: 첫 줄에는 2차원 배열의 행과 열의 개수(N, M)가 주어지고, 그 다음 N개의 줄에는 M개의 정수가 주어지며, 이는 빙산의 높이 정보 출력: 빙산이 두 덩어리 이상으로 분리되는 최초.. 2024. 3. 11. [백준 14501번] 퇴사 (Python) 다이나믹 프로그래밍을 활용하여 푸는 문제이다. (DP? 나에겐 너 무 어 려 워 😭) 점화식 세우는게 반복되는 규칙성있는 로직을 파악하지 않고서야 감도 안잡히기 때문에 자꾸 DP문제에 그리디로 접근하게 되는 부족함이 있다. 하다하다 안되어서 뤼튼과 함께했다. → 이해를 목표로 다시 정리! 문제 링크 14501번 퇴사 (똑같은 문제, 15486번 퇴사2) 문제 요약 재택 근무 중인 백준이가 퇴사까지 남은 N일 안에 상담을 통해 얻을 수 있는 최대 수익을 계산하는 문제 상담을 완료하는 데 필요한 기간 ( T_i )와 상담을 통해 얻을 수 있는 수익 ( P_i )가 주어진다. 상담 기간이 퇴사일을 넘기면 안 되고, 한 번에 한 개의 상담만 진행할 수 있다. 필요 항목 정리 퇴사까지 N일 날짜별로 얻을 수 있는.. 2024. 3. 7. 이전 1 2 다음
