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) :...

힙정렬

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

Peak 찾기

P

Peak란? [0, 5, 7, 7, 7, 7, 9, 0, 4] 라는 배열을 위처럼 그려본다면, 저 빨간색 동그라미들이 모두 peak이다. 즉, a <= b and b >= c를 만족하는 b가 peak인 것이다. 다만 마지막 4는 오른쪽에 값이 없기 때문에 그냥 그 4가 peak이다. Peak 찾기 전제 배열 안에 peak가 몇개있다는건 고려하지 않고 단순히 어떤 하나의 peak를 찾는다고 가정한다. 느린 방법 - 왼쪽부터 peak를 찾을때까지 비교 왼쪽값과 오른쪽값을 비교해서 왼쪽이 더 크거나 같으면 해당 배열의 peak중 하나가 그 왼쪽값이 된다. # -*- coding: utf-8 -*- def findSimplePeakSlowly(arr): length = len(arr) if...

2109번 – 순회강연

2

문제 풀이 코드 n = int(input()) pds = [] maxD = 0 for _ in range(n): p, d = map(int ,input().split()) pds.append((p, d)) maxD = max(maxD, d) def answer(): global pds, maxD pds = sorted(pds, reverse=True) memo = [0]*(maxD+1) count, fullCount = (0, len(memo)) for i in range(len(pds)): p, d = pds[i] if memo[d] == 0: memo[d] = p count += 1 else: for underD in range(d-1, 0, -1): if memo[underD] == 0:...

11066번 – 파일합치기

1

문제 풀이 코드 재귀로 풀기 from sys import stdin costs = [] minSums = [] arr = [] big = 10**8+1 def 최소합찾기(s, e): global arr, minSums if minSums[s][e] > 0: return minSums[s][e] if s == e: return 0 minSum = big for i in range(s, e): ls, le, rs, re = s, i, i+1, e minSums[ls][le], minSums[rs][re] = 최소합찾기(ls, le), 최소합찾기(rs, re) 후보 = minSums[ls][le]+minSums[rs][re]+(costs[re]) if ls > 0: 후보 -= costs[ls-1]...

1939번 – 중량제한

1

문제 풀이 코드 from sys import stdin from collections import deque n, m = map(int, input().split()) graph = {} ws = [] for _ in range(m): a, b, c = map(int, stdin.readline().split()) if graph.get(a) is None: graph[a] = [(b, c)] else: graph[a].append((b, c)) if graph.get(b) is None: graph[b] = [(a, c)] else: graph[b].append((a, c)) ws.append(c) S, E = map(int, input().split()) ws = sorted(ws) def...

1780번 – 종이의 개수

1

문제 풀이 코드 n = int(input()) B = [list(map(int, input().split())) for _ in range(n)] def answer(): global board counts = [0, 0, 0] boards = [B] while(len(boards) > 0): board = boards.pop() num, result = 모두같은숫자인지체크(board) if result is True: counts[num] += 1 elif (len(board) >= 3): boards.extend(종이자르기(board)) print(counts[-1]) print(counts[0]) print(counts[1]) def 종이자르기(board): s1, s2 =...