우당탕탕 개발일지

함수 안에서 함수 자기자신을 호출하는 방식 보통 알고리즘에 따라서 반복문으로 구현한 코드보다 재귀호출로 구현한 코드가 좀 더 직관적이고 이해하기 쉬운 경우가 많음 파이썬 최대 재귀깊이 1000 재귀호출과 스택 넘침 현상 - 함수가 자기자신을 계속 호출하다가 최대 깊이(1000)를 초과하면 RecursiveError가 발생 재귀호출에 종료 조건 만들기 def hello(count): if count == 0: return print('Hello, world!', count) count -=1 hello(count) hello(5) 피보나치 수열 - 재귀는 거꾸로 생각해야 한다(ex. fib(6)을 구하려면 fib(5) + fib(4)가 필요하다), 역산 1 1 2 3 5 8 13 21 ... f(n) = ..

시간복잡도 O(N^2) 삽입 정렬, 버블 정렬, 선택 정렬 삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 방법으로 문제를 해결 다른 정렬은 무조건 위치를 바꾸는 방식이라면 삽입 정렬은 필요할 때만 위치를 바꿈 -> 버블정렬과 선택정렬보다 더 빠름 -> 시간복잡도 O(N^2)알고리즘 3가지 중에 가장 강력한 알고리즘 1 10 5 8 7 6 4 3 2 9 삽입 정렬 과정 1 10 5 8 7 6 4 3 2 9 - 1은 이미 맨 앞에 있기 때문에 넘어감 - 10은 1 앞과 뒤 중에 뒤로 _ 1 _ 10 5 8 7 6 4 3 2 9 => 1 10 5 8 7 6 4 3 2 9 - 5는 1과 10사이 _ 1 _ 10 _ 5 8 7 6 4 3 2 9 => 1 5 10 8 7 6 4 3 2 9 - _ 1 _ 5 _ 10..

스택 (Stack) 박스구조와 같음 선입후출 큐 (Queue) 입구와 출구가 모두 뚫려있는 형태 선입선출 재귀함수 (Recursive Function) 자기자신을 다시 호출하는 함수 반복문을 이용하여 동일한 기능을 구현할 수 있음 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임 그래서 스택을 사용해야 할 때 스택 라이브러리 대신에 재귀 함수를 이용하는 경우 많음 DFS (Depth-First-Search) 깊이우선 탐색 그래프의 깊은 부분을 우선 탐색하는 알고리즘 스택 자료구조(혹은 재귀 함수)를 이용 구체적인 동작과정 1. 탐색 시작 노드를 스택에 삽입하고 방문처리 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리 방문하..