개념

트리의 순회 (pre, in, post order)

이진 트리를 순회하는 3가지 방식에 대해 알아보자. 트리의 모양 먼저 순회할 트리의 모양은 다음과 같다. from collections import deque class Node: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right class Tree: L, R = 'left', 'right' def __init__(self, rootVal): self.rootNode = Node(rootVal) def insert(self, val): emptyNode = self.findEmptyNode() if emptyNode[1] == Tree.L: emptyNode[0]...

알고리즘을 위한 파이썬 – Collections

참고자료 OrderedDict 파이썬에서 dictionary는 기본적으로 hashmap으로 만들어졌기 때문에 저장되는 순서를 고려하지 않는다. 그래서 dic.items() 함수가 항상 같은 순서의 배열을 리턴한다고 보장 할 수 없다(고한다..). 내부적으로 linked list를 사용해서 순서를 유지함 from collections import OrderedDict a = OrderedDict([['a', 1], ['b', 2], ['c', 3]]) print(a) # OrderedDict([('a', 1), ('b', 2), ('c', 3)]) 나중에 유용하게 쓰일 것 같다. Counter 원소들의 개수를 세준다. 매~우 유용하다. from collections import Counter items =...

알고리즘을 위한 파이썬 – 순열/조합

Permutations 순열, 줄세우는 여러가지 경우의 수 from itertools import permutations items = [1, 2, 3] perms = permutations(items, 2) print(list(perms)) # [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)] Combinations 조합, 주머니에서 n개를 뽑아서 나오는 모든 경우의수 from itertools import combinations items = [1, 2, 3] combs = combinations(items, 2) print(list(combs)) # [(1, 2), (1, 3), (2, 3)] Product 곱집합 from itertools import...

알고리즘을 위한 파이썬 – Dictionary

참고자료 키 중복 dic = { 'a': 2, 'a': 5 } print(dic) # {'a': 5} 새로운 key-value 추가 dic = { 'a': 2 } dic['b'] = 100 print(dic) # {'a': 2, 'b': 100} Array to Dictionary list = [('a', 10), ('b', 20)] dic = dict(list) print(dic) # {'a': 10, 'b': 20} list = [(10, 'a'), (20, 'b')] dic = dict(list) print(dic) # {10: 'a', 20: 'b'} 복사 얕은복사 a = {'alice': [1, 2, 3], 'bob': 20, 'tony': 15, 'suzy': 30} b = a.copy()...

알고리즘을 위한 파이썬 – Array

Range reverse a = [1, 23, 5, 6, 7] for i in range(len(a), -1, -1) : print(i) step for i in range(0, 20, 2) : print(i) # 0 2 4 6 ~ 20 test = [4, 3, 5, 11, 5] for i in range(20, 0, -2) : print(i) # 20 18 16 14 ... 2 다만, 아래와 같은 경우에는 루프를 (당연히) 안돈다 for i in range(10, 20, -2): print(i) Array to String list1 = ['a', 'b', 'c'] str1 = ''.join(list1) 근데, 숫자는 안의 내용물을 문자로 바꿔주고 join해야한다 list1 = [1, 2, 3] str1...

에라토스체네스의 체

이게뭐야?

위키피디아

쉽게 말하면, 소수를 찾는 방법이다. 소수라 함은 그 수의 약수가 1과 자기 자신만을 가지는거다.

파이썬 구현

def prime_list(n):
# 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
n = n + 1 # 이렇게 하면 소수목록에서 조회할때 -1 안해줘도 된다
sieve = [True] * n

# n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
m = int(n ** 0.5)
for i in range(2, m + 1):
if sieve[i]: # i가 소수인 경우
for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
sieve[j] = False

# 소수 목록 산출
return sieve

어따씀?

Bisect

B

Bisect란? 파이썬에서 Binary Search를 편하게 하라고 만든 모듈이다. bisect를 쓰면 특정값이 어디에 들어갈지 쉽게 알 수 있다. 예제 import bisect arr = [100, 200, 300] print(bisect.bisect_left(arr, 0)) # 0 print(bisect.bisect_left(arr, 150)) # 1 print(bisect.bisect_left(arr, 200)) # 1 print(bisect.bisect_left(arr, 250)) # 2 print(bisect.bisect_left(arr, 300)) # 2 print(bisect.bisect_left(arr, 350)) # 3 어떤 값(0, 150, 200 ...)이 정렬된 배열(arr)에...

유클리드 호제법

사전지식 약수 12와 28의 약수는 ? 12의 약수 => 1 2 3 4 6 12 28의 약수 => 1 2 4 7 14 28 서로소 공약수가 1밖에 없는 두수를 서로소 관계에 있다고 한다. 예를들어, 17과 8은 서로소 관계에 있다. 공약수가 1밖에 없기 때문이다. 최대공약수 두 수의 공약수중 가장 큰것. 12와 28의 최대공약수는 4이다. 2와 4둘중에 4가 더 크기 때문이다. 최대공약수 구하는 방법 첫번째(노가다) 12의 약수와 28의 약수를 구한다음에 공통된것을 찾고(공약수), 그중에 가장 큰것(최대공약수)을 찾으면 된다. 직관적이지만, 유클리드 호제법보다 속도가 느리다는 단점이 있다. 두번째(유클리드호제법) 유클리드 호제법이란? A, B의 최대공약수를 G라고 할때(A > B)[28과 12의...

1억의 약수의 개수 구하기

1

첫번째 방법 import time n = 100000000 factors = [] s = time.time() for i in range(1, n+1) : if n%i == 0 : factors.append(0) print('소요시간 : ', time.time() - s) 소요시간 : 6.5초 두번째 방법 (예를들어) 12의 약수 [1, 2, 3, 4, 6, 12] 중 자신을 제외하고 가장 큰 약수는 12의 절반인 6이니까, 6까지만 12를 1~6으로 나누었을때 나머지가 0인지를 확인해보면 된다. 7~11은 어차피 약수가 아니니까 안나눠봐도 된다는 소리다. import time n = 100000000 factors = [] s = time.time() for i in range(1, n//2 +1) :...