본문 바로가기

Algorithm245

[백준] 5972번 - 택배 배송 (파이썬) # 택배 배송 import heapq import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = [[]for _ in range(N+1)] for _ in range(M): a, b, cost = map(int, input().split()) arr[a].append((cost, b)) arr[b].append((cost, a)) def dijkstra(): q = [] heapq.heappush(q, (0, 1)) total = [sys.maxsize] * (N+1) total[1] = 0 while q: cost, node = heapq.heappop(q) if node == N: return total[node] if t.. 2022. 4. 1.
[프로그래머스] Lv2 - 메뉴 리뉴얼 (파이썬) https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr from collections import defaultdict from itertools import combinations as comb def solution(orders, course): # 모든 조합을 딕셔너리에 기록 dict = defaultdict(int) for x in orders: get_all_comb(list(x), course, dict) .. 2022. 3. 31.
[프로그래머스] Lv2 - 행렬 테두리 회전하기 (파이썬) https://programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr import sys def solution(rows, columns, queries): arr = [[(i)*columns+(j+1) for j in range(columns)] for i in range(rows)] result = [] for x1, y1, x2, y2 in queries: result.append(change(x1-1, y.. 2022. 3. 31.
[백준] 1719번 - 택배 (파이썬) # 택배 import sys input = sys.stdin.readline n, m = map(int, input().split()) arr = [[sys.maxsize] * (n+1) for _ in range(n+1)] for i in range(1, n+1): arr[i][i] = 0 for _ in range(m): x, y, cost = map(int, input().split()) arr[x][y] = cost arr[y][x] = cost result = [[j for j in range(n+1)] for i in range(n+1)] for i in range(1, n+1): result[i][i] = '-' for k in range(1, n+1): for i in range(1, n+.. 2022. 3. 31.
[프로그래머스] Lv2 - 짝지어 제거하기 (파이썬) https://programmers.co.kr/learn/courses/30/lessons/12973 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr def solution(s): answer = 0 if can_remove(s) else 1 return answer def can_remove(s): stack = [] for x in s: if not stack: stack.append(x) else: if stack[-1] == x: stack.pop() else: stack.append(x).. 2022. 3. 30.
[프로그래머스] Lv2 - 124 나라의 숫자 (파이썬) https://programmers.co.kr/learn/courses/30/lessons/12899 코딩테스트 연습 - 124 나라의 숫자 programmers.co.kr def solution(n): dic = {1: 1, 2: 2, 0: 4} result = '' while n: result += str(dic[n % 3]) n = n//3 if n % 3 else n//3-1 return result[::-1] 풀이 1. 딕셔너리 정의 : 1, 2, 0 키를 각각 1, 2, 4 값으로 설정해준다. 2. 3진법을 이용해서 result에 추가해나간다. (단, 0이 없으므로 4를 사용할 때는 -1을 해주어야 함) 3. result를 역순으로 출력 사용할 수 있는 숫자는 1, 2, 4로 총 3개이므로 3.. 2022. 3. 30.
[백준] 1477번 - 휴게소 세우기 (파이썬) # 휴게소 세우기 N, M, L = map(int, input().split()) arr = [0]+list(map(int, input().split()))+[L] arr.sort() start, end = 1, L-1 result = 0 while start mid: # 나눈 만큼 휴게소를 설치 (현재 설치 돼있는 구역은 제외해야해서 -1) count += (arr[i]-arr[i-1]-1)//mid if count > M: start = mid+1 else: end = mid-1 result = mid print(result) 이분탐색 1. 입력을 받으면서 휴게소 배열(arr)의 양 끝에 출발지점과 도착지점을 추가해주고 정렬 2. start, end는 휴게소 위치의 범위 3. 이분탐색 - mid : .. 2022. 3. 30.

티스토리툴바