목록Algorithms (64)
# 첫접근 # Brute Force로 하려했다... # 하지만 이후 조건에서 10, [1,2,3] 주어졌을 때 또 다시 조합을 늘려가야 했기 때문에 풀이 불가 # 5 # 1 * 5 # 1 + 2*2 # 1*3 + 2*1 # 5*1 # 10, [1,2,3,5,10] # 1,2,3,4,5 로 조합하는 방법 from itertools import combinations def solution(n, money): answer = 0 money.sort() for i in range(1, len(money)+1): for m in combinations(money, i): temp = 0 if sum(m) > n: break else: temp = n - sum(m) return answer % 100000000..
from collections import deque def move(cur1, cur2, board): dirs = [(1,0), (0,1), (-1,0), (0,-1)] ret = [] for y, x in dirs: if board[cur1[0]+y][cur1[1]+x] == 0 and board[cur2[0]+y][cur2[1]+x] == 0: ret.append({(cur1[0]+y, cur1[1]+x), (cur2[0]+y, cur2[1]+x)}) rotate = [1,-1] # 가로로 위치해있는 로봇 회전 if cur1[0] == cur2[0]: for r in rotate: if board[cur1[0]+r][cur1[1]] == 0 and board[cur2[0]+r][cur2[1]] =..
# return 최소한의 친구들 투입 # 외벽 길이(1~200), 취약 지점 위치(길이:1~15, 원소:0~n-1), 한시간동안 이동가능 거리(길이:1~8, 원소:1~100) # 1. 시작점 선정 # 2. 각 시작점 별 시계 반시계 방향으로 갔을 때 다 들리는 값 구하기 from collections import deque from itertools import permutations # 친구 투입 후 다음 친구 투입 def nxt_idx(queue, d, start_idx=0): # 시작점 start_num = queue[start_idx] # i = 거리 for i in range(1, d+1): try: # 이동 가능 거리 안에서 다음 취약점 포함되는 경우 if queue[start_idx + 1]..
# 인덱스 범위 맞추는게 항상 헷갈린다.. # 인덱스 끝에 맞춰서 -1 방식이 마지막 인덱스 -1 경우 보다 인덱스 범위 맞추기 쉬운것같다. def solution(triangle): dp = [[] for _ in range(len(triangle))] dp[0].append(triangle[0][0]) # i = 다음 dp / i-1 = 이전 dp for i in range(1, len(triangle)): # 다음 dp의 범위 for j in range(i+1): # 맨 왼쪽끼리 더하기 if j == 0: dp[i].append(dp[i-1][0] + triangle[i][j]) # 맨 오른쪽끼리 더하기 elif j == i: dp[i].append(dp[i-1][-1] + triangle[i][j..
from collections import defaultdict, deque def bfs(graph, start, distances, visited): q = deque([start]) visited[start] = True while q: current = q.popleft() for adj in graph[current]: if not visited[adj]: visited[adj] = True q.append(adj) distances[adj] = distances[current] + 1 def solution(n, edge): # 그래프 만들기 graph = defaultdict(list) visited = [False] * (n+1) for x, y in edge: graph[x].append..
- 포함 관계에 대한 이해 필요 # return 최소 카메라 설치 갯수 # 차량: 1~ 10000 # [진입, 진출] # 진입, 진출 지점에 카메라 설치도 만난 것 # -30000 ~ 진입, 진출 ~ 30000 # 교점이 많은 부분에 설치하는게 이득 from copy import deepcopy def solution(routes): answer = 0 n = len(routes) check = [0] * n start = sorted(routes, key=lambda x: x[0])[0][0] end = sorted(routes, key=lambda x: x[1])[-1][1] checked = set() # 전체 구간 for idx in range(start, end+1): new_checked = ..