one Book a Day

실패한 코드입니다. 최초는 규칙대로 gcd를 모두 구해가며 진행했으나 TLE가 납니다. 때문에 소인수분해를 해서 각 요소를 제거해가며 풀이하려 했으나 아직 로직이 완벽하지 못합니다. 추후 보완하겠습니다. import sys input = sys.stdin.readline from collections import defaultdict for test in range(int(input())): n = int(input()) a = list(map(int, input().split())) cnt = 0 primes = defaultdict(int) for i in range(n): tmp = a[i] for j in range(2, tmp + 1): if tmp == 1: break if not tmp % ..

문제의 핵심은 결국 에어컨으로부터 얼만큼의 거리에 있는가? 입니다. 백준의 최대 직사각형 만들기, SWEA의 수영장 가자 와 동일한 문제로 dp를 이용해 방해물이 없으면 기존값에서 거리값을 늘려가며 기록해주되 방해물(나보다 작은 온도의 에어컨)이 나타나면 그값에서 부터 다시 거리값을 기록해줍니다. 본 풀이는 좌, 우 다른 dp를 사용했으나 경험상 dp하나로도 구현할 수 있습니다. import sys input = sys.stdin.readline for test in range(int(input())): input() n, k = map(int, input().split()) a = list(map(lambda x: int(x) - 1, input().split())) t = list(map(int, i..

앞전의 이진수에서 1이 있는 자릿수를 계승하는 수열을 growing sequence라 하고 그렇지 않은 수열을 xor연산을 통해 growing sequence로 만들어 주는 수열을 Co-growing Sequence라 합니다. 전에 있는 값을 pivot으로 가져가야할 1의 위치를 저장하는 기준값으로 정하고 pivot에는 1이 있는데 현 수열의 값에는 없다면 Co-growing Sequence가 그만큼의 값을 가져가게끔 코드를 짰습니다. import sys input = sys.stdin.readline for test in range(int(input())): n = int(input()) x = list(map(int, input().split())) pivot = x[0] y = [0] * n for..

영어 독해가 매우 힘들었던 문제입니다. 이 문제는 열 추가와 열 조회로 나뉩니다. 지금 조회할 수 없는 열을 조회하면 불가능한 command로 판단하면 됩니다. 앞에서부터 0을 while로 넣어주고 그 후 0이 아닌값의 가능여부를 검사해 넣어주는 전략입니다. import sys input = sys.stdin.readline for test in range(int(input())): input() k, n, m = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) answer = [] idx_a = 0 idx_b = 0 while idx_a < n and not a[idx_a]: ..

a부터 좌우로 하나씩 연속되는 알파뱃을 붙혀가는 규칙. s가 규칙으로 만들어진 문자열이면 YES를 출력. 얼마전 현대모비스 알고리즘 대회 2번?의 열화판 당시는 deque로 풀었지만 이번에는 twopointer로 양끝에서부터 한 규칙씩 거슬러 올라가 마지막에 a가 남는 것까지 확인하는 전략을 세웠습니다. 최초 시작은 start로 총 문자열 길이에서 소문자 a의 아스키코드 넘버만큼 더해주고 a를 제외하는 의미에서 1을 빼주면 마지막 문자의 아스키코드 넘버가 됩니다. 거기서부터 확인해주면 됩니다. import sys input = sys.stdin.readline for test in range(int(input())): s = input().rstrip() left = 0 right = len(s) - 1..

점 a에서 b까지의 최소거리를 구하는 문제. 방해물 f가 한개 존재하지만 한개로는 무수히 많은 path를 방해할 수 없다. 방해 가능한 경우의 수는 a와 b와 f가 일직선상에 존재하고 f 가 두 점 사이에 있을 때. 이경우만 예외처리해서 +2 해주면 된다. import sys input = sys.stdin.readline for test in range(int(input())): input() a_x, a_y = map(int, input().split()) b_x, b_y = map(int, input().split()) if a_x < b_x: a_x, b_x = b_x, a_x if a_y < b_y: a_y, b_y = b_y, a_y f_x, f_y = map(int, input().split..

구현중 가장 귀찮은 구현이 배열 회전인것같다.. 확산, 회전순으로 과정압축없이 진행 위는 내코드 아래는 1등코드 1등코드는 내 코드보다 10배 빠르다. 차이점은 dusts를 배열로 관리했다는 것. 불필요한 과정이었던것같다. import sys input = sys.stdin.readline from collections import deque def rotate_dust(): up_cycle = deque() down_cycle = deque() up_cycle_down, down_cycle_up = air_clear[0][0], air_clear[1][0] # 0, 공기청정기 x 작은 좌표, 좌, 우 -> rotate(-1) for i in range(C): up_cycle.append(matrix[0..

사진틀을 dict로 관리 갯수 초과하면 하나 삭제 import sys input = sys.stdin.readline from collections import defaultdict N = int(input()) n = int(input()) nums = list(map(int, input().split())) count = defaultdict(int) for i in range(n): count[nums[i]] += 1 if len(count) > N: min_val = float('inf') for candidate in count: if candidate == nums[i]: continue if count[candidate] < min_val: min_val = count[candidate] t..

1등을 찾고 삭제한 그룹에서 1등을 찾으면 2등 그룹이 나온다. import sys input = sys.stdin.readline from collections import defaultdict while 1: N, M = map(int, input().split()) if not N and not M: break rankers = defaultdict(int) answer = [] max_cnt = 0 for _ in range(N): a = list(map(int, input().split())) for num in a: rankers[num] += 1 if rankers[num] > max_cnt: max_cnt = rankers[num] answer = [num] elif rankers[num]..

pivot을 정하고 배열의 요소를 교환해주는 식으로 해야 시간내 들어온다.(배열 복사해 병합하면 시간초과) def quick_sort(a, left, right): if left < right: pivot = a[left] start = left + 1 end = right while start