C++에서 코드로 input 파일을 열 때 freopen함수를 쓰려고 하면 IDE에 따라 freopen_s를 쓰라고 귀찮게 할 때가 있다. 그럴때는 ifstream을 쓰는게 낫다. 코드는 아래와 같다 fstream을 include하고 아래와 같이 ifstream cin; cin.open("파일명"); 을 써주면 된다. 물론 인풋 파일은 소스코드 파일과 같은 폴더에 있어야한다. 위에 ios::sync_with_stdio(false); cin.tie(NULL);도 같이 적어주면 좋은데, cin의 속도를 줄여준다. (입력 속도를 줄여준다) 보통 입력을 이렇게까지 해서 불러오는 경우는 입력의 용량이 클 때이니 같이 적어주면 좋다요. 필요에 따라 cout내용도 많다면 cout도 적어주어서 속도를 줄여주면 되겠다.
벨만-포드 알고리즘(Bellman-Ford Algorithm)은 그래프 탐색의 최단거리 알고리즘 중 하나입니다. 잘 알려진 다익스트라, 플로이드-마샬 알고리즘과 달리 벨만-포드 알고리즘은 음수 가중치를 가진 그래프의 최단 경로를 찾아낼 수 있습니다. 또한 최단 거리 알고리즘에서 치명적인 음수 사이클의 존재도 알아차릴 수 있게 해줍니다. (짱짱 👍👍👍) 이 알고리즘은 저에게 조금 신선하고 재밌는 알고리즘이였습니다. 처음엔 이해도 잘 안 가서 고생했습니다 ㅠㅠ 그래서 제 딴에서는 이해하기 쉽게 알려드리고 싶지만 잘 되려나 모르겠습니다. 벨만-포드 알고리즘의 특징과 구현, 그리고 문제를 풀며 얻은 팁들을 소개해드리려 합니다. 잘 부탁드립니다. 🙏🙏🙏 (gd 스타일 ㅋ) 일단, 이 알고리즘의 특징은 기존의 그래..
다익스트라 알고리즘은 최단 경로 알고리즘 중에 가장 기초가 되는 알고리즘입니다. 🏃🏃 그동안 최단거리를 구할 때 죽어라고 BFS를 이용해왔으나(제일 재밌는걸요), 가중치가 있는 상황에서는 항상 풀이가 까다로웠습니다. 저는 이제까지 BFS의 다음 노드 탐색 과정에서 가중치가 더 적은 노드의 탐색을 단순히 '코드 상으로 더 위쪽에' 작성함으로서 먼저 탐색하도록 했습니다. 이는 나름 괜찮은 방법이였지만, 당연히 한계가 있었습니다. 이럴 때 사용 할 수 있는 것이 '최단 경로 알고리즘'입니다. 가중치가 더 적은 쪽을 우선적으로 탐색하도록 하는 알고리즘이죠. 1. 다익스트라 알고리즘: 가중치가 있는 그래프 탐색의 최단 경로 찾기. 셋 중에 가장 빠름! 2. 벨만-포드 알고리즘: 음수 가중치가 있는 그래프 탐색의 ..
https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net [백준 5719] 거의 최단 경로 (platinum 5) 거의 최단 경로 문제는 최단경로를 제외한 경로들 중 가장 짧은 경로를 찾아 그 길이를 출력하는 문제입니다. 최단 경로를 알아내는 과정이 여러번 필요할 것으로 예상되므로, 최단 경로 알고리즘 중 저에게 가장 익숙한 다익스트라 알고리즘으로 풀어보겠습니다. (저는 그래프 관련 알고리즘 중에 다익스트라가 제일 재미있는..
