Yang 코딩 공부

Heap 이란 -> 이진 트리의 한 종류로 (이진 힙 - binary heap) 이라고도 함 조건 1. 루트(root) 노드가 언제나 최댓값 또는 최솟값을 가진다 (최대 힙 - max heap, 최소 힙 - min heap) 2. 완전 이진 트리여야 한다. max heap -> 재귀적으로 정의 가능 : 어느 노드를 루트로 하는 서브트리도 모두 max heap 이다 이진 탐색 트리와의 비교 1. 원소들은 완전히 크기 순으로 정렬되어 있는가 ? X (이진 탐색 트리는 가능 ) 2. 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가 ? X (이진 탐색 트리는 가능) 3. 부가의 제약 조건은 어떤 것인가 -> heap은 완전 이진트리여야한다는 조건을 가진다 Max Heap의 추상적 자료 구조 연산의 정의 -..

: 정점 (node)과 간선(edge) 을 이용하여 데이터의 배치 형태를 추상화한 자료구조 노드는 루트노드, 내부노드, 리프노드 로 나뉜다 루트노드 : 가장 최상위에 위치한 노드 내부노드(Internal) : 루트도 리프도 아닌 노드 (중간 노드 들) 리프노드 : 더 이상 하위 노드가 없는 최하위 노드 노드들 사이에는 부모노드와 자식 노드가 존재하고 더 선택한 노드를 기준으로 더 상위에 가까운 노드를 부모(Parent)노드 더 하위에 가까운 노드를 자식(Child) 노드라고한다 (루트 노드는 자식노드만 리프노드는 부모 노드만 존재한다) 형제노드 : 같은 부모 아래 존재하는 노드를 형제(sibling) 노드라고 부른다 조상(ancestor) 노드 : 부모의 부모(의 부모의 ...) 후손(descendant..

원소의 삽입 원소의 삭제 두 리스트 합치기 원소의 삽입 코드 구현 주의 사항 (1) 사입하려는 위치가 리스트 맨 앞일 때 prev 없음 Head 조정 필요 (2) 삽입 하려는 위치가 리스트 맨 끝일 때 Tail 조정 필요 (3) 삽입 하려는 리스트가 빈 리스트인 경우 def insertAt(self, pos, newNone) # pos가 옳바른 위치에 잇는가 if pos self.nodeCount + 1: return False # 첫 위치에 삽입하는 경우 if pos == 1: newNode.next = self.head self.head = newNode else: if pos == self.nodeCount + 1: prev = self.tail else: prev = self.getAt(pos -..

추상적 자료구조 (Abstract Data Structures) Data 예 : 정수, 문자열, 레코드, ... A set of operations 삽입, 삭제, 순회 ... 정렬,탐색 연결 리스트(Linked Lists) 연결 리스트는 "각 원소들을 줄줄이 엮어서" 관리하는 방식입니다, 이때 각각의 아이템(칸 하나)를 Node라고 부른다. Node는 담은 데이터도 가지고 있지만 다음 노드가 어디있는지 링크데이터도 가지고있다. 리스트는 무조건 맨앞을 알아야하고 그것을 Head라고 부른다. 또한 리스트의 맨 끝 원소를 Tail이라고 부른다. 연결 리스트 안에 노드가 총 몇개 있는지 알고 있는것도 좋을 것. ex 코드 class LinkedList: def __init__(self): # 비어있는 연결 리스..

알고리즘 복잡도란 해당 문제를 해결하는데 있어서 얼마나 많은 자원을 사용하는가를 나타낸다 이는 둘로 나뉜다 시간 복잡도 (Time Complexity) 문제의 데이타 크기와 이를 해결하는 데 걸리는 시간 사이의 관계 공간 복잡도 (Spzce Complexity) 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계. 시간 복잡도를 알아 볼건데 이는 크게 둘로 나눈다. 평균 시간 복잡도 (Average Time Complexity) 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균 최악 시간 복잡도 (Worst-case Time Complexity) 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간 복잡도를 흔하게 쓰는 표기법이 있는데 Big-O Notation 점근 표기법 (asy..

재귀 알고리즘 (recursive algorithms) - 응용 조합의 수 (n 개의 서로 다른 원소에 m 개를 택하는 경우의 수) 구하기 하노이의 탑 (크기 순서로 쌓여 있는 원반을 한 막대에서 다른 막대로 옮기기) 피보나치 순열 조합의 수 n 개의 서로 다른 원소에 m 개를 택하는 경우의 수 # 빠른 풀이 from math import factorial as f def combi(n,m): return f(n) / (f(m) * f(n-m)) 조합의 수 계산 - 재귀적 방법 특정한 하나의 원소 입장에서 볼 때, 이 해당 원소를 포함하는 경우와 그렇지 않은 경우를 따로 계산해서 더한다. def combi(n, m): if n == m: return 1 elif m == 0: return 0 else: ..

재귀 알고리즘 (recursive algorithms) - 기초 주어진 문제가 있을 때, 이것을 같은 종류의 보다 쉬운 문제의 답을 이용해서 풀 수 있는 성질을 이용하여 같은 알고리즘을 반복적으로 적용함으로 써 풀어내는 방법. 재귀함수 (recursive functions) 란? 하나의 함수에서 **자신을 다시 호출**하여 작업을 수행하는 것. EX) 이진 트리(binary trees) 자연수의 합 구하기(1부터 n까지 모든 자연수의 합을 구하시오) def sum(n): if n = 2: return solution(x-1) + solution(x-2)

배열 - 정렬 (sort)과 탐색 (search) 정렬과 탐색은 많은 응용에 적용되는 알고리즘들 중에서도 가장 널리 알려져 있으며 활용도도 높은 것이라고 할 수 있다. 정렬과 탐색을 위한 여러 자료 구조와 알고리즘들이 있지만, 간단하게 선형 배열을 대상으로 정렬과 탐색의 기초를 배워본다. 정렬(sort)이란? 복수의 원소로 주어진 데이터를 정해진 기준에 따라 새로 늘어놓는 작업. Python의 리스트(list)를 이용한다면, 직접 정렬 알고리즘을 구현할 필요가 없다. list에 내장된 정렬 기능이 있기 때문인데, 아래 와같은 같은 두 방법이 대표적이다. 파이선 내장 함수 sorted() 리스트에 쓸 수 있는 메서드 .sort() 정렬 순서 반대로 reverse = True L2 = sorted(L, re..