프로그래밍/알고리즘 (2) 썸네일형 리스트형 BFS의 기본 방식 1. 첫번째 경로의 좌표를 큐 A에 넣는다. 2. 인접한 노드들의 좌표를 또다른 큐 B에 넣는다. 이때, 중복해서 같은 노드가 큐에 들어가는것을 방지하기 위하여 방문한 노드들을 리스트에 넣어 처리한다. 3. 큐 B에 있는 좌표들을 큐 A로 옮긴다. 4. 큐A가 빌때까지 2의 과정을 반복한다. 5. 더이상 큐 B에 들어가는 좌표가 없거나, 혹은 목표 지점을 큐A가 발견했을시 반복을 종료한다. 피보나치 수열을 표현하는 2가지 방법 1. 재귀함수를 통한 표현 방법 1 2 3 4 5 6 7 def fibo(n): if n == 0: return 0 elif n == 1: return 1 else: return fibo(n-1) + fibo(n-2) cs 기본적으로 사용되는 피보나치 함수이다. 하지만 이 함수는 하나의 함수호출이 다른 두개의 함수 호출로 나뉘어지는 바이너리 형태이다. 따라서 시간 복잡도는 O(2^n)로 n이 커질수록 결과를 가져오는 시간이 급증한다. 2. 반복문을 통한 표현 방법 1 2 3 4 5 6 7 8 9 def fibo(n): zero = 1 one = 0 tmp = 0 for _ in range(n): tmp = one one = one + zero zero = tmp return one cs 앞의 함수와 다르.. 이전 1 다음