Total

[11726번] 2×n 타일링

11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 분석 D[N] : 길이 N으로 만들 수 있는 타일의 경우의 수 D[N-1] : n-1까지 타일이 채워져있는 경우 ➔ 새로운 타일 1개를 채워 N길이를 만듦 D[N-2] : n-2까지 타일이 채워져있는 경우 ➔가로로 타일 2개를 래워 N길이를 만듦 D[N] = D[N-1]+D[N-2] 풀이 # 2*n크기 직사각형을 2*1/1*n으로 채우는 방법의 수 n = int(input()) d=[0]*1001 # n의 최댓값 1000 d[1]=1 d[2]=2 for i in range(3, n+1..

[14501번] 퇴사

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net bottom up n = int(input()) s = [list(map(int, input().split())) for i in range(n)] dp = [0 for _ in range(n+1)] for i in range(n): for j in range(i+s[i][0], n+1): if dp[j] < dp[i] + s[i][1]: dp[j] = dp[i] + s[i][1] print(dp[-1]) top down n = int(input()) dp = [0]*(n+2) # 오늘부터 퇴사일까지 벌수있는 최대수입 (점화식 테이블) t=[0]*(n+1) # 상담에 필요한 일수 p=[0]*(n+1)..

택배 배달과 수거하기 (그리디)

""" 트럭에 실을 수 있는 재활용 택배 상자의 최대 개수 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]