one Book a Day

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

분할정복으로 병합정렬을 실시하며 좌 우배열의 마지막 값만 비교해 전역변수 answer에 누적시킴. def merge_arr(left_arr, right_arr): global answer if left_arr[-1] > right_arr[-1]: answer += 1 merge_arr = [] left_idx, right_idx = 0, 0 n, m = len(left_arr), len(right_arr) while left_idx != n and right_idx != m: if left_arr[left_idx]

뒤쪽의 큰값을 찾아 교환하며 탐색한 후 혹시 이미 내림차순 정렬이 완료됐는데 교환 횟수를 소모하지 못했을 경우 홀수면 맨뒤 두개 교환, 짝수면 그대로 반환시킨다. def dfs(idx, cnt): global answer if cnt == int(target): answer = max(int("".join(nums)), answer) return for now in range(idx, n): for max_idx in range(now + 1, n): if nums[now]

숫자 M의 뒤에서 N개의 요소가 1인것을 확인하기 위해 M자체를 shift 해주며 확인했습니다. for test in range(1, int(input()) + 1): N, M = map(int, input().split()) for i in range(N): if not M & 1: answer = 'OFF' break M >>= 1 else: answer = 'ON' print(f'#{test} {answer}')

암호를 찾으면 7자리씩 decoding하고 배열에 저장해 유효성 판단하고 값을 반환합니다. 따로 알고리즘이 필요한 문제는 아닙니다. for test in range(1, int(input()) + 1): N, M = map(int, input().split()) nums = {'0001101': 0, '0011001': 1, '0010011': 2, '0111101': 3, '0100011': 4, '0110001': 5, '0101111': 6, '0111011': 7, '0110111': 8, '0001011': 9} bits = [] for _ in range(N): a = input() idx = 0 if bits: continue while idx < M - 7: idx += 1 if a[idx..

각 경우의 수를 check 해주면 된다. def check(player, num): if player[num] == 3: return True if num > 1 and player[num - 1] and player[num - 2]: return True if num < 9 and player[num + 1] and player[num + 2]: return True if num and not num==9 and player[num + 1] and player[num - 1]: return True return False for test in range(1, int(input()) + 1): nums = list(map(int, input().split())) a = {i: 0 for i in rang..

웰노운. 빨리 끝나는 순으로 정렬 후 시작점과 비교해주며 작업 할당(그리디) for test in range(1, int(input()) + 1): N = int(input()) works = [tuple(map(int, input().split())) for _ in range(N)] works.sort(key=lambda x: (x[1], x[0])) last_finish = 0 cnt = 0 for s, e in works: if s >= last_finish: last_finish = e cnt += 1 print(f'#{test} {cnt}')

요새 비슷한 문제 너무 많이 풀었다. 매칭문제. 투포인터로 매칭 for test in range(1, int(input()) + 1): N, M = map(int, input().split()) w = list(map(int, input().split())) t = list(map(int, input().split())) t.sort(reverse=True) w.sort(reverse=True) answer = 0 left = 0 for truck in t: while left < N and truck < w[left]: left += 1 if left == N: break answer += w[left] left += 1 print(f'#{test} {answer}')

마찬가지로 백트래킹 문제. def dfs(depth, cur_node, total): global min_sum if depth == N-1: min_sum = min(min_sum, total + matrix[cur_node][0]) return if total > min_sum: return for next_node in range(N): if not col_check[next_node]: col_check[next_node] = True dfs(depth + 1, next_node, total + matrix[cur_node][next_node]) col_check[next_node] = False for test in range(1, int(input()) + 1): N = int(input())..

백트래킹문제. def dfs(x, y, total): global min_sum if total > min_sum: return if x == N - 1 and y == N - 1: min_sum = min(min_sum, total) return for dx, dy in delta: nx, ny = x + dx, y + dy if nx < N and ny < N: dfs(nx, ny, total + matrix[nx][ny]) for test in range(1, int(input()) + 1): N = int(input()) matrix = [list(map(int, input().split())) for _ in range(N)] delta = ((1, 0), (0, 1)) min_sum = flo..