파이썬 킹냥이😺

✅ 완전탐색 (Brute Force Search)완전탐색(Brute Force Search)은 주어진 문제의 가능한 모든 경우의 수를 모두 탐색하여 정답을 찾아내는 알고리즘입니다. 모든 경우를 검토하므로, 해결책을 반드시 찾을 수 있지만, 경우의 수가 많을 경우 실행 시간이 급격히 증가하는 단점이 있습니다.완전탐색은 매우 직관적이고 간단한 접근 방식으로, 작은 문제나 계산량이 적은 경우에 유용하지만, 입력 크기가 커지면 비효율적입니다.항목내용알고리즘 정의가능한 모든 경우의 수를 다 확인하는 방식특징1. 간단한 구현 2. 항상 정답을 찾을 수 있음 3. 비효율적시간 복잡도O(n!) 또는 O(2^n), 경우의 수에 비례적합한 경우작은 문제나 다른 방법이 없을 때 유용단점입력 크기가 커질수록 시간이 급격히 증..

✅ Counting Sort(카운팅 정렬)시간 복잡도: O(n + k) 카운팅 정렬(Counting Sort)은 정수나 범위가 제한된 값을 정렬할 때 매우 효율적인 알고리즘입니다. 특히 값이 작고 범위가 제한적일 때 매우 빠르게 동작합니다. 카운팅 정렬은 비교 기반 정렬 알고리즘이 아니며, 대신 각 숫자의 등장 횟수를 세는 방식으로 정렬을 수행합니다.항목내용알고리즘 이름카운팅 정렬 (Counting Sort)시간 복잡도O(n + k)공간 복잡도O(k)정렬 방식비교 기반 정렬이 아닌 빈도수 기반 정렬사용 사례정수 값이나 작은 범위의 값들을 정렬할 때 유용장점- 매우 빠른 속도 (특히 값의 범위가 작을 때) - 안정적인 정렬단점- 값의 범위가 너무 크면 비효율적 - 공간 복잡도 문제 발생  ✅ 카운팅 정렬 ..

✅ Bubble Sort (버블 정렬)평균 시간복잡도 : O(n2)   버블 정렬(Bubble Sort)은 가장 간단한 정렬 알고리즘 중 하나로, 주어진 리스트에서 인접한 두 원소를 비교하고 교환하면서 정렬하는 방식입니다. 이름 그대로 버블(bubble)처럼, 가장 큰 수가 차례차례 리스트의 끝으로 "떠오르는" 모습을 비유하여 붙여졌습니다. 항목설명알고리즘 유형비교 기반 정렬시간 복잡도최악: O(n^2) 최선: O(n) 평균: O(n^2)공간 복잡도O(1)안정성안정적인 정렬적용데이터가 적고, 이미 정렬된 경우 최적화 가능단점큰 데이터에서 비효율적, O(n2)O(n^2)O(n2) 시간 복잡도 ✅버블정렬 특징버블 정렬의 동작 원리는 크게 반복문을 통한 비교와 교환으로 이루어집니다. 각 단계에서 가장 큰 수가..

✅ Time Complexity(시간복잡도)알고리즘이 문제를 해결하는 데 걸리는 시간을 입력 크기에 따라 분석한 것입니다. 간단히 말해서, 주어진 알고리즘이 처리해야 할 데이터의 양이 커질수록, 그 알고리즘이 얼마나 더 오래 걸리는지를 나타내는 척도입니다. 시간 복잡도를 잘 이해하면, 프로그램을 더 효율적으로 만들 수 있습니다. 시간복잡도 분석 알고리즘의 성능을 분석할 때, 주로 입력 크기(n)에 대한 함수로 표현합니다. 예를 들어, 입력 크기가 두 배가 되면 알고리즘의 실행 시간이 어떻게 변하는지 알 수 있습니다. 가장 일반적인 시간 복잡도는 빅오 표기법(Big-O Notation)을 사용하여 나타냅니다. ✅ 빅오 표기법 표시간 복잡도설명 예시알고리즘O(1)상수 시간 – 입력 크기와 관계없이 실행 시간..

✅ Dynamic Programming:동적 계획법(DP, Dynamic Programming)은 큰 문제를 작은 문제로 나누고, 작은 문제들의 결과를 저장하여 같은 문제를 중복 계산하지 않도록 하는 알고리즘 기법입니다. 그리디 알고리즘 처럼 최적화 알고리즘이다. DP 알고리즘 순서문제를 DP로 풀 수 있는지 확인 1. 최적 부분 구조 : 큰 문제의 최적해가 작은 문제들의 최적해로 구성될 수 있어야한다.ex ) fib(n) = fib(n-1) + fib(n-2)2. 중복되는 부분 문제 (Overlapping   #Top-Down 방식def fibo_memo(n, memo={}): if n # Bottom-up 방식def fibo2(n): f = [0] * (n + 1) # 크기가 (n+1)..

✅ Memoization: 함수가 한 번 계산한 결과를 저장해두고, 같은 입력이 들어오면 저장된 결과를 바로 사용하는 기법입니다.이렇게 하면 이미 계산한 값을 재계산하지 않아도 되므로 시간 복잡도를 크게 줄일 수 있습니다.  Memoization을 사용하는 이유 중복 계산 방지:피보나치 수열처럼 같은 부분 문제를 여러 번 계산해야 하는 경우에 유용합니다.Memoization을 쓰면 한 번 계산한 결과를 저장해 놓기 때문에, 동일한 입력이 다시 들어올 때 이미 계산해 둔 값을 그대로 돌려줄 수 있습니다. 그 결과 같은 입력에 대해 중복으로 계산할 필요가 없어 실행 시간을 크게 줄일 수 있습니다. 시간 복잡도 감소:단순 재귀로 피보나치를 구하면 지수 시간(O(2^n))이 걸리지만, Memoization을 적..

기본 예제# 스택을 구현해 봅시다.# 구현한 스택을 이용하여 3개의 데이터를 스택에 저장하고 다시 3번꺼내서 출력해봅니다.#간단한 스택top = -1stack = [0] * 10top += 1 # push(1)stack[top] = 1top += 1 # push(2)stack[top] = 2top += 1 # push(3)stack[top] = 3top -= 1 #pop()print(stack[top+1])top -= 1 #pop()print(stack[top+1])top -= 1 #pop()print(stack[top+1])  Stack의 활용 : 백준 9012번 괄호 https://www.acmicpc.net/problem/9012import sysdef is_valid_parentheses(stri..