6.5. Data Sturcture (15) 썸네일형 리스트형 7/6(목) IT 자료구조(16일차) / 15.검색/탐색트리 15. 정렬과 검색 #@title 무작위 import random as r def sequential_search(alist, target): for element in alist: if element == target: return True return False ss_list = [r.randint(1,30) for _ in range(8)] print(ss_list) target = r.randint(1,30) print(target) print(sequential_search(ss_list, target)) import random as r def binary_search_rec(alist, target, start, end): if start > end: return None mid = (sta.. 7/5(수) IT 자료구조(15일차) / 14.동적계획법 14. 동적 계획법(Dynamic Programming) + 원리 + 현재 문제의 환경을 알고 있음 + 문제를 작은 문제들로 분할 + 작은 문제를 다 풀면 큰 문제를 해결 가능 + 부분 문제 풀이의 결과를 다음 부분(중복) 문제를 풀 때 사용 + 특징 + 최적 하위구조 : Optimal Substructure\ + 최적의 세부 구조가 있다 + 답을 구하기 위해 했던 계산을 반복해야하는 문제의 구조 + 중복 하위문제 : Overlapping Problems + 작은 문제들의 해답이 겹침 + 분할정복 VS 동적 계획법 + 분할 정복 + 문제 풀이의 결과가 독립적 + 동적 계획법 + 문제들의 풀이 결과가 겹친다 + 결과값을 메모리에 저장 -> 캐싱 def fib_naive(n): if n == 0: retur.. 7/4(화) IT 자료구조(14일차) / 13. 특수 정렬 알고리즘 13. 특수 정렬 알고리즘 특수 정렬 알고리즘은 일반적인 정렬 알고리즘과는 다르게 특정한 기준에 따라 요소를 정렬하는 방식을 의미. 보다 특별한 규칙을 따르거나 특정한 요구 사항을 충족시키기 위해 사용되기도 함. 일반적인 정렬 알고리즘을 변형하거나 새로운 정렬 알고리즘을 개발하여 구현할 수 있으며, 특수 정렬 알고리즘의 선택은 주어진 문제나 데이터의 특성에 따라 달라짐. 예를 들어, 버블 정렬의 변형인 '개선된 버블 정렬'은 최솟값을 맨 끝으로 이동시키는 대신, 최솟값과 최댓값을 번갈아가며 정렬하는 특수 정렬 알고리즘임. 이렇게 하면 정렬된 요소들이 중앙을 기준으로 대칭적으로 배치됨. 또 다른 예로는 짝수와 홀수를 번갈아가며 정렬하는 특수 정렬 알고리즘이 있음. 이 알고리즘은 먼저 짝수 번째 인덱스에 짝.. 7/3(월) IT 자료구조(13일차) / 12. 고급 정렬 알고리즘 12. 고급 정렬 알고리즘 고급 정렬 알고리즘은 효율적으로 데이터를 정렬하기 위해 개발된 알고리즘. 이러한 알고리즘들은 일반적으로 일반적인 정렬 알고리즘인 버블 정렬이나 삽입 정렬보다 더 효율적인 성능을 제공함. 분할 정복(Divide and Conquer): 큰 문제를 작은 하위 문제로 분할하고, 각 하위 문제를 재귀적으로 해결한 다음, 그 결과를 결합하여 원래 문제의 해답을 얻는 알고리즘 설계 기법. 주요 아이디어: 1) 분할(Divide): 원래 문제를 작은 부분 문제로 분할. 문제를 반으로 쪼개는 것이 일반적이지만, 경우에 따라 다른 방식으로 분할할 수도 있음. 2) 정복(Conquer): 각 하위 문제를 재귀적으로 해결. 하위 문제가 충분히 작아서 직접 해결할 수 있는 경우에는 재귀 호출을 중단.. 6/27(화) IT 자료구조(10일차) / 10. 힙(Heap) (2) 10. 힙(Heap) 10-5. heapq 라이브러리 사용 heapq 라이브러리는 파이썬의 표준 라이브러리인 heapq 모듈을 의미. 이 모듈은 힙(heap) 자료구조를 구현하는 함수와 알고리즘을 제공. import heapq as hq import random as r # random.randint() list_data = [r.randint(1,30) for _ in range(6)] # 1부터 30까지 6개의 숫자를 무작위로 뽑음 print(list_data) print() # 최소 힙 : 기록순 정렬 print('힙 만들기') hq.heapify(list_data) # heapify(): 리스트를 힙으로 변환하는 역할 print(list_data) # print(list_data.pop(0)) #.. 6/28(수) IT 자료구조(11일차) / 11. 정렬 알고리즘 11. 정렬 알고리즘 주어진 데이터를 특정 기준에 따라 순서대로 정렬하는 알고리즘 11-1. 정렬 알고리즘의 종류 1) 기본 정렬 알고리즘 (O(n^2) 시간 복잡도): 선택 정렬(Selection Sort): 가장 작은 값을 선택하여 정렬되지 않은 부분의 맨 앞에 위치시키는 방식으로 정렬. 버블 정렬(Bubble Sort): 인접한 두 원소를 비교하여 필요한 경우 위치를 교환하여 정렬. 삽입 정렬(Insertion Sort): 정렬되지 않은 부분의 첫 번째 원소를 이미 정렬된 부분에 적절한 위치에 삽입하여 정렬. 2) 고급 정렬 알고리즘 / 분할 정복 (O(nlogn) 시간 복잡도): 병합 정렬(Merge Sort): 리스트를 반으로 나누고, 나누어진 부분 리스트를 재귀적으로 정렬하여 병합. 퀵 정렬(.. 6/26(월) IT 자료구조(9일차) / 10. 힙(Heap) (1) 10. 힙(Heap) 완전 이진 트리의 일종으로, 부모 노드와 자식 노드 간에 특정한 순서를 유지하는 자료구조. 힙은 일반적으로 배열로 구현되며, 해당 노드의 자식 노드들의 값보다 크거나 작은 순서를 가짐. 이를 힙 속성(Heap Property)이라고 함. 힙은 보통 최대 힙(Max Heap) 또는 최소 힙(Min Heap)으로 사용됨. 최대 힙은 부모 노드의 값이 자식 노드의 값보다 큰 순서를 가지며, 최소 힙은 부모 노드의 값이 자식 노드의 값보다 작은 순서를 가짐. 힙은 주로 다음과 같은 연산을 지원함: 삽입(Insert): 힙에 새로운 요소를 추가. 삭제(Delete): 힙에서 최대 또는 최소 값을 제거. 최대 값 또는 최소 값 확인: 힙의 최대 또는 최소 값을 반환하거나 확인. 힙은 주로 우선.. 6/22(목) IT 자료구조(8일차) / 9. 트리(Tree) 9. 트리(Tree) '계층'적인 구조를 가지는 비선형 자료구조로, 노드(Node)들의 집합으로 이루어짐. 트리는 하나의 루트(Root) 노드를 가지며, 루트 노드로부터 다른 노드들을 연결하는 가지(Edge)로 구성된다. 또한, 회로(Cycle)를 만들지 않는 것이 특징이다. 9-1. 용어 트리(Tree): 비선형의 자료구조로, '나무'와 같은 생김새라서 Tree라는 이름이 붙여짐. 노드(Node): 트리의 구성 요소. 각 노드는 데이터를 저장하고 있는 단위로서, 계층 구조에서 트리의 구성원으로 존재함. 루트(Root): 트리의 맨 위에 있는 노드. 전체 트리구조에 접근하기 위해 기억할 첫 번째 노드. 부모 노드가 없는 유일한 노드. 리프(Leaf): 트리의 가장 아래에 있는 노드 자식 노드가 하나도 없.. 이전 1 2 다음
