코딩테스트/알고리즘

[알고리즘] DFS & BFS - 깊이우선 탐색과 너비우선 탐색

2023.03.06

:: 그래프 탐색 :: dfs와 bfs알고리즘은 대표적인 그래프 탐색 알고리즘이다. 해당 알고리즘은 코딩 테스트에 높은 비율로 출제되기 때문에 꼭 학습해야하는 알고리즘 중 하나이다. DFS(Depth First Search) - 깊이 우선 탐색 깊이 우선 탐색은 재귀를 통하여, 시작 노드부터 그래프의 제일 안쪽 노드까지 깊숙히 방문하며 그래프를 탐색하는 알고리즘이다. 다음 그림 예시를 통해 탐색과정에 대하여 알아보자 1번에서 시작하는 다음과 같은 그래프가 있다고 하자. 그래프는 수가 작은 순으로 탐색하도록 초기 값이 주어진다. 그럼 DFS로 탐색하게 되었을 때, 어떻게 탐색하게 될까? 노드에 방문할 때마다 해당 노드에 방문 처리를 하며, 1과 연결되어 있는 노드2와 노드3 중에 수가 작은 순으로 탐색을 ..

코딩테스트/알고리즘

[알고리즘] 에라토스테네스의 체 with '프로그래머스 2단계 - 소수찾기 문제'

2023.02.22

"에라토스테네스의 체" 알고리즘 문제, 특히 완전 탐색 유형을 풀다보면 아래와 같은 문제상황을 종종 마주친다. 1~n 사이에 있는 소수의 개수 구하기 보통 브루트포스를 통해 풀 수 있는데 레벨이 어느정도 되는 문제라면 시간초과가 발생하기 마련이다. 브루트포스(Brute Force)란? 직역하면 "무식한 힘" 이라는 뜻을 가진 알고리즘으로 무식하게 전체를 탐색하는 문제이다. 프루트포스를 사용하여 소수찾기 문제를 해결하면 아래와 같은 코드를 얻을 수 있다. 브루트포스 소수찾기 코드 def findSosuBF(n): sosuArr = [] for i in range(2,n+1): cnt = 0 for j in range(2,i): if i % j == 0: cnt+=1 if cnt == 0: sosuArr.a..

[알고리즘] DFS & BFS - 깊이우선 탐색과 너비우선 탐색

[알고리즘] 에라토스테네스의 체 with '프로그래머스 2단계 - 소수찾기 문제'

티스토리툴바