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

이진 트리를 순회하는 3가지 방식에 대해 알아보자. 트리의 모양 먼저 순회할 트리의 모양은 다음과 같다. Preorder preorder는 DFS랑 똑같다. 부모 노드가 앞(pre)에 온다 Inorder inorder는 부모 노드가 가운데(in)에 배치된다. Postorder postorder는 부모가 뒤(post)에 배치된다 이진 트리를 순회하는 3가지 방식에 대해 알아보자. 트리의 모양 먼저 순회할 트리의 모양은 다음과 같다. Preorder preorder는 DFS랑 똑같다. 부모 노드가 […]

다익스트라 알고리즘

다익스트라 알고리즘은 가중치가 있는 그래프에서 A지점 -> E지점 으로 가는 최단 경로를 찾을 때 사용합니다.

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

참고자료 https://www.slideshare.net/dahlmoon/collections-20160313 https://godoftyping.wordpress.com/2015/05/13/python-%EC%88%9C%EC%84%9C%EB%A5%BC-%EA%B8%B0%EC%96%B5%ED%95%98%EB%8A%94-%EC%82%AC%EC%A0%84%ED%98%95-ordereddict/ OrderedDict 파이썬에서 dictionary는 기본적으로 hashmap으로 만들어졌기 때문에 저장되는 순서를 고려하지 않는다. 그래서 dic.items() 함수가 항상 같은 순서의 배열을 리턴한다고 보장 할 수 없다(고한다..). 내부적으로 linked list를 사용해서 순서를 유지함 나중에 유용하게 쓰일 것 같다. Counter 원소들의 개수를 세준다. 매~우 유용하다. most_common() Counter를 튜플로 보여준다. 루프돌릴때 유용할것같다. defaultdict key에대한 default value를 지정해준다. 원래 […]

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

Permutations 순열, 줄세우는 여러가지 경우의 수 Combinations 조합, 주머니에서 n개를 뽑아서 나오는 모든 경우의수 Product 곱집합

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

참고자료 https://wikidocs.net/16043 키 중복 새로운 key-value 추가 Array to Dictionary 복사 얕은복사 b의 alice에만 5가 추가되어있을것 같지만, 실제로는 a에도 추가되어있다. 주소값을 복사했기 때문이다. 깊은복사 copy 모듈을 써서 deepcopy를 하면 값이 완전히 복사된다 Update 한번에 여러 원소들을 업데이트할때 update함수를 쓰면 좋다. 없는 key는 추가된다. Loop key 순서는 임의적이다. value key, value in array의 in이 값이 들어있는지 […]

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

Range reverse step 다만, 아래와 같은 경우에는 루프를 (당연히) 안돈다 Array to String 근데, 숫자는 안의 내용물을 문자로 바꿔주고 join해야한다 띄어 쓰기를 중간에 넣어주려면 Enumerate index와 value를 한꺼번에 얻고 싶을때 사용하면 좋을것같다 연산(=만들기) 곱하기로 여러개 만든다 더하기로 붙인다 주의 : A += B 와 A = A + B는 다르게 작동할 수 있다 x가 배열 […]

에라토스체네스의 체

이게뭐야? 위키피디아 쉽게 말하면, 소수를 찾는 방법이다. 소수라 함은 그 수의 약수가 1과 자기 자신만을 가지는거다. 파이썬 구현 어따씀? https://codeforces.com/contest/1332/problem/B

Bisect

Bisect란? 파이썬에서 Binary Search를 편하게 하라고 만든 모듈이다. bisect를 쓰면 특정값이 어디에 들어갈지 쉽게 알 수 있다. 예제 어떤 값(0, 150, 200 …)이 정렬된 배열(arr)에 들어간다 쳤을때, 그 인덱스를 알려준다.bisect_left는 위치를 찾으려는 값(200)이 배열에 이미 있다면(200) 그 있는놈의 왼쪽에 둔다는 말이다. 그래서, 위의 예제에서도 bisect.bisect_left(arr, 200)이 3이 아닌 1을 리턴한다. bisect_left는 범위도 지정할 수 있다.150을 […]

유클리드 호제법

사전지식 약수 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둘중에 […]

1억의 약수의 개수 구하기

첫번째 방법 소요시간 : 6.5초 두번째 방법 (예를들어) 12의 약수 [1, 2, 3, 4, 6, 12] 중 자신을 제외하고 가장 큰 약수는 12의 절반인 6이니까, 6까지만 12를 1~6으로 나누었을때 나머지가 0인지를 확인해보면 된다. 7~11은 어차피 약수가 아니니까 안나눠봐도 된다는 소리다. // -> 소수점을 버린다 소요시간 : 3.29초 세번째 방법 12에 루트를 씌운 값까지만 루프를 돌리면 […]