- [ 알고리즘 ][알고리즘] DFS(Depth-First-Search, 깊이 우선 탐색)2024-08-13 15:07:20DFS란? 그래프 탐색 알고리즘으로 그래프의 모든 정점(vertex)을 깊이 탐색하는 방법(알고리즘) DFS는 시작 정점에서 인접한 정점들을 방문하고, 인접 정점들의 인접 정점을 방문하는 방식으로 동작한다.BFS와 다르게 하나의 경로를 깊이(끝)까지 탐색한 후에야 다른 경로로 되돌아와 탐색을 진행한다. 표현 방법// 인접 리스트1 - [2, 8]2 - [1, 3, 6, 7]3 - [2, 4, 5]4 - [3, 5]5 - [3]6 - [2]7 - [2]8 - [1, 9]9 - [8]// 인접 행렬 1 2 3 4 5 6 7 8 91 [0 1 0 0 0 0 0 1 0]2 [1 0 1 0 0 1 1 0 0]3 [0 1 0 1 1 0 0 0 0]4 [0 0 1 0 1 0 0 0 0]5 [0 0 1 1 0 0..
- [ 알고리즘 ][알고리즘] 에스토스테네스의 체 (소수 판별 알고리즘)2024-08-08 16:12:47에스토스테네스의 체? 소수를 찾기 위한 고전적인 알고리즘으로일반적으로 수를 하나씩 체크하며 소수를 판별하는 것은 비효율적이기 때문에 에스토스테네스의 체 알고리즘을 사용하면 좋다. 원리 [1 ... 50]까지 존재한다고 가정하였을 때동일한 크기의 Bool 타입의 true로 가득 찬 배열을 생성한다. [1 ... 50]* 지워준다 == false로 변환여기서 2부터 배수를 지워준다. 이 후 다음 3의 배수를 지워준다. 4의 배수는 이미 2의 배수에서 지워졌다이렇게 계속 배수를 지워주는데, 언제까지 지워주는지가 중요할 것이다.50의 경우 제곱근이 7.0****이 나오게 된다. 이때 50보다 작은 수 중 소수가 아닌(m)은 m = a * b가 된다. (a 이때 a는 무조건 50의 제곱근 7.0*****보다 작게..