본문 바로가기

알고리즘4

알고리즘 - 플로이드-워셜(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.
[백준: 9375] 패션왕 신해빈 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 128 MB 39671 22016 18519 55.281% 문제 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까? 입력 첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다. 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다. 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은.. 2024. 4. 8.