one Book a Day

heap으로 값이 작은것부터 정렬 시킨 뒤 누적합과 내 값을 비교해가며 왕이될 수 있는 값을 구해갔습니다. import sys input = sys.stdin.readline from heapq import heappop, heappush for test in range(int(input())): n = int(input()) arr = list(map(int, input().split())) heap = [] for idx, num in enumerate(arr): heappush(heap, (num, idx)) total, answer = 0, [] while heap: num, idx = heappop(heap) if total >= num: answer.append(idx + 1) else: an..

미리 범위 내 세제곱 수 구해놓은다음 매칭시켰스비낟. import sys input = sys.stdin.readline dic = {} for i in range(1, 10001): dic[i**3] = True for test in range(int(input())): x = int(input()) for num in dic: if x - num in dic: print("YES") break if num > x // 2: print("NO") break

카운팅 해준 후 넘치는거 모자란곳에 계속 옮겨줬습니다. import sys input = sys.stdin.readline def check(d): pivot = d[0] for i in range(1, 3): if d[i] != pivot: return True return False def move(over, d): global answer for i in range(3): if not over and d[i] > n // 3: pivot = d[i] - (n // 3) over.append((i, pivot)) d[i] -= pivot elif over and d[i] < n // 3: idx, num = over.pop() if idx < i: dist = num * (i - idx) else: ..

중간에 2의 배수가 몇개 채워져야 하나? 앞 뒤 비교해서 나누면서 세주거나 작은거에서 곱하면서 세주면 된다. import sys input = sys.stdin.readline for test in range(int(input())): n = int(input()) arr = list(map(int, input().split())) answer = 0 for i in range(n - 1): a, b = arr[i], arr[i + 1] if a > b: a, b = b, a while 2 * a < b: answer += 1 b /= 2 print(answer)

진법수로 변환할때 맨 앞부터 채울 생각을 했는데 다른 사람들 풀이보니 전부 뒷자리부터 채웠다.. 생각해보니 그렇게 해도 전혀 상관없는데 나는 무슨짓을 한건지.. def solution(n, t, m, p): answer = '' parse_table = {i: hex(i)[2:].upper() for i in range(16)} p -= 1 tmp = '0' num = 1 while len(tmp) = k: k *= n k //= n now = num while k: a = now // k tmp += parse_table[a] now -= a * k k //= n num += 1 for i in range(p, p + t * m, m): answer..

파일이름 뒤에 f를 붙혀 tail없는 예외를 없앤 후 head, number를 heap에 넣은 후 뽑아내며 정렬 from heapq import heappop, heappush def solution(files): answer = [] sort_arr = [] for pos, each_file in enumerate(files): tmp = each_file + 'f' flag = 0 for idx, char in enumerate(tmp): if not flag and char.isdigit(): start = idx flag = 1 elif flag and not char.isdigit(): end = idx break head, number = each_file[:start], each_file[s..

인접 행렬 V^2개의 원소를 가진 2차원배열. 인접 리스트 V개의 연결리스트( 동적 배열 ) vector기반이라 느리다. 간선 번호 붙일 때 불편하다 ( 순회하기 힘들다. ) 간선 배열 #include #include using namespace std; typedef pair pint; #define x first #define y second const int maxv = 100000, maxe = 200000; pint edge[maxe]; // 배열의 각 주소는 (x, y) 튜플 페어를 가짐. int st[maxv]; // 간선을 정렬한 후, 각 점에서 시작하는 간선의 첫 인덱스 int v, e; int main() { // Input cin >> v >> e; for (int i=1; i> ed..

내림차순 정렬 후 3번째 물건은 공짜로 계산하면 됩니다. import sys input = sys.stdin.readline n = int(input()) nums=sorted([int(input()) for _ in range(n)], reverse=True) answer = 0 for i in range(n): if not i % 3 == 2 : answer += nums[i] print(answer)

B가 오름차순이므로 이분탐색 upperbound로 내가 들어갈 자리 찾는다. import sys input = sys.stdin.readline from bisect import bisect_right N = int(input()) A = list(map(int, input().split())) B = list(map(int, input().split())) answer = [] for idx, a in enumerate(A): answer.append(bisect_right(B, a) - idx - 1) print(*answer)

Hash 데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것. 해시함수를 구현하여 데이터값을 해시값으로 매핑시킨다. 내부적으로 array를 사용해 데이터를 저장. 데이터 고유의 인덱스로 key의 고유 숫자 값이 저장됨. 특정 데이터만의 고유한 위치이기 때문에 삽입 연산 시 다른 데이터 사이에 끼어들어나 삭제시 다른 데이터로 채울 필요가 없음. 즉 추가적인 비용이 없도록 만들어진 구조. Hash Table 해시 테이블은 로 데이터를 저장하는 자료 구조 중 하나이다. Key값에 해시 함수를 적용해 index를 생성하고, index를 활용하여 값을 저장, 검색 할 수 있다. Key값을 해싱하여 검색, 저장하므로 평균 시간 복잡도는 O(1)이다. (항상 O(1)이 아닌 ..