소수 판별 Intro 코딩테스트 문제를 풀다보면 가끔 소수 판별하는 문제가 나옵니다. 소수는 간단하게 정의하자면 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수입니다. 수학 시간에 소수를 많이 다뤘다보니 수를 보면 이 수는 소수인지 아닌지는 작은 수면 바로 판별이 가능하지만 이를 알고리즘으로 바꾸는 것은 좀 어려웠습니다. 다행히 소수 판별 문제를 해결하기 위한 대표적인 방법이 의미 정의 되어있습니다. 에라토스테네스의 체 알고리즘을 활용하는 것입니다. 이는 다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘이며 N보다 작거나 같은 모두 소수를 찾을 때 사용할 수 있습니다....
0. Spanning Tree Spanning Tree란 그래프 내의 모든 정점을 포함하는 트리입니다. 즉, 그래프에서 일부 간선을 선택해서 만든 트리입니다. 이때 그래프에 사이클이 형성이 되면 안됩니다. 연결 그래프에 대한 spanning tree는 여러개 일 수 있습니다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 spanning tree가 됩니다. 따라서 spanning tree는 그래프에 있는 n개의 정점을 (n-1)개의 간선으로 연결합니다. 1. Minimum Spanning Tree (MST) MST는 트리를 구성하는 간선들의 가중치를 합한 것이 최소가 되는 신장 트리이며 다음의 조건을 충족해야합니다....
Graph Search graph search 방법에는 DFS, BFS 2가지 종류가 있다. DFS(Depth-First-Search) 정의 root node 혹은 다른 임의의 node에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식이다. binary tree를 순회할 때 사용했던 다음의 순회 방법이 DFS에 속한다. inorder preorder postorder 구현 방법 stack을 이용해서 구현 처음에는 스택에 노드가 없으니깐 시작할 노드를 넣는다. stack에서 노드를 하나 꺼내서 해당 node의 child node를 전부 스택에 넣고 꺼낸 노드는 출력한다. child node를 stack에 넣을 때 한번 stack에 넣었던 node는 다시 넣지 않는다....