어차피 공부는 해야한다./알고리즘4 TSP(외판원의 순회) 알고리즘 오늘은 문제를 풀다가 TSP(Traveling Salesman problem) 알고리즘을 공부하게 되었습니다. 문제 : https://www.acmicpc.net/problem/2098 TSP 알고리즘은 "특정 출발점에서 모든 점을 순회하여 다시 출발점으로 돌아오는 최단 거리"를 구하는 알고리즘입니다. 처음 이 문제에 대해 접근할 때, 각 출발점에 대해 최단 순회 경로를 구하는 것이 당연하다고 생각했었습니다. 하지만 위 그래프를 2차원 배열로 바꿔서 생각해보면, 이런 2차원 형태에서, 순환이 가능한 조합은 위 2차원 배열에 row 당 하나의 체스의 록을 넣을 수 있는 경우와 같습니다. 예로 1 >2 >3 >5 > 4 >1 의 순환이나 2 > 3 > 5 > 4 > 1 > 2 은 같은 값을 가지게 됩니.. 2024. 10. 24. 밸만 포드 알고리즘과 다이젝스트라 알고리즘 오늘 문제를 풀다가 밸만 포드 알고리즘을 공부하게 되었습니다. 그래서 벨만 포드 알고리즘을 사용하여 문제를 풀던 도중 저의 얇은 지식으로 인한 구현 오류에 대해 작성하기로 했습니다. 우선 다이젝스트라 알고리즘에 대해 간단하게 말하자면, 간선이 양수인 경우 특정 지점에서 다른 모든 지점까지의 거리를 구할 수 있는 알고리즘 입니다. "노드 u에 대한 최단 거리의 예상 값은 = v까지의 최단 거리 + u와 v의 거리" 의 원리를 사용하여 최단거리를 구합니다. 최단거리의 예상 값인 이유는 u에 연결된 노드가 많을 수 있기 때문입니다. 이와 같은 비교는 우선순위 큐를 통해 쉽게 구현이 가능합니다. public static int[] Dijkstra(List> map, int node,int start){.. 2024. 10. 15. 코사라주 알고리즘 - SCC 알고리즘 최근 SCC에 대해 공부하면서 SCC를 구하는 알고리즘은 대표적으로 지난번 공부한 타잔 알고리즘과 코사라주 알고리즘이 있다는 것을 알게 되었습니다. 절대 타잔 알고리즘이 복잡해서가 아니고, 순수하게 학문적인 호기심이 들어서 코사라주 알고리즘을 공부해 보기로 하였습니다. 그럼 아래 그래프의 SCC를 코사라주 알고리즘을 통해 구해보도록 하겠습니다.우선 DFS의 진행 순서를 생각해 보면 1, 2, 3, 4, 5 입니다. 그럼 함수가 종료되는 (탐색이 끝난 노드?) 순서를 생각해보면 4, 3, 5, 2, 1 이렇게 되겠네요. 여기서 주목해야 할 부분은 2입니다. 위 탐색에서 2번 노드에서 갈 수 있는 노드들은 모두 2번 노드보다 빨리 함수가 종료되게 됩니다. (4, 3, 5 노드) 이제 역방향 그래프가 필요합니.. 2024. 8. 6. [Graph] SCC 알고리즘 - 타잔 알고리즘, 백준 2150번 오늘 코테 문제를 풀다 방향이 있는 그래프에서 Loop의 유무를 검증해야 하는 문제를 만났습니다. 늘 어렴풋이 만 알고 있던 SCC와 WCC에 대해 정리해 보고 공부하기로 했습니다. SCC ( Strongly Connected Components )이는 방향성이 있는 그래프에서 출발점과 도착점이 같아지는 경우를 의미합니다. 백문이 불여일견 그림을 보면 바로 알 수 있습니다. 위와 같은 그래프에서 2 - 3 - 4 - 2 으로 2번에서 시작에서 2번으로 도착하는 경우 SCC라고 합니다. 물론 3 - 4 - 3 도 SCC라고 할 수 있습니다. 알고리즘SCC를 출발점과 도착점이 같아지는 경우 라고 설명한 이유는 알고리즘을 구현할 때 가장 포인트가 되는 조건이라고 생각하기 때문입니다. 위 문장은 탐색 중.. 2024. 7. 31. 이전 1 다음
