맛대의 블로그

트리 트리 용어 비선형 구조 원소(node)들 간에 1:n 관계를 가지는 자료구조 계층 관계를 가지는 구조(상위 원소에서 하위 원소로 갈수록 확장) root = 최상위 노드, 트리의 시작 노드 leaf = 단말 노드 , 최 하단 노드 형제 노드(sibling node) - 같은 부모를 가진 노드 조상 노드 = 간선을 따라 루트까지 이어지는 경로상의 모든 노드 자손 노드 = 서브 트리에 있는 모든 하위 노드 간선(edge) = 노드를 연결하는 선 서브 트리 : 부모 노드와 간선을 끊었을때 새롭게 생성되는 트리 차수(degree) 노드의 차수 : 노드에 연결된 자식 노드의 수 (바로 밑) 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값 높이 노드의 높이 : 루트에서 노드까지 이르는 간선의 수 트..

큐(Queue) 뒤에서는 값을 추가만 하고, 앞에서는 삭제만 하는 구조 선입선출 구조(FIFO:First In First Out) 들어온 순서대로 삭제됨 주요 연산 enQueue(item) 큐의 뒤쪽에 원소(item)를 추가하는 연산 deQueue() 큐의 앞쪽 원소를 삭제하고 반환하는 연산 createQueue() 공백 상태의 큐를 생성하는 연산 isEmpty() 큐가 공백상태인지를 확인하는 연산 isFull() 큐가 포화상태인지를 확인하는 연산 Qpeek() 큐의 맨앞 원소를 삭제없이 반환만 하는 연산 선형 큐 #선형 큐 만들어봄 class Queue: def __init__(self,size): self.size = size #배열의 크기 self.front = -1 #첫 원소의 인덱스(머리부분) ..

최소 신장 트리(MST) & 최단 경로 최소 신장 트리(MST) 그래프에서 최소 비용 문제 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리 두 정점 사이의 최소 비용의 경로 찾기 신장 트리 n 개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 싸이클이 존재 x 최소 신장 트리(Minimum Spanning Tree) 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 Prim 알고리즘 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식 정점 한곳에서 시작 선택한 정점과 인접한 정점중에 최소 비용의 간선이 존재하는 곳을 선택 다시 선택된 정점들 중에서 위 과정 반복 KRUSKAL 알고리즘 간..

정수론(Number Theory) 모듈러 연산 (a+b)%c == (a%c+b%c)%c 7%3 == 1 8%3 == 2 (7+8)%3 == 0 (7%3+8%3)%3 == 0 number = ac + d number//c == a number%c == d A = ac + x B = bc + y A+B = (a+b)c + (x+y) 정리 (a+b) % c == (a%c + b%c) % c (a-b) % c == (a%c - b%c + c) % c # +c해주는 것은 a%c-b%c가 음수가 되는것을 방지 (a*b) % c == (a%c * b%c) % c 모듈러 나눗셈 (a/b) % c = (a*(b**-1))%c = (a*c)*((b**-1)%c)%c (b**-1)%c가 문제 페르마의 소정리, 유클리드 호제..

완전 탐색 & 그리디 반복(Iteration)과 재귀(Recursion) 반복 구조 초기화 변수의 초기값 설정 조건검사 반복할 명령문 실행 업데이트 무한 루프가 되지 않게 업데이트 #반복을 이용한 선택 정렬 def Selction_sort(ls): n = len(ls) for i in range(n-1): min_num = i for j in range(i+1,n): if ls[j] < ls[min_num]: min_num = j ls[min_num],ls[i] = ls[i],ls[min_num] 재귀 함수 내부에서 직접,간접적으로 자기 자신을 호출하는 함수 반복 구조에 비해 간결하고 이해하기 쉽다 반복되는 함수 호출 과정에서 메모리 스택이 쌓여 성능 저하 발생 #팩토리얼 재귀 def factorial(..

스택(Stack) 스택 자료를 쌓아 올린 형태의 자료구조 선형 구조를 가짐 선형구조 : 자료 간의 관계가 1:1 비선형구조: 자료간의 관계가 1:N 마지막에 삽입한 자료를 가장 먼저 꺼낸다(후입선출Last-In-First_Out) top : 마지막 삽입된 원소의 위치 연산 class stack: def __init__(self): self.items = [] self.top = -1 def push(self,item): self.top +=1 self.items.append(item) def pop(self,item): value = self.items[self.top] self.items[self.top] = None self.top -= 1 return value def isEmpty(self): i..

서로소 집합(Disjoint-sets) or 상호배타 집합 서로 중복 포함된 원소가 없는 집합들(교집합이 없음) 집합에 속한 하나의 특정 멤버를 통해 각 집합을 구분 가능(대표자,representative) 연결 리스트, 트리를 통해 상호배타 집합 표현 가능 연산 Make-Set(x) : 유일한 멤버 x를 포함하는 새로운 집합을 만드는 연산 Find-Set(x) : x를 포함하는 집합을 찾는 연산 Union(x,y) : x와 y를 포함하는 두 집합을 통합하는 연산, y를 포함하는 집합의 대표를 x집합 대표로 변경 연결리스트 같은 집합의 원소들을 하나의 연결리스트로 관리 연결리스트의 맨 앞 원소가 집합의 대표 원소 각 원소는 집합의 대표 원소를 가리키는 링크를 가짐 a,b,c 가 한집합에 a가 대표일 경우..

배열 Array 시간 복잡도 실제 걸리는 시간을 측정 실행되는 명령문의 개수를 계산 빅-O표기와 비슷(가장 큰 영향력을 주는 N에 대한 항만 표시) 정렬 버블 정렬(Bubble Sort) 첫 번째 원소부터 시작하여 인접한 원소와 비교하여 자리를 바꾸며 이동 시간복잡도 O(n^2) def Bubble_sort(bubble,N) : #정렬할 list, 원소 수 for i in range(N-1,0,-1): for j in range(i): if bubble[j] > bubble[j+1]: bubble[j],bubble[j+1] = bubble[j+1],bubble[j] 카운팅 정렬(Conuting Sort) 각 항목이 몇 개씩 있는지 세는 작업을 하여 정렬 시간복잡도 O(n+k) : n=리스트길이,k=정수의..

Brute Force 문자열을 처음부터 끝까지 차례대로 순회하면서 문자를 일일이 비교하는 방식 find_str = &#39;ljm&#39; target = &#39;my name is ljm&#39; str_len = len(find_str) target_len = len(target) def Brute_force(find_str,target): i = 0 #target 순회 j = 0 #find_str 순회 while j < str_len and i < target_len : if target[i] != find_str[j]: #다음 시작점으로 이동 i = i - j j -= 1 i += 1 j += 1 if j == str_len : return i - str_len else: return -1 pr..