문제 https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1번 정점에서 K 이하의 거리인 정점의 개수를 구하는 문제였다. 문제 풀이 1번 정점에서 각 정점까지의 거리를 구하는 문제여서 다익스트라로 풀면 더 효율적이겠지만, N의 최댓값이 50이어서 플루이드를 사용해 풀었다. #include #include #include using namespace std; int dist[51][51]; int solution(int N, vector road, ..
문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 각 N에 대해 N → X → N 최단 경로를 구하고, 각 최단 경로 중 최댓값을 구하는 문제였다. 문제 풀이 N이 1000까지여서 플로이드 워셜 알고리즘을 이용해 풀었다. 최댓값은 이전 문제를 풀 때 정한 값이다. 이 문제에서는 100 * 10000보다 큰 값이면 돼서 이전에 사용하던 값을 그대로 사용했다. #define _CRT_SECURE_NO_WARNING..
문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 1 → u → v → N (혹은 1 → v → u → N)의 최단 경로의 길이를 찾는 문제였다. 문제 풀이 플루이드 워셜 알고리즘을 이용해 풀었다. 처음에 1 → u → v → N 경우에 대해서만 최솟값을 찾아줘서 틀렸는데 1 → v → u → N 경우와도 비교해 최솟값을 구해서 맞췄다. MAX_INT 값은 간선의 최대 길이인 1000 * 간선의 ..
최단 경로 알고리즘은 다익스트라, 플로이드 워셜, 벨만 포드 알고리즘이 있는데 이를 각각 구현하는 포스트는 다음에 올리겠다. 한 지점에서 특정 지점까지의 최단 경로를 구할 때에는 다익스트라를, 모든 지점에서 모든 지점까지의 최단 경로를 구할 때는 플로이드 워셜을, 다익스트라와 같은 경우지만 음의 가중치를 가진 간선이 존재할 경우 벨만 포드 알고리즘을 사용하면 된다. 미래 도시 방향이 없고 가중치가 없는 그래프로 1번 회사에서 K번 회사로, K번 회사에서 X번 회사로 가는 최단 경로를 구하는 문제였다. 나는 이 문제를 1번부터 K번, K번부터 X번까지의 최단 경로를 다익스트라를 이용해 구한 후 두 개의 값을 더해서 풀었는데 책에서는 전형적인 플로이드 워셜 유형의 문제라고 했다. 노드와 간선의 개수가 100..
다익스트라 알고리즘 최소 비용을 구해야 할 때 사용 가능 한 지점에서 다른 특정 지점까지의 최단 경로 구해야 할 경우에 사용 가능 음의 간선이 없을 때 정상 동작함 (현실에는 음의 간선의 길이 없어서 GPS의 기본 알고리즘으로 사용됨) 그리디 알고리즘 -> 매번 가장 비용이 적은 노드를 선택해 과정을 반복함 동작 원리 dist[] 에 비용 저장, INF로 초기화 되어 있음 출발 노드 설정, 최단 거리 초기화 (dist[] INF로 초기화) 출발 노드를 방문한 노드로 체크하기 출발 노드와 연결되어 있고 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택, 방문했다고 체크 이 노드에서 다른 노드로 가는 비용을 계산해 dist[] 갱신 3,4 과정을 반복 구현 방법 동작 원리대로 구현하기 - 시간 복잡..
