본문 바로가기

알고리즘6

알고리즘 - 플로이드-워셜(Floyd-Warshall) 들어가며Baekjoon 11403 문제를 접하게 되면서 플로이드 워셜에 대해 알게되었고 그에 대해 간단하게 공부해보려고 한다.플로이드 워셜(Floyd-Warshall)이란?모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘. 즉 모든 노드간의 최단 경로를 구하는 알고리즘이다. 시간 복잡도는  $ O\left ( V^{3} \right ) $ 이며, 다익스트라 알고리즘과 다르게 음의 가중치를 가지는 그래프에서도 사용할 수 있다.거쳐가는 정점을 기준으로 한다 예시)위와 같은 그래프가 존재한다고 생각합시다. 이때 만나지 못하는 정점의 관계는 무한, 자기자신의 정점은 0으로 두고 각각 정점을 기준으로 표로 정리하게 되면. 1234105무한82709무한32무한044무한무한30현재까지 계산된 최소 비용.. 2024. 6. 18.
[백준: 1339] 단어 수학 (발표자료) 들어가며수업시간에 알고리즘 문제 발표를 맡게 되어 이 글을 작성한다. https://www.acmicpc.net/problem/1339단어 수학시간 제한메모리 제한제출정답맞힌 사람정답 비율2 초256 MB35715165631268546.047%문제민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, .. 2024. 6. 14.
다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra)란?다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path)탐색 알고리즘 입니다. 즉 하나의 정점에서 모든 정점으로 가는 최단 경로를 알려준다. -> ex) 인공위성다만 음의 간선을 포함할 수 없으며, 현실에도 음의 간선은 존재하지 않기에 현실에서 사용하기 적합한 알고리즘 입니다. 예제1)"1부터 다른 노드로 가는 최단 경로를 구해보자"1. 1의 연결 노드는 2, 3, 4이며 각각 3, 6, 7로 산정할 수 있다.0367위 그래프는 1, 2, 3, 4 다른 노드로 가는 비용을 정리한 것  2. 그럼 비용이 가장 저렴한 2번 노드로 가서 산정을 해본다. 이때 무한은 접근 할수가 없는 노드이다.301무한이렇게 되면 3번 노드는 3 + 1로 이전에 있었던 6비용보다.. 2024. 5. 1.
[백준: 6198] 옥상 정원 꾸미기 https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net = = = = - = = = = -> 관리인이 보는 방향 = - = = = = = = = = = 10 3 7 4 12 2 -> 빌딩의 높이 [1][2][3][4][5][6] -> 빌딩의 번호 이런 문제이다. 즉 자신보다 낮은 빌딩은 확인하고 그때의 갯수가 카운트 되지만 자신보다 높으면 확인하지 막히는 문제이다. 입출력 예제를 보고 생각을 해보자 예제 입력 1 복사 6 10 3 7 4 12 .. 2024. 4. 9.

티스토리툴바