프로그래밍/Algorithm (3) 썸네일형 리스트형 너비 우선 탐색(BFS: Breadth First Search) 너비 우선 탐색(BFS)란? 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법 큐를 이용해서 지금 위치에서 갈 수 있는 곳을 모두 큐에 넣는 방식 큐에 넣을 때 방문했다고 체크 모든 가중치가 1일때 최단 거리를 구하는 알고리즘 너비 우선 탐색 알고리즘 breadth_first_search(v) v를 방문되었따고 표시; 큐 Q에 정점 v를 삽입; while (not is_empty(Q)) do Q에서 정점 w를 삭제; for all u ∈ (w에 인접한 정점) do if (u가 아직 방문되지 않았으면) then u를 큐에 삽입; u를 방문되었다고 표시; 에라토스테네스의 체 에라토스테네스의 체에라토스테네스의 체는 합성수를 지우는 방식으로 소수를 찾는 방법이다.소수(Prime Number)소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 약수로 1과 자기 자신만을 가지는 정수라고 할 수 있다.합성수1과 자기 자신 이외의 약수를 가진 정수로 두개 이상의 소수의 곱이다.(비소수)동작 과정1은 제거지워지지 않은 수 중 제일 작은 2를 소수로 채택하고 2의 배수를 모두 지운다.지워지지 않은 수 중 제일 작은 3을 소수로 채택하고 나머지 3의 배수를 모두 지운다.지워지지 않은 수 중 제일 작은 수 중 제일 작은 5를 소수로 채택하고 나머지 5의 배수를 모두 지운다.이러한 과정을 반복한다.코드(Python)n = int(input()) a = [Fals.. 조합과 순열 1. 조합집합에서 일부 원소를 취해 부분집합을 만드는 방법서로 다른 n개의 원소에서 중복을 허용하지 않고 k개를 뽑는 경우의 수순서가 없음- 조합의 수(Python)1234def combination(n, r): if n == r or r == 0: return 1 else: return combination(n-1, r-1) + combination(n-1, r)combination(5, 3)Colored by Color Scriptercs- 조합 출력(Python)123456789101112def combination(comArr, n, r, index, target, arr): if r==0:print(comArr) elif target==n: return else: comArr[index] = a.. 이전 1 다음