0과 1의 쉼터

목록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 = [] # ..

목차소수(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를 제외한 모든 짝수는 소수가 아니므로 홀수로만 나누어 봅..

목차유클리드 호제법 (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의 자릿수..

트리에서 두 노드 u, v의 가장 가까운 공통 조상을 찾는 알고리즘💡공통 조상이란?두 노드가 공통으로 공유하는 조상 노드의 집합= 루트 노트에서 두 노드로 가는 경로가 만나는 노드의 집합 트리에서 LCA를 찾아보자! 1 / \ 2 3 / \ \ 4 5 6 / \ 8 92, 3의 LCA : 18, 5의 LCA : 24, 8의 LCA : 4🔄 동작 원리LCA를 찾는 일반적인 방법은 다음과 같습니다.깊이 맞추기 두 노드의 깊이가 다를 경우, 깊이가 더 깊은 노드를 조상 방향으로 올려 깊이를 맞춥니다.공통 조상 찾기 두 노드가 같아질 때 까지 두 부모를 따라 올라가며 비교합니다.최종 공통 조상 반환 가장 먼저 발견된 공통 조상을 반환합니다...

재귀 호출(Recursive Call)자기 자신을 호출하는 방식왜 Recursive Call이 필요할까요?미로를 탈출한다고 생각해봅시다. 막다른 길에 도달하면 이전 갈림길로 돌아가 다른 경로를 시도해야 합니다.이처럼 여러 선택지를 모두 시도해야 할 때, 실패한 경우 이전 상태로 되돌아가는(backtracking) 과정이 필요합니다.재귀 호출은 함수가 종료되기 전까지 상태를 유지하므로, 각 단계의 상태를(스택 구조로) 자동으로 기억합니다.💡하나의 선택지가 끝나면 이전 상태로 돌아가 다른 선택지를 시도할 수 있습니다.💡하나의 큰 문제를 여러 작은 문제로 분리하거나, 반복문보다 직관적이고 간결한 코드 작성이 가능합니다. 🔄 동작 원리피보나치 수열을 통해 재귀 호출의 동작 원리를 살펴봅시다.피보나치 수열이..

연습문제 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 (..

연습문제 1. 원형 연결 리스트의 특징과 거리가 먼 것을 두가지 고르시오. (4) 마지막 노드의 링크는 비어있다. 2. 그림과 같은 워형 연결 리스트를 만드는 코드의 (1)을 채우시오. (1) node1.link = node1 3. 원형 연결 리스트를 삭제하는 그림이다. 정연 노드를 node2,쯔위 노드를 node3, 사나 노드를 node4라고 했을 때 다음 (1) ~ (3)을 노드 이름으로 채우시오. (1) node2 (2) node3 (3) node3 4. 원형 연결 리스트의 마지막 노드가 참이 되는 조건은? (1) current.link != head 5. 원형 연결 리스트의 첫 번째 노드를 삭제하는 코드다. (1) ~ (3)에 적합한 코드를 다음 중 고르시오. current = head last...

연습 문제 1. (1)과 (2)에 알맞는 용어를 각각 채우시오 (1) 선형 리스트는(은) 배열에 데이터를 차례대로 저장하므로 데이터의 실제 위치 순서로 데이터가 구성된다. (2) 단순 연결 리스트 에서는 데이터를 노드 단위로 삽입/삭제한다. 2. 선형 리스트와 비교한 단순 연결 리스트에 대한 설명이다. 거리가 먼 것은? (3) 중간에 새로운 데이터를 삽입할 때는 비효율적이다. → 앞뒤 노드와 연결만 하면되므로 효율적이다. 3. 노드 구조에서 (a)와 (b)를 무엇이라고 하는지 다음 중에서 고르시오 리스트, 링크, 헤드, 배열, 주소, 번지, 데이터 (a) 데이터 (b) 링크 4. 그림과 같이 노드를 생성하고 연결하는 코드를 차례대로 올바르게 나열한 것은? (2) (c) node1 = Node() (a) ..

연습문제 선형리스트는(은) 데이터를 일정한 순서로 나열한 자료구조로, 입력 순서대로 저장하는 데이터에 적당하다 다음은 선형 리스트에 데이터를 삽입하는 과정이다. 거리가 먼 것은? 맨 앞에 공간을 하나 추가해야 한다. → 맨 뒤에 마지막 위치에 바로 앞 위치의 데이터를 이동시킨다. 삽입할 위치까지 (2)를 반복한다. 삽입할 위치에 데이터를 삽입한다 다음은 선형 리스트에 데이터를 삭제하는 과정이다. 순서대로 나열하시오. 4 → 2 → 3 → 1 맨 마지막 칸을 제거한다. 삭제된 위치의 다음 데이터를 삭제한 위치로 이동시킨다. 마지막 위치까지 (2)를 반복한다. 삭제할 위치의 데이터를 삭제한다. 다음은 선형 리스트에 맨 마지막에 빈칸을 추가하는 코드다. (1) 을 채우시오. katok.append(None)​..

목차 Disjoint Set (서로소 집합, 분리 집합) - Time Complexity 구현 - MakeSet(n) - find(x) - union(x, y) 최적화 - Path Compression - Path Halving - Path Splitting - Union by Rank - Union by Size Disjoint Set (서로소 집합, 분리 집합) 원소들의 모임을 표현하는 자료구조로, 각각의 집합은 공통된 원소가 없다. 주로 서로 다른 원소들이 동일한 집합에 속하는지 여부를 판별하는데 사용된다. Time Complexity 경로 압축과 트리 깊이 제어를 하는 로직이 없다면 선형 구조와 같은 예시에서 하나의 작업이 최대 O(N)이 될 수 있다. 하지만, 최적화를 위한 로직을 적용했다면, ..