우당탕탕 개발일지

함수 안에서 함수 자기자신을 호출하는 방식 보통 알고리즘에 따라서 반복문으로 구현한 코드보다 재귀호출로 구현한 코드가 좀 더 직관적이고 이해하기 쉬운 경우가 많음 파이썬 최대 재귀깊이 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(1) - push, pop an stack - access hash table O(log n) - Binary Search, Tree Access, Search, Insertion, Deletion O(n) - traverse tree - traverse linked list O(nlog n) - Quick, Merge, Heap sort O(n^2) - Insertion -Bubble -Selection 최상 : 오메가 표기법 (Big-Ω Notation) 평균 : 세타 표기법 (Big-θ Notation) 최악 : 빅오 표기법 (Big-O Notation) 빅오표기법의 성능(수행시간, 연산횟수) O(1) < O(log n) < O(n) < O(n * log n) < O(n²) < O(n³) < O..

이진탐색(Binary Search) 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 시작점, 끝점, 중간점을 이용해 탐색범위를 정한다 이진탐색 알고리즘은 배열의 데이터가 정렬(오름차순, 내림차순)되어 있을 때 선형검색보다 빠르게 검색할 수 있다 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는 예시 [Step 1] 시작점: 0 끝점: 9 중간점:4(소수점 이하 제거) 중간점에 2개가 있는 경우 소수점을 제거해서 중간점을 선정 찾고자 하는 위치(4)보다 중간점(8)이 크다면 중간점을 포함한 오른쪽의 것들은 확인할 필요 없음 [Step 1] 시작점:0, 끝점:3, 중간점:1 찾고자 하는 위치(4)가 중간점(1)보다 커서 시작점부터 중간점까지는 확인할 필요 없음 [Step..

시간복잡도 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..

📌 아래와 같은 순서로 작성되었습니다. - 다이나믹 프로그래밍 개요 - 다이나믹 프로그래밍(DP)이란? - 다이나믹 프로그래밍 사용 조건 - 피보나치 수열 - 피보나치 수열 - 피보나치 수열 시간복잡도 - 메모이제이션(Memoization) - 메모이제이션(Memoization) - 탑다운 vs 보텀업 - 메모이제이션을 활용해 피보나치 수열을 해결해보면? - 다이나믹 프로그래밍 vs 분할 정복 다이나믹 프로그래밍(DP)이란? 메모리를 적절히 사용해 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과는 별도의 메모리 영역에 저장해 다시 계산하지 않도록 함 일반적으로 두 가지 방식(탑다운, 보텀업)으로 구성 동적계획법이라고도 부름 다이나믹 프로그래밍 사용 조건 최적 부분 구조 : 큰 문제를 작은..

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