분류 전체보기84 백준 14938번: 서강그라운드 (C++) 문제링크 https://www.acmicpc.net/problem/14938 풀이방법 해당 문제는 플로이드 알고리즘을 이용하여 해결할 수 있다. 풀이 방법은 다음과 같다. 우선 플로이드 알고리즘을 구현하여 인접 배열을 통해서 특정 노드와 특정 노드 사이의 최단 거리를 모두 구한다. 또한 unordered_map을 이용하여 특정 노드의 아이템 개수를 저장해둔다. 마지막으로 시작지점 1~n 까지 각 노드로부터 수색 범위(m) 이하에 존재하는 아이템 개수를 모두 더해서 vector 에 저장해둔다. result에는 각 시작 지점 별로 수색 범위(m) 이하에 존재하는 아이템 개수를 더한 값이 들어있다. 마지막으로 result에 들어있는 값 중 가장 큰 값을 출력하면 정답이 된다. 코드 #include #inclu.. 2024. 2. 3. 백준 1504번: 특정한 최단 경로 (C++) 문제링크 https://www.acmicpc.net/problem/1504 풀이방법 해당 문제는 다익스트라 알고리즘을 이용하여 해결할 수 있다. 풀이 방법은 다음과 같다. 우선 solve라는 함수를 만들고 int st, int en을 추가해서 st 부터 en까지 최단 거리 값을 알려주는 함수를 만든다. 1~N까지의 경로 중에 v1과 v2를 반드시 지나는 경우는 딱 두 가지 케이스가 존재한다. (~~~ 중간에 다른 경로를 의미한다. 중간에 다른 경로가 없을 수도 있다.) (1) 1~~~V1을 지나고 V1부터 ~~~ V2를 거쳐서 V2~~~n에 도달하는 방법 (2) 1~~~V2를 지나고 V2부터 ~~~ V1을 거쳐서 V1~~~n에 도달하는 방법 위 두 케이스만 존재한다. 두 케이스에서 작은 값을 최종 결과 .. 2024. 2. 3. 백준 11779번: 최소비용 구하기 2 (C++) 문제링크 https://www.acmicpc.net/problem/11779 풀이방법 해당 문제는 다익스트라 알고리즘을 이용하여 해결할 수 있다. 풀이 방법은 다음과 같다. 위 설명의 시퀀스를 바탕으로 코드를 구현하여 시작점 st로부터 특정 인덱스를 가진 노드까지 최단거리를 모두 구한다. 추가적으로 위 그림처럼 시작 지점부터 끝 지점 까지 경로를 찾기 위해서 pre 배열을 선언해서 pre배열을 채우고 해당 테이블을 이용해서 경로까지 출력한다. 문제 풀이는 아래 바킹독님 강의 영상을 참고하자. https://www.youtube.com/watch?v=o9BnvwgPT-o&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=30 코드 #include using namespace.. 2024. 2. 3. 백준 1753번: 최단경로 (C++) 문제링크 https://www.acmicpc.net/problem/1753 풀이방법 해당 문제는 다익스트라 알고리즘을 이용하여 해결할 수 있다. 풀이 방법은 다음과 같다. 위 설명의 시퀀스를 바탕으로 코드를 구현하여 시작점 st로부터 특정 인덱스를 가진 노드까지 최단거리를 모두 구하여 배열에 넣는다 아래 강의를 참고하자. https://www.youtube.com/watch?v=o9BnvwgPT-o&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=30 코드 #include using namespace std; #define X first #define Y second int v,e,st; // {비용, 정점 번호} vector adj[20005]; const int IN.. 2024. 2. 3. 이전 1 ··· 3 4 5 6 7 8 9 ··· 21 다음
