반응형 언어별 개념 정리/Python16 [파이썬] 메모이제이션과 동적 프로그래밍 메모이제이션(memoization) 과 동적 프로그래밍(Dynamic Programming) 특징 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술. 재귀처럼 이전으로 돌아가는게 아니라 이미 저장된 값을 불러오는 것 재귀 vs 메모이제이션 대표적으로 피보나치 수열을 생각해보자. # 재귀로 구현한 피보나치 수열 def fibo(n): if n =2 and len(memo) 2023. 2. 19. [파이썬] 큐(Queue) 자료구조 정리 Queue 스택이 바닥이 막힌 세로로 세운 통이라면 큐는 양쪽이 뚫린 가로로 된 통의 형태 삽입, 삭제의 위치가 제한적인 자료구조 데이터 값을 저장하는 기본적인 구조이며, 일차원의 선형 자료구조 선입선출(First In First Out, FIFO)의 형태를 가짐 활용 스트리밍(streaming) 너비 우선 탐색(Breath First Search, BFS) Queue의 주요 연산 enQueue(tiem) : 큐의 뒤쪽에 원소를 삽입하는 연산 deQueue() : 큐의 앞쪽에서 원소를 삭제하고 반환하는 연산 createQueue() : 공백 상태의 큐를 생성하는 연산 isEmpty() : 큐가 공백상태인지를 확인하는 연산 isFull() : 큐가 포화상태인지를 확인하는 연산 Qpeek() : 큐의 앞쪽에.. 2023. 2. 15. [파이썬] 정렬 알고리즘 - 선택 정렬 선택 정렬(Selection Sort) 정렬과정 리스트 내의 최소값을 찾음 그 값을 리스트의 맨 앞에 위치한 값과 교환 맨 처음 위치를 제외한 나머지 값들을 대상으로 위 과정 반복 (시간 복잡도 O(n^2) Step 최솟값 7을 찾아 맨앞 35와 교환하고 다시 최소값을 찾음 다시 정렬 안된 리스트와 교환하고 위의 과정을 반복함 정렬되지 않은 마지막 원소가 가장 큰 값을 가지므로 정렬 완료 코드 구현 def selectionsort(arr) : n = len(arr) for i in range(n-1) : min_arr = i for j in range(i+1, n) : if arr[min_arr] > arr[j]: min_arr = j arr[i], arr[min_arr] = arr[min_arr], a.. 2023. 2. 12. [파이썬] 자료찾기 알고리즘 - 검색 방법(순차 검색, 이진 검색) 검색 방법(Search) 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업 순차 검색 (sequential search) 이진 검색 (binary search) 정렬되어 있지 않은 경우의 검색 과정 첫 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지 비교하며 찾음 키 값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환 자료구조의 마지막에 이를 때까지 검색 대상을 찾지 못하면 검색 실패 ex) [4, 9, 2, 7, 21] 에서 7을 검색하는경우 앞에서부터 체크 4≠7 → 9≠7 → 2≠7 ≠ 7 = 7 def search(a, key): x = 0 n = len(a) while x < n and a[x] != key : x += 1 if x 2023. 2. 12. [파이썬] 부분집합을 구하는 방법 부분집합 구하는 방법 부분집합의 수 각 원소가 n개 일 때, 공집합을 포함한 부분집합의 수는 2^n개 ex) [1,2,3,4,5] —> 2^5 = 32개 각 원소가 부분 집합에 포함되었는지 확인하는 방법 arr = [1,2,3,4,5] for i in range(2) : arr[0] = i for j in range(2) : arr[1] = j for k in range(2) : arr[2] = k for l in range(2) : arr[3] = l for n in range(2) : arr[4] = n print(arr) 부분집합을 for문을 이용하는 방법(비트 연산자 활용) 비트연산자 & : 비트 단위로 and 연산 | : 비트 단위로 or 연산 >피트연산자의 비트 열을 오른쪽으로 이동 arr =.. 2023. 2. 12. [파이썬] 정렬 알고리즘 - 버블 정렬 & 카운팅 정렬 버블 정렬 특징 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지로 이동하는 정렬 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬됨 (시간 복잡도 O(n^2)) 실제로 알고리즘 풀이에는 잘 쓸일 없음(시간 복잡도 때문) 정렬 과정 7, 6, 4 를 정렬한다고 해보자. Step 맨 앞의 7과 6의 자리를 서로 바꿔준다. 다시 반복해서 7과 4의 자리를 바꿔준다. (숫자가 더 많을 경우) 계속해서 반복해서 바꿔준다. 1번의 싸이클이 돌고 난 후 다시 처음부터 같은 작업을 반복한다 버블 정렬 코드 def Bubblesort(List): #정렬할 list, 원소 수 N for i in range(len(List)-1, 0.. 2023. 2. 12. 이전 1 2 3 다음 반응형
