개발일기/Python

[Python] - 이진검색트리

이진트리 * 트리 자료구조 - 트리는 나무를 거꾸로 뒤집어 놓은 형태 *이진트리 : 자식 노드가 최대 2개(좌우노드라고도함) *이진검색 트리 : 이진트리중 활용도가 높은 트리로, 값 크기를 기준으로 일정형태로 구성 (왼쪽 자식노드는 나보다 작고, 오른쪽자식노드는 나보다 크다, 같거나 기준 붙어도 ok) *포화이진트리 : 루트로부터 시작해서 모든 노드가 정확히 두개 씩의 자식노드를 가지도록 꽉 채워진 트리 노드수가 2의 k제곱 - 1 *전 이진트리 : 모든 자신 노드 개수가 0개 또는 2개 *완전 이진트리 : 노드의 수가 맞지 않아 포화 이진트리를 만들 수 없을 때 왼쪽부터 모두 채워나간 이진트리(포화이진트리만들어나가는 과정) 이진검색트리검색 이진검색트리에서의 값 검색 -> 매우 빠르게 검색가능 ,완전 이..

[Python] - 축소정복

축소정복기법 ◆ 주어진 문제와 더 작은 문제간의 관계를 이용하는 전략 - 예 : n! = n * (n-1)! - 분할정복기법의 일종 ◆ 적용방식 - 하향식 : 순환(재귀)구조 #팩토리얼(하향식 축소정복기법) def factorial_recur(n): if n == 1: return 1 else: return(n*factorial_recur(n-1)) - 상향식 : 반복구조 #팩토리얼(상향식 축소정복기법) def factorial_iter(n): result = 1 for k in range(1,n+1): result = result * k return result 문제 축소형태 1. 고정크기축소 - 팩토리얼(일정한 크기의 수만큼 일정하게 줄어든다) 2. 고정 비율 축소 - 이진탐색, 거듭제곱(문제가 일정..

[Python] 알고리즘 - 완전탐색

억지기법 문제의 정의를 바탕으로 한 가장 직접적인 방법 예) 최대공약수 방법, a^n구하는 알고리즘 등... 억지기법의 중요성 : 쉬운문제 어렵게 풀필요없다, 광범위하게 문제적용가능, 실제로 더 빠를수도, 이론적인 기반이 된다 정렬, 탐색, 기하학적문제, 완전탐색, 그래프탐색 선택정렬 - 정렬문제에 대한 가장 직접적인 해결방법 - 입력리스트에서 가장 작은 항목을 찾고 이것을 꺼내 정렬된 리스트에 순서대로 저장한다(입력된 리스트와 같은 크기의 리스트 1개를 추가 필요로함) * 제자리 정렬을 위한 알고리즘 개선 -> 정렬이 안된 리스트에서 최솟값이 선택되면 이 값을 새로운 리스트가 아닌 첫 번째 요소와 교환한다. -> n-1번 반복(n번쨰는 자동으로 큰 값이니까!) def selection_sort(A): ..

[Python] 기본적인 자료구조 - 그래프(Graph)

그래프(graph) - 현상이나 사물을 정점 vertex(node)와 간선edge로 표현한것 Graph G = (V,E) V : 정점집합 V : 간선집합 - 두 정점이 간선으로 연결되어 있으면 인접 adjacent하다고 한다.= 이웃관계에 있다고 표현하기도 한다. * 그래프의 종류 - 무방향성 그래프 : 간선에 방향이 없는 그래프 정점표현 = {A,B,C,D} 간선표현 = { (A,B) , (C,D) } - 방향성 그래프 : 간선에 방향이 있는 그래프 정점표현 = {A,B,C,D} 간선표현 = { , } ≠ 가중치 그래프 : 간선마다 가중치가 다르게 부여된 그래프 - 간선에 방향이 없는 그래프 - 간선에 방향이 있는 그래프 그래프 표현법 - 그래프는 정점의 집합과 간선의 집합의 결합 -> 그래프를 표현하..

[Python] 알고리즘 효율성 분석

오늘은 알고리즘 효율성 분석에 대해 알아보려고 한다. * 좋은 알고리즘은? - 시간효율성 : 이론적분석에 사용, 컴퓨터마다 다르게 측정된다. - 공간효율성 : 코드효율성(코드 보수성), 알고리즘이 사용하는 메모리 공간 ====> 보통 시간 효율성을 더 중요시 한다고 한다. ====> BUT! 이론적인 복잡도 분석 > 절대적인 시간 측정 * 알고리즘 복잡도 분석에서 중요한 점 1. 알고리즘에서 입력의 크기는 무엇인가? 2. 복잡도에 영향을 미치는 가장 핵심적인 기본 연산은 무엇인가? 3. 입력의 크기가 증가함에 따라 처리시간은 어떤 형태로 증가하는가? 4. 입력의 특성에 따라 알고리즘 효율성에는 어떤 차이가 있는가? 1. 입력의 크기 - 알고리즘의 효율성은 입력크기(개수)의 함수형태로 표현 - 무엇이 입력..

[Python] 알고리즘 - 최대 공약수 구하기(유클리드 알고리즘)

유클리드 알고리즘 이용 gcd(a,b) = gcd(b, a mod b) def gcd(a,b): #a가 b보다 작지 않아야 한다 while b != 0 : #b가 0이면 멈춤 r = a % b a = b b = r return a

[Python] 알고리즘 - 최대값찾기

*사용자로부터 입력 : input()* 1. 첫 번째 방법 def find_max(A): max = A[0] for i in range(len(A)): #range(start,end,step) : start이상, end미만, step간격 if A[i] > max: max = A[i] return max array = [int(n) for n in input().split()] print(array, "최댓값 = ", find_max(array)) 2. 두 번째 방법(좀 더 간결하게!) def find_max(A): max = A[0] for i in A[1:] if i > max: max = i return max array = [int(n) for n in input().split()] print(ar..

[Python] 기본적인 자료구조 - 리스트(list), 스택, 큐

자료구조 중 리스트를 알아보자! ArrayList : 배열을 만들어 순서대로 저장한다 LinkedList : 노드 형태로 원소를 저장한다. Singly Linked List, Doubly Linked List(이중연결리스트), Circular Linked List(원형연결리스트), Circular Doubly Linked List가 존재 ▶Singly Linked List : 항상 Head부터 시작한다. 그래서 마지막 원소를 알고싶어도 처음부터 시작해야한다는 점! 그래서 Tail을 이용해 맨 마지막 원소를 가리키게 하기도 한다.(단 역방향 불가) * python에서는 맨마지막원소가 가리키는 것을 None이라고하고 C에서는 Null이라고 한다. ▶Circular Linked List(원형연결리스트) : 순..

[Python] 리스트(List)관련 자주 쓰이는 기능 정리

● Python에서 list란? → 정보 여러 개를 하나로 묶어 저장하고 관리할 수 있는 기능 → 숫자 여러개는 파이썬의 리스트 기능을 이용하면 쉽게 관리 가능 → 리스트는 대괄호[] 안에 정보 여러개를 쉼표(,)로 구분하여 적는다. ◆ 리스트에서 자주 쓰이는 기능 ♥ len(A) : 리스트길이(자료 개수)를 구한다. ex) len(A), len( [1, 2, 3] ) ♥ append(x) : 자료 x를 리스트의 맨 뒤에 추가한다. ex) A.append(4) ♥ insert(i,x) : 리스트의 i번 위치에 x를 추가한다. ex) A.insert(0, 5) #0번 위치에 원소5를 추가한다. ♥ pop(i) : i번 위치에 있는 자료를 리스트에서 빼내면서 그 값을 함수의 결과값으로 돌려준다. i를 지정하..