Algorithm10 Stack 목록Stack이란?Python에서 Stack 구현 방법✏️ 연습 문제📚 Stack후입선출(LIFO, Last In, First Out) 구조를 가진 자료구조💡 가장 나중에 삽입된 데이터가 가장 먼저 삭제됩니다! 스택의 주요 연산push(x): 스택의 맨 위에 요소 x를 추가한다.pop(): 스택의 맨 위 요소를 제거하고 반환한다.top() / peek(): 스택의 맨 위 요소를 제거하지 않고 반환한다.size(): 스택에 포함된 요소의 개수를 반환한다.isEmpty(): 스택이 비어 있는지 확인한다.Python에서 Stack 구현 방법Python에서는 내장 자료구조인 list 를 사용해 스택을 구현할 수 있습니다.스택 정의Python의 list를 사용해 stack을 선언합니다.stack = [] # .. 2025. 2. 19. Sieve of Eratosthenes 목차소수(Prime Number)란?소수 판별법(Prime Number Checking)에라토스테네스의 채 (Sieve of Eratosthenes)✏️ 연습 문제소수(Prime Number)란?1과 자기 자신 이외의 약수를 갖지 않는 2이상의 자연수 ex) 2. 3. 5. 7. 11. 13, ….⚠️1은 소수가 아닙니다.소수 판별법(Prime Number Checking)주어진 수가 소수인지 어떻게 알 수 있을까요?1. 전부 나누어 보기2부터 N - 1로 나누어 떨어지는지 확인하는 방법입니다.시간 복잡도는 O(N)입니다.def is_prime(n): # 1은 소수가 아니므로 제외 if n 2. 홀수로 나누어보기수의 절반은 짝수입니다.2를 제외한 모든 짝수는 소수가 아니므로 홀수로만 나누어 봅.. 2025. 2. 19. Euclidean Algorithm 목차유클리드 호제법 (Euclidean Algorithm)확장 : GCD와 LCM의 관계math.gcd / math.lcm✏️ 연습 문제유클리드 호제법 (Euclidean Algorithm)두 수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘원리두 수 a와 b 의 최대공약수는 a를 b로 나눈 나머지 r과 b의 최대공약수와 같습니다.즉, GCD(a, b) = GCD(b, a % b)가 성립합니다. 💡나머지가 0이 될 때 탐색을 종료합니다def gcd(a, b): return a if b == 0 else gcd(b, a % b)# 예제print(gcd(48, 18)) # 출력: 6⌛ 시간 복잡도유클리드 호제법의 시간 복잡도는 a > b에 대해 최대 b의 자릿수.. 2025. 2. 19. LCA, (Lowest Common Ancestor, 최소 공통 조상) 트리에서 두 노드 u, v의 가장 가까운 공통 조상을 찾는 알고리즘💡공통 조상이란?두 노드가 공통으로 공유하는 조상 노드의 집합= 루트 노트에서 두 노드로 가는 경로가 만나는 노드의 집합 트리에서 LCA를 찾아보자! 1 / \ 2 3 / \ \ 4 5 6 / \ 8 92, 3의 LCA : 18, 5의 LCA : 24, 8의 LCA : 4🔄 동작 원리LCA를 찾는 일반적인 방법은 다음과 같습니다.깊이 맞추기 두 노드의 깊이가 다를 경우, 깊이가 더 깊은 노드를 조상 방향으로 올려 깊이를 맞춥니다.공통 조상 찾기 두 노드가 같아질 때 까지 두 부모를 따라 올라가며 비교합니다.최종 공통 조상 반환 가장 먼저 발견된 공통 조상을 반환합니다... 2025. 1. 25. Recursive Call 재귀 호출(Recursive Call)자기 자신을 호출하는 방식왜 Recursive Call이 필요할까요?미로를 탈출한다고 생각해봅시다. 막다른 길에 도달하면 이전 갈림길로 돌아가 다른 경로를 시도해야 합니다.이처럼 여러 선택지를 모두 시도해야 할 때, 실패한 경우 이전 상태로 되돌아가는(backtracking) 과정이 필요합니다.재귀 호출은 함수가 종료되기 전까지 상태를 유지하므로, 각 단계의 상태를(스택 구조로) 자동으로 기억합니다.💡하나의 선택지가 끝나면 이전 상태로 돌아가 다른 선택지를 시도할 수 있습니다.💡하나의 큰 문제를 여러 작은 문제로 분리하거나, 반복문보다 직관적이고 간결한 코드 작성이 가능합니다. 🔄 동작 원리피보나치 수열을 통해 재귀 호출의 동작 원리를 살펴봅시다.피보나치 수열이.. 2024. 11. 23. [파이썬 자료구조와 알고리즘 for Beginner] 연습문제 6 정답 연습문제 1. 종이컵을 스택에 넣는 동작과 거리가 먼 것은? (4) 종이컵은 가장 먼저 들어간 것이 가장 먼저 나온다. 2. 다음 중 스택의 삽입과 추출에서 사용되는 용어 세 가지를 고르시오. top, push, pop 3. 스택에서 데이터를 (1)은 삽입하는 코드고, (2)는 추출하는 코드다. 모두 top과 관련된 코드다. (1)~(2)를 채우시오. (1) top += 0 (2) top -= 1 4. 스택이 꽉 찼는지 확인하는 함수다. (1)에 적합한 코드는? (2) top == SIZE - 1 5. 스택이 비었는지 체크하는 함수다. (1)에 적합한 코드는? (2) top == -1 6. 스택에서 다음에 나올 데이터를 확인만 하는 함수다. (1)~(2)에 적합한 코드는? (1) return None (.. 2024. 4. 1.
