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에 루트를 씌운 값까지만 루프를 돌리면 […]

힙정렬

힙정렬은 비교적 빠른 정렬 방식중 하나이다. 먼저 트리와 힙에 대해서 알아본뒤, 힙정렬을 어떻게 하는지 알아보고 마지막으로 시간복잡도에 대해서 설명하겠다. Tree 위의 슬라이드에 보이는 것들이 모두 Tree구조이다. 이진트리 자식이 최대 2개있는 트리를 이진트리라고 부른다. 이진트리의 종류는 대표적으로 Full, Complete, Perfect가 있다. Full 이진트리중에서 자식 노드가 아예 없거나 혹은 2개 가지고 있는것을 Full 이진트리라고 부른다. Complete 왼쪽부터 […]

Peak 찾기

Peak란? [0, 5, 7, 7, 7, 7, 9, 0, 4] 라는 배열을 위처럼 그려본다면, 저 빨간색 동그라미들이 모두 peak이다. 즉, a <= b and b >= c를 만족하는 b가 peak인 것이다. 다만 마지막 4는 오른쪽에 값이 없기 때문에 그냥 그 4가 peak이다. Peak 찾기 전제 배열 안에 peak가 몇개있다는건 고려하지 않고 단순히 어떤 하나의 peak를 […]

2109번 – 순회강연

문제 https://www.acmicpc.net/problem/2109 풀이 코드

2138번 – 전구와 스위치

문제 https://www.acmicpc.net/problem/2138 풀이 코드

11066번 – 파일합치기

문제 https://www.acmicpc.net/problem/11066 풀이 코드 재귀로 풀기 하지만 이 코드는 PyPy3으로 돌려도 시간초과가 난다 ㅠ. 하지만 아래 C++은 잘 돌아간다. 왼쪽에서 오른쪽으로 채워가는 방식

1939번 – 중량제한

문제 https://www.acmicpc.net/problem/1939 풀이 코드

1780번 – 종이의 개수

문제 https://www.acmicpc.net/problem/1780 풀이 코드