DFS와 BFS 이번 포스팅에서는 DFS와 BFS에 대해서 자세히 설명하도록 하겠습니다. DFS(Depth First Search) : 깊이 우선 탐색 DFS는 맹목적 탐색 방법의 하나로 탐색 트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식 노드를 첨가하며, 첨가된 자식 노드가 목표 노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 나가는 방식입니다. 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식입니다. 대표적으로 백트래킹(부모 노드로 되돌아오는 과정)에 사용합니다. 일반적으로 재귀 호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하..

에라토스테네스의 체 수학자 에라토스테네스가 발견한 소수를 찾는 방법입니다. 2의 배수부터 시작 하여 10의 자리 미만 까지 배수를 체크한 후 나머지 체크가 안된 부분이 소수라고 말할 수 있습니다.(소수는 n의 배수가 아니여야합니다.) 다음과 같이 구현이 가능합니다. 첫번째 for문에서 (i*i

Eulerian circuit 오일러 회로는 그래프에 존재하는 모든 Edge를 정확히 1번씩만 방문하는 연속된 경로입니다. 이때, 시작점과 도착점이 같아야 합니다. 또한, 한 컴포넌트에 존재하여야 하며 각 Vertex의 Degree가 짝수개여야합니다. 구현 코드 문제를 바탕으로 구현한 것이므로, 다른 문제에 맞게 변형하여서 사용하면 됩니다.

Flood Fill 플러드 필 혹인 시드 필은 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘입니다. 이 알고리즘은 그림 프로그램에서 연결될 비슷한 색을 가지는 영역에 "채우기" 도구에 사용되며, 바둑이나 지뢰찾기 같은 게임에서 어떤 비어 있는 칸을 표시 할 지 결정할 때에도 사용됩니다. 구현 코드 문제 풀이 방법에서 만든 코드이며, 문제 유형에 맞게 사용하면 됩니다.

그래프 - SCC SCC란? SCC(Strongly Connected Component)는 방향 그래프에서 임의의 두 정점 U,V가 있을때, U->V로 가는 경로가 존재한다면 그 그룹은 SCC라 부를 수 있습니다. 이때, U->V로 가는 경로는 직, 간접적인 경로를 의미합니다. SCC의 특징 1. 같은 SCC내에서 뽑은 임의의 U,V점에서 U->V 혹은 V->U의 경로(직/간접적)는 항상 존재합니다. 2. SCC는 Maximal한 성질을 가지고 있어 SCC가 형성된다면 형성될 수 있는 가장 큰 집합으로 형성이됩니다. --강한결합요소끼리는 서로 일방향적으로 연결되어 있습니다. 구현 코드 참고 : https://www.crocus.co.kr/950

위상정렬(Topological Sort) 위상정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미합니다. 위상정렬을 가장 잘 설명해 줄수 있는 예로 대학의 선수과목 구조를 들 수 있습니다. 만약 특정 수강과목에 선수 과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있습니다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상정렬을 이용할 수 있습니다. 정렬의 순서는 유향 그래프의 구조에 따라 여러개의 종류가 나올 수 있습니다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야합니다. 즉, 그래..