백준 – 평범한 배낭(12865)

유명한 knapsack문제를 풀어봅니다

에라토스테네스의 체에서 제곱근 까지만 루프를 도는 이유

intro 에라토스테네스의 체로 소수를 판별하는 코드를 보면, n의 제곱근까지만 루프를 돌면서 index의 배수들을 소수목록에서 지운다. 보통 쉽게 한두줄로 왜 그런지 설명을 해놓았는데, 나는 이해가 잘 안가서 오래 생각을 해봤다. 아하! 그런거군! 자, 50까지의 수에서 2의 배수를 소수탈락 시켜보자. 2 * 2 / 2 * 3 / 2 * 4 ……. 2 * 25까지 지운다. 이제 […]

알고리즘을 위한 파이썬 – 집합

집합 교집합 합집합

트리의 순회 (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