77H발 블로그

[Algorithm] 재귀 함수(Recursion Function)

1. 재귀 함수(Recursion Function) 란?재귀 함수 란?함수 내부에서 자기 자신을 다시 호출 함수 복잡한 문제를 "더 작은 문제"로 쪼개서 해결하는 프로그래밍 기법이다.2. 왜 반복문을 사용하지 않고 재귀함수를 사용할까? 반복문으로도 대부분의 문제를 해결할 수 있는데, 왜 굳이 재귀를 사용할까?팩토리얼: n! = n × (n−1)!피보나치 수: F(n) = F(n−1) + F(n−2)트리의 깊이: depth(node) = 1 + depth(child) 이러한 문제는 반복문으로 풀려고 하면 코드가 복잡하고 가독성이 떨어진다.그래서 사용하는 것이 재귀 함수이다.피보나치 수를 예로 반복문과 재귀함수 코드로 비교해보자. 반복문def fib_iterative(n): if n 재귀함수def ..

1. 탐색(Search) 탐색(Search)이란?여러 데이터 중에서 원하는 값을 찾는 과정 ✅ 대표적인 탐색 방법순차 탐색(Linear Search)이진 탐색(Binary Search)2. 순차 탐색(Linear Search)순차 탐색(Linear Search) 이란?데이터를 앞에서부터 하나씩 차례대로 비교하며 찾는 탐색 방법 ✅ 동작 방식[0, 3, 2, 8] 에서 8 찾기0 → X3 → X2 → X8 → O 발견 ✅ 코드 예시def linear_search(array, target): for value in array: if value == target: return True return False ✅ 시간 복잡도 O(n)→ 최악의 경우 모든 데이터..

1. Array(배열) 연속된 메모리 공간에 데이터를 저장하는 구조 메모리 연속 저장인덱스 접근 O(1) (매우 빠름)중간 삽입 · 삭제 O(N) (느림, 전체를 밀어야 함)크기 고정 (일반적으로 변경 어려움)같은 타입만 저장(언어에 따라 다름)[10][20][30][40] ← 연속된 메모리2. LinkedList각 요소(Node)가 다음 노드를 가리키는 방식으로 연결된 자료구조즉, 메모리 어디에 있어도 상관없고, 포인터(next)로 연결 메모리 불연속 저장 가능삽입 · 삭제 O(1) (포인터만 변경)인덱스 접근 O(N) (앞에서부터 순서대로 이동)메모리 사용량 높음 (next 포인터 필요)크기 제한 없음[10] → [20] → [30] → [40] → None 3. Array와 LinkedList ..

1. 알고리즘이란?어떤 문제를 해결하기 위한 절차 또는 방법즉, 어떤 문제가 있을때, 그것을 해결하기 위한 여러 동작들의 모임입니다. 2. 시간복잡도 입력 크기 N이 커질수록, 실행 시간이 얼마나 빨리 늘어나는지즉, “입력값에 비해 얼마나 일을 수행해야 하는가?” 이다.3. 공간복잡도입력 크기 N이 커질수록, 추가로 쓰는 메모리가 얼마나 늘어나는지즉, 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말한다.4. 점근표기법 알고리즘의 성능(시간, 공간 복잡도)을 수학적으로 표기하는 방법즉, “n이 충분히 커졌을 때의 성장 속도만 보자” 표기법의 종류Big-O: 상한(Upper Bound) - O(f(n)) 최대 이 정도까지 느려질 수 있다 =“이 알고리즘은 최악으로 잡아도 f(n)보다 더 빨리..