Python

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/77486 문제 해설 Idea Union-Find 알고리즘의 Find() 함수를 사용하여 부모 노드에 대해 재귀적으로 접근 최악의 경우 O(NM)=10^10으로 시간 초과가 발생하지만, 매 탐색마다 최대 10,000원을 10씩 나눠 0이 되는 순간에 재귀가 종료되기 때문에 최대 깊이가 5로 좁혀짐 Time Complexity O(N) = 100,000 Data Size enroll, referral: str(10) * 10,000 seller: str(10) * 100,000 amount: int(100) * 100,000 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def find(parents, cur, income, answer): alloc = income//10 if parents[cur] == cur or alloc == 0: answer[cur] += income-alloc return answer[cur] += income-alloc find(parents, parents[cur], alloc, answer) return def solution(enroll, referral, seller, amount): N = len(enroll) answer = [0] * N name2id = {name:i for i,name in enumerate(enroll)} parents = [i if referral[i]=='-' else name2id[referral[i]] for i in range(N)] for i in range(len(seller)): find(parents, name2id[seller[i]], amount[i]*100, answer) return answer

문제 링크 https://www.acmicpc.net/problem/1182 문제 해설 Idea Brute Force 전체 배열에서 1부터 N개의 부분 조합을 완전탐색하면서 합이 S와 같은 경우를 카운트하고 출력 Data Size N: 1 <= int <= 20 S: abs(int) <= 1,000,000 arr: int(100,000) * N 해설 코드 1 2 3 4 5 6 7 8 9 10 11 from itertools import combinations N, S = map(int, input().split()) arr = list(map(int, input().split())) count = 0 for i in range(1,N+1): comb = combinations(arr, i) count += sum(map(lambda x: sum(x)==S, comb)) print(count)

문제 링크 https://www.acmicpc.net/problem/11725 문제 해설 Idea BFS 1번 노드부터 BFS를 수행하면서 다음 노드에 순차적으로 접근 다음 노드가 이미 방문한 노드의 경우 부모 노드라 판단하여 배열에 저장 부모 노드가 저장된 배열에 대해 2번 노드부터 순차적으로 부모 노드를 출력 Time Complexity O(N+E) = 200,000 Data Size N: 2 <= int <= 100,000 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 from collections import deque import sys input = sys....

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/68936 문제 해설 Idea Divide and Conquer 2차원 배열을 4등분씩 나눠 재귀함수를 호출하고 동일한 값으로 채워져 있는지 판단하여 값의 개수 증가 2^n 형태의 정수에 대해 NumPy를 활용해 행렬 인덱싱을 간단히 구현 Time Complexity O(N^2 Log N^2) = 20,000,000 Data Size arr: [[int(1)]], shape(2^n, 2^n) 1 <= 2^n <= 1024 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 import numpy as np def quad_comp(n, arr, answer): values = np....

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/87390 문제 해설 Idea Greedy n의 크기가 굉장히 크기 때문에 2차원 배열을 만드는 것만으로 시간 초과가 발생할 것을 예상 r행 c열의 값은 max(r,c)+1과 같고 1차원 배열의 인덱스 i에 대해 r은 i//n, c는 i%n와 동일 left부터 right까지의 인덱스를 규칙에 맞는 값으로 변환하여 반환 Time Complexity O(N) = 10^5 Data Size n: 1 <= int <= 10^7 left, right: 0 <= long <= n^2 right - left < 10^5 해설 코드 1 2 def solution(n, left, right): return [max(divmod(i,n))+1 for i in range(left,right+1)]