Coding Test
택배 배달과 수거하기 (그리디)
""" 트럭에 실을 수 있는 재활용 택배 상자의 최대 개수 cap, 배달할 집의 개수를 나타내는 정수 n, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리 """ def solution(cap, n, deliveries, pickups): answer = 0 # 먼곳부터 배달하기위해 뒤집기 deliveries = deliveries[::-1] pickups = pickups[::-1] print("cap", cap) print(deliveries, pickups) # 배달해야 하는 양 have_to_..
이모티콘 할인행사 (완전 탐색, 조합)
def solution(users, emoticons): from itertools import product answer = [0, 0] # 모든 할인율 중복 조합 combi = product((40, 30, 20, 10), repeat=len(emoticons)) for discounts in combi: sold = [0, 0] # 이모티콘, 판매액 # 각 유저 for user_discount, user_money in users: sold_emoticons = 0 # 각 이모티콘과 할인율 for emoticon, discount in zip(emoticons, discounts): # 사용자 할인율 기준보다 많이 할인하면 구매 if discount >= user_discount: sold_emot..
[24042번] 횡단보도(다익스트라)
24042번: 횡단보도 당신은 집으로 가는 도중 복잡한 교차로를 만났다! 이 교차로에는 사람이 지나갈 수 있는 $N$ 개의 지역이 있고 그 지역 사이를 잇는 몇 개의 횡단보도가 있다. 모든 지역은 횡단보도를 통해 직, www.acmicpc.net 분석 시간 역행 불가, 이미 지난 가중치로 지나갈 수 없음 ➔ 주기 이전 소요 시간 ≤ 지금 이용하는 시간 값이 될 때까지 M을 여러 번 더하여(곱하여) 사용 풀이 import heapq import sys input = sys.stdin.readline n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] for i in range(m): a, b = map(int, input().split())..
미로 탈출 명령어 (DFS, 백트래킹)
문자열이 사전 순으로 가장 빠른 경로로 탈출 시간제한으로 방문하지 않아도 되는 경로는 탐색하지 않도록 조건 제한 """ 격자의 크기를 뜻하는 정수 n, m, 출발 위치를 뜻하는 정수 x, y, 탈출 지점을 뜻하는 정수 r, c, 탈출까지 이동해야 하는 거리를 뜻하는 정수 k 미로를 탈출하기 위한 경로를 return 미로를 탈출할 수 없는 경우 "impossible" """ import sys sys.setrecursionlimit(10**8) dAlpha = ['d', 'l', 'r', 'u'] dx = [1, 0, 0, -1] dy = [0, -1, 1, 0] answer = "z" def dfs(n, m, x, y, r, c, prev_s, cnt, k): global answer if k-cnt <..
표현가능한 이진 트리 (이진수 변환, 포화이진트리, 중위순회, 이분탐색)
세그먼트 트리, 인덱스 트리, 구간합 1. 세그먼트 트리 주어진 데이터의 구간합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조 2. 구간합 합배열(prefix sum)은 업데이트가 느림 arr[1]를 update 한다면 ? sum[1]부터 sum[9]까지 karla.tistory.com 트리 중위순회 노드갯수 len(n) 트리높이 int(math.log(len(n), 2)) 포화이진트리 2ᴷ-1, 비어있으면 앞에 0추가 """ 이진트리에서 리프 노드가 아닌 노드는 자신의 왼쪽 자식이 루트인 서브트리의 노드들보다 오른쪽에 있으며, 자신의 오른쪽 자식이 루트인 서브트리의 노드들보다 왼쪽에 있다고 가정합니다. numbers에 주어진 순서대로 하나의 이진트리로 해당 수를 표현할 수 있다면 1을, 표..
[14003번] 가장 긴 증가하는 부분 수열5 (LIS, 이분탐색)
14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 분석 D[i] : 0~i까지 i를 포함하는 가장 길게 가하는 수열의 길이 A[i]를 i번째 수열의 값이라고 정의하면 D[k]는 A[i]>A[K]를 만족하는 최대 수열의 길이 즉, A[i]보다 작은 값을 지니고 있는 수열의 최장 증가 수열의 길이들 중 최댓값을 찾아 해당 값에 +1 한 값을 D[i]에 저장 D[i] = max({D[k]}) +1 (k=1~i-1) D 리스트를 맨 뒤에서부터 탐색해 최댓값과 동일 값을 가지는 최초 inde..
[18353번] 병사 배치하기(LIS, 이중 for문)
18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net LIS 문항 수열 길이 입력값 복잡도 18353 병사배치 1 ~ 1,000 1~10,000,000 n² 12738 가장 긴 증가하는 부분 수열2,3 1 ~ 1,000,000 1~1,000,000 -1,000,000~1,000,000 nlogn 14003 가장 긴 증가하는 부분 수열5 1 ~ 1,000,000 -1,000,000,000~1,000,000,000 nlogn 분석 N(1~2,000) : 이중 for문으로 풀이 D[i]=array[i]를 마지막..
[12015/12738번] 가장 긴 증가하는 부분 수열2,3 (LIS, 이분탐색)
12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net LIS Longest Increasing Subsequence 풀이 import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) d = [0] for i in arr: if d[-1]
[2098번] 외판원 순회(TSP, 비트 마스킹)
2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 외판원 순회 (모든 도시를 순회하는 최단 거리) n≤11일 경우: 브루트포스(O(n!)) n≤12일 경우: 백트래킹 n≤16일 경우: DP + BitMasking (n2∗2n) 분석 D[c][v] : 현재 도시 c, 현재까지 방문한 모든 리스트 v, 앞으로 남은 모든 도시를 경유하는데 필요한 최소비용 점화식 : D[c][v] = min(d[c][v], d[i][v|(1
[11049번] 행렬 곱셈 순서 (행렬 곱 연산 횟수의 최솟값 구하기, DP)
11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 분석 풀이 import sys imput=sys.stdin.readline # 행렬의 갯수 n=int(input()) # 행렬 m=[] # 최소 연산 횟수 저장 리스트 d=[[-1 for j in range(n+1)] for i in range(n+1)] m.append((0,0)) for _ in range(n): x,y=map(int, input().split()) m.append((x,y)) def execute(s,e): result=sys.m..