728x90 백준149 SPFA(Shortest Path First Algorithm) SPFA(Shortest Path First Algorithm) 알고리즘은 "음수 간선을 포함한 데이크스트라 알고리즘"으로 이해하면 편한 "벨만 포드 알고리즘"을 개선한 알고리즘 입니다. BFS - 데이크스트라 - 벨만포드(SPFA)로 학습을 진행하시면 편합니다. 벨만 포드는 "모든 간선에 대해 업데이트를 진행"하지만, SPFA는 "바뀐 정점과 연결된 간선에 대해서만 업데이트를 진행"합니다. 벨만포드를 학습하지 않고, SPFA를 학습하셔도 태그로 벨만포드가 들어간 문제를 대부분 해결하실 수 있습니다. ex) https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주.. 2023. 1. 24. Dijkstra - 데이크스트라(다익스트라) 데이크스트라(Dijkstra)는 BFS 알고리즘을 알고 있다면 조금 더 쉽게 이해할 수 있다. 시작 지점 부터 가고자하는 도착지점까지 최소한의 시간으로 도착할 수 있는 거리를 구하는 알고리즘이다. ex)https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 예제 입력은 1번에서 출발하여 5번까지 도착하는데 걸리는 최소 시간을 구하는 문제입니다. 1 -> 4 -> 5을 이동하게 된다면 1 + 3 = 4의 시간이 걸리게 .. 2023. 1. 22. BFS - 너비 우선 탐색 / DFS - 깊이 우선 탐색 너비 우선 탐색(Breadth First Search) / DFS(Depth First Search)은 시작지점부터 갈 수 있는 지점들을 들리면서, 더이상 갈 곳이 없을때까지 반복한 후 종료한다. ex) https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 해당 문제는 이런 모양의 간선과 노드들로 이루어져 있습니다. 1번 컴퓨터에 바이러스가 걸리게 된다면, 1과 2, 3, 5, 6 총 4개의 컴퓨터가 1번 컴퓨터에 의해 바이러스에 감염되면서, 5개의 컴퓨.. 2023. 1. 22. 백준 랭킹 1페이지 달성! 2023 / 01 / 03 2022년 목표였으나 미뤄져 2023년 목표 중 하나인 랭킹 1페이지를 달성했습니다. 2513문제로 100등을 달성하였습니다. 오늘 하루동안 26문제를 해결하였고, https://www.acmicpc.net/problem/25822 요기 나오는 24문제의 기준점을 넘어버렸습니다! 25822번: 2000문제 푼 임스 이 문제는 문제 출제를 위해 꾸준히 문제를 풀어 2000문제 풀이를 달성한 임스가 처음으로 출제한 문제입니다. 임스는 문제 출제를 위해 매일 0 ~ 24문제를 풀었습니다. 임스가 스트릭을 끊기지 않 www.acmicpc.net solved.ac 현 상황 앞으로 랭킹을 빼앗기지 않는 이상 1문제씩만 풀면서 스트릭을 유지할거 같습니다. 2023. 1. 3. 이전 1 ··· 7 8 9 10 11 12 13 ··· 38 다음 728x90
