알고리즘

최소 신장 트리란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다.사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하면 사용할 수 없다.N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개

벨만-포드 벨만포드 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 주요 특징은 다음과 같다. 기능 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색 특징 음수 가중치 에지가 있어도 수행할 수 있다. 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수

플로이드-워셜 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.모든 노드 간에 최단 경로 탐색음수 가중치 에지가 있어도 수행할 수 있다.동적 계획법의 원리를 이용해 알고리즘에 접근한다.O(V^3)로 느린 편이라서 노드의 갯수를 잘 보고 사용해야할 알고리즘이다.A노

조합은 n개의 숫자에서 r개를 뽑는 경우의 수를 뜻한다.순열은 n개의 숫자 중 r개를 뽑아 순서를 고려해 나열할 경우의 수를 이야기 한다.ex) 5개의 데이터에서 3개를 선택하는 조합의 경우의 수를 구하여라위 문제의 경우 5개 중 4개의 데이터의 선택 여부가 결정되었다

문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법이다.큰 문제를 작은 문제로 나눌 수 있어야 한다.작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야한다.모든 작은 문제들은 한 번

문제를 해결해나가다가 이게 답이 될 수 없다고 판단하면 되돌아가는 방식이다.그 방향으로 나아가지 않고 되돌아가는 것을 가지치기라고 한다.이 가지치기를 하게 될 조건을 잘 생각해야하는 것이 포인트이다.보통 모든 경우의 수를 탐색해야할 경우에 유용하게 쓰인다.상태를 트리로