Coding Test/programmers

표병합 (구현, 유니온파인드)

""" UPDATE r c value : (r,c) value 저장 UPDATE value1 value2 : value1값 value2로 변경 MERGE r1 c1 r2 c2 : (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀을 선택하여 병합 UNMERGE r c: 병합을 해제 PRINT r c : (r, c) 위치의 셀 출력 """ def solution(commands): n=50 board=[[(i,j) for j in range(n)] for i in range(n)] # 좌표 넣고 병합셀이면 좌측좌표 저장 str_board=[['EMPTY']*n for _ in range(n)] # 값 저장 answer = [] for c in commands: arr=c.split() if arr[0]..

개인정보 수집 유효기간 (문자열, 구현)

""" 오늘 날짜를 의미하는 문자열 today, 약관의 유효기간을 담은 1차원 문자열 배열 terms 1 ≤ terms의 길이 ≤ 20 수집된 개인정보의 정보를 담은 1차원 문자열 배열 privacies 1 ≤ privacies의 길이 ≤ 100 파기해야 할 개인정보의 번호를 오름차순으로 1차원 정수 배열에 담아 return """ def solution(today, terms, privacies): answer = [] #오늘 날짜 nyear = int(today[:4]) nmonth = int(today[5:7]) nday = int(today[8:]) for i in range(len(terms)): for j in range(len(privacies)): if terms[i][0] == priva..

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

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

미로 탈출 명령어 (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을, 표..