본문 바로가기

Algorithm 💡272

[백준 7562번] 나이트의 이동 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net from collections import deque t = int(input()) dx = [-1,-2,-2,-1,1,2,2,1] dy = [-2,-1,1,2,-2,-1,1,2] for _ in range(t): n = int(input()) start_x, start_y = map(int,input().split()) dest_x, dest_y = map(int,input().split()) visited = [[-1]*n for _ in range(n)] d.. 2023. 10. 18.
[백준 17136번] 색종이 붙이기 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net area = [list(map(int,input().split())) for _ in range(10)] size_count = [0]*5 min_value = float("inf") def check(x,y,n): # n 크기의 색종이를 붙일 수 있는 확인하는 함수 if (x + n - 1) >= 10 or (y + n - 1) >= 10: return False for i in range(n+1): for j in range(n+1): if area[.. 2023. 10. 14.
[백준 1753번] 최단경로 - 다익스트라(Dijkstra Algorithm) 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net import sys import heapq input = sys.stdin.readline v, e = map(int,input().split()) INF = float("inf") graph = [[] for _ in range(v+1)] distance = [INF]*(v+1) start_node = int(input()) for _ in range(e): start, end, cost = map(int,input().s.. 2023. 10. 7.
[백준 1916번] 최소비용 구하기 - 다익스트라(Dijkstra Algorithm) 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net import heapq import sys input = sys.stdin.readline n = int(input()) m = int(input()) INF = float("inf") graph = [[] for _ in range(n+1)] distance = [INF]*(n+1) for _ in range(m): start, end, cost = map(int,input().split()) graph[start].appen.. 2023. 10. 7.
[백준 12100번] 2048(Easy) - 구현 / 시뮬레이션 / 완전탐색 / 백트래킹 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net # 4x4 크기 보드 # 한번 이동할 때 보드 위에 있는 모든 블록이 상-하-좌-우 중 하나로 이동 # 같은 값을 갖는 두 블록이 충돌하면 합쳐짐 # 한번의 이동에서 합쳐진 블록은 다시 합쳐질 수 X import copy n = int(input()) zone = [list(map(int,input().split())) for _ in range(n)] max_value = -1 # 왼쪽으로 이동시키는 함수 def moveLeft():.. 2023. 10. 7.
[백준 1049번] 기타줄 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net # 끊어진 기타줄 개수 N # 기타줄 브랜드 M # 각 브랜드마다 판매중인 6개의 패키지의 가격, 낱개 가격 # 적어도 N개를 사기 위해 필요한 돈의 "최솟값" n,m = map(int,input().split()) prices = [list(map(int,input().split())) for _ in range(m)] min_package = min([x[0] for x in prices]) min_item = min([x[1] for x in price.. 2023. 10. 7.

티스토리툴바