너비 우선 탐색이 시작 정점에서 시작하여 점차 탐색 범위를 넓혀 나가는 방식이라면, 깊이 우선 탐색은 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식이다.깊이 우선 탐색 깊이 우선 탐색은 시작 정점을 경계에 추가하는 것으로 시작한다. 너비 우선 탐색의 그림 예를 변형해서 가져왔다. 하나의 지점에서 시작하여 가능한 멀리 있는 정점에 도달하고 재귀하는 방식을 가진다.구현 깊이 우선 탐색은 두 가지의 코드를 사용할 수 있다. 1. Stack를 이용한 깊이 우선 탐색 2. 재귀 함수를 이용한 깊이 우선 탐색 이 두 가지가 있다. (1) #include #include #include using namespace std; bool visited[9]; vector ..

그래프 순회 문제란 특정 정점에서 시작하여 나머지 모든 정점을 방문하는 문제를 그래프 문제라고 한다.그래프 순회 문제는 그래프에서 특정 정점을 찾기 위한 용도로 사용할 수 있기 때문에 그래프 탐색 문제(graph search problem)라고 부르기도 한다. 오늘 알아볼 것은 여러 그래프 탐색 알고리즘 중 하나인 너비 우선 탐색에 대한 내용이다.너비 우선 탐색 너비 우선 탐색(BFS)은 시작 정점을 경계에 추가하는 것으로 시작한다.(1)의 검정 동그라미가 시작정점이라고 했을 때 퍼져나가는 모습을 표현했다. 그림 예 (1) (2) (3) (4) (5) 즉 이렇게 시작 지점에서 경계에 인접한 정점을 반복적으로 탐색하는 방법을 가진다.이렇게 되면 전체 그래프를 순회할 수 있게 된다.구현 #include #i..

탐욕 알고리즘이라고도 불리는 그리디 알고리즘이 있다.그리디 알고리즘은 항상 각 단계에 있어서 가장 좋을 거라 생각되는 선택을 한다. 다시 말해 이 선택이 전체적으로 최적해로 안내하게 될 거라는 바람을 가지고 부분적으로 최적인 선택을 한다. 그리디 알고리즘의 접근 과정selection procedure: 현재 상태에서 가장 greedy한 선택으로 해를 결정feasibility check: 결정한 해의 적절성 검사solution check: 해의 최적성 검사https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 탐욕 알고리즘(Gr..

소수(Prime Number)란 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다.https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0) 소수 (수론) - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 각각의 자리에 놓인 숫자와 소수점을 통해 나타낸 실수(小數)에 대해서는 소수 (기수법) 문서를 참고하십시오. 좌측은 소수, 우측은 합성수. ...소수란 1보다 큰ko.wikipedia.org소수만 구하는 알고리즘 풀이12부터 n까지 나눠보고 나머지가 0이 안나오게 되면 소수가 되는 방법이다. 이 경우에는 시간 복잡도가 O(n)이 된다.bool isPrime(int n) { for (int i = 2; i..