반응형 📝 알고리즘7 🚶 큐(queue) 파이썬으로 구현하기! 큐에 대해서 알아보고 파이썬으로 구현해보기 큐(Queue)란? 선입선출(First In First Out, FIFO), 처음에 넣은게 가장 먼저 나옴 놀이공원 줄 서기를 생각하면 편하다 사용처 : 여러 작업들이 동시에(병렬적으로) 이루어져도 상관없는 경우, 의존관계 없는 경우 예시 : 스케쥴링 (운영체계 프로세스 관리) 큐의 추상 자료형(ADT) 객체 (characters) arr : T[], 데이터가 저장되는 배열, 리스트 front : int, 큐의 맨 앞부분 인덱스 rear : int, 큐의 맨 뒷부분 인덱스 연산 (operations) enqueue() : 맨 뒤에 원소를 넣음 dequeue() : 맨 앞 원소를 뺌 back() : 맨 뒤 원소를 확인 front() : 맨 앞 원소를 확인 isem.. 2023. 1. 16. 📚 스택 (Stack) 파이썬으로 구현하기! 스택에 대해서 알아보고, 파이썬으로 스택을 구현해보기 스택이란? 후입선출(Last In First Out, LIFO), 나중에 넣은게 가장 먼저 나옴 한쪽이 뚫려있는 통을 생각하면 편하다 사용처 : 어떤 작업이 다른 작업보다 먼저 이루어져야만 하는 경우, 의존관계 있는 경우, 재귀함수를 이용해 구현도 가능 DFS 예시 : 하드웨어 스택, 콜 스택 스택의 추상 자료형 (ADT) 객체 (characters) arr : T[], 데이터가 저장되는 배열, 리스트 top : int, 가장 나중에 저장된 데이터의 위치 연산 (operations) push() : 위에 새 요소를 넣음 pop() : 맨 위의 요소를 뺌 top() : 맨 위의 요소를 출력 isempty() : 스택이 비어있는지 확인 isfull() :.. 2023. 1. 15. 🧮 부분 집합, 멱집합 구하기 알고리즘 직접 구현! 부분집합, 멱집합을 구하는 알고리즘을 파이썬으로 구현해보자. 부분 집합, 멱 집합이란? 부분 집합은 어떤 집합에서 몇몇 원소들만 뽑아서 만든 집합. 부분 집합은 원래 집합에 포함되는 관계이다. 멱집합은 어떤 집합의 모든 부분 집합을 모아둔 집합 원소 갯수가 n인 원래 집합에서 원소 갯수가 r인 부분집합의 갯수는 nCr(조합)과 같다. 멱집합 원소의 갯수는 2^n이다. 부분 집합, 멱집합 알고리즘 구현해보기 부분 집합 조합을 구하는 방법과 같다. 아래 글 참고. 🧮 조합 알고리즘 직접 구현! 조합과 중복조합 알고리즘을 파이썬으로 구현하기 조합이란? 원소를 순서없이 나열하는 것 n개의 원소에서 r개를 조합하면 가짓수는 n!/(n-r)!r! 중복조합은 n+r-1개의 원소에서 r개를 조합하는 것 programm.. 2023. 1. 10. 🧮 조합 알고리즘 직접 구현! 조합과 중복조합 알고리즘을 파이썬으로 구현하기 조합이란? 원소를 순서없이 나열하는 것 n개의 원소에서 r개를 조합하면 가짓수는 n!/(n-r)!r! 중복조합은 n+r-1개의 원소에서 r개를 조합하는 것과 같다. n개의 원소에서 모든 조합 가지수는 2^n - 1 여러가지 조합 알고리즘 구현해보기 기본 조합 n개의 원소가 있는 배열에서 r개를 뽑는다. 조합 점화식에 기반한 방식 def combination(arr, r): if r == 0: return [set()] elif arr == []: return [] new_arr = arr[:] item = new_arr.pop() not_item_comb = combination(new_arr, r) item_comb = [s|{item} for s in c.. 2023. 1. 10. 🧮 순열 알고리즘 직접 구현! 순열과 중복순열 알고리즘을 파이썬으로 구현하기 순열이란? 원소들을 순서에 따라 나열하는 것 n개의 원소에서 r개를 나열한다 하면 그 가짓수는 n!/(n-r)! 중복해서 원소를 뽑으면 n^r 전체 순열 가짓수의 합은 조금 복잡하다. (링크) 여러가지 순열 알고리즘 구현해보기 기본 순열 n개의 원소를 가진 배열 arr에서 r개를 뽑아 나열한다. swap을 이용한 방식 def permutations (arr, r): n = len(arr) results = [] def _perm_swap (arr, depth): if (depth == r): results.append(arr[:r]) return for i in range(depth, n): # 위치를 바꿈 arr[i], arr[depth] = arr[dep.. 2023. 1. 10. ⚡ 고속 거듭제곱 알고리즘 간단설명! 요약 지수를 2진법으로 바꿈 밑을 제곱해서 올려가며 2진법에서 1일 때만 곱해줌 그냥 n번을 곱하면 복잡도 O(n)이나 이 방식은 O(log n)임 설명 def fast_pow(a, b): ret = 1 while b: if b%2: ret *= a a *= a b >>= 1 # 혹은 b //= 2 return ret print(fast_pow(2, 10)) 파이썬 코드 밑 a와 지수 b를 입력받음 b는 계속 2로 나눠주고, a는 계속 제곱을 시킴. b를 2로 나눈 값이 1일 때(2진수에서 해당 자리수가 1일때) 결과값에 제곱한 결과를 곱해줌. 2022. 10. 6. 이전 1 2 다음 반응형
