분류 전체보기

최종 코드import sysfrom collections import dequeinput=sys.stdin.readlinerectangle=[list(map(int,input().split())) for _ in range(4)]characterX,characterY=map(int,input().split())itemX,itemY=map(int,input().split())dx = [0, 1, -1, 0]dy = [-1, 0, 0, 1]maps = [[0] * 101 for _ in range(101)]me = [[0] * 101 for _ in range(101)]for i in range(len(rectangle)): l_d_x, l_d_y = rectangle[i][0]*2, rectangle..

최종 코드import sysfrom collections import dequeinput = sys.stdin.readlinetickets=[list(map(str,input().strip().split(" "))) for _ in range(5)]# #BFS# answer=[]# q=deque()# q.append(("ICN",["ICN"],[]))## while q:# airport,path,used=q.popleft()## if len(used)==len(tickets):# answer.append(path)## for idx,ticket in enumerate(tickets):# if ticket[0] == airport and not idx in..

탐색search 이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다.프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다른다.대표적인 탐색 알고리즘으로 DFS와 BFS를 꼽을 수 있는데 이를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 전제 되어야한다. 자료구조 Data Structure '데이터를 표현하고 관리하고 처리하기 위한구조'를 의미한다.그중 스택과 큐는 자료구조의 기초개념이다.삽입(push) : 데이터를 삽입한다.삭제(pop) : 데이터를 삭제한다.실제로 스택과 큐를 사용할 때는 삽입과 삭제 외에도 오버플로와 언더플로를 고민해야 한다.오버플로는 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할..

웅덩이를 피해 학교로 가는 모든 경로의 수를 구하는 문제이다. 방향은 오른쪽과 아래쪽으로만 갈 수 있다.모든 경로의 수를 1,000,000,007로 나눈 나머지를 return한다.def solution(m, n, puddles): mod=10**9+7 dp=[[0]*(m+1) for _ in range(n+1)] puddles_set=set((y,x) for x,y in puddles) dp[1][1]=1 for i in range(1,n+1): for j in range(1,m+1): if (i,j) in puddles_set: dp[i][j]=0 else: if i>1 ..

모든 섬을 통행 가능하도록 만들 때 최소 비용을 구하는 문제이다. 최소 신장 트리 (MST)를 활용하는 문제이다.def find_parent(parent,a): if parent[a] != a: parent[a]=find_parent(parent,parent[a]) return parent[a]def union(parent,a,b): a=find_parent(parent,a) b=find_parent(parent,b) if a내가 사용한 알고리즘은 크루스칼 알고리즘이다.정점의 갯수만큼 부모 리스트를 생성한다. 모든 정점의 초기 부모는 자기 자신이다.모든 간선을 비용을 기준으로 오름차순 정렬 한다. costs정렬costs를 순회하며 간선을 하나씩 확인한다.정점..

🌲 최소 신장 트리(MST-Minimum Spanning Tree)란?정의: 무방향 가중치 그래프에서 모든 정점을 연결하면서 간선 가중치의 합이 최소가 되는 트리를 의미합니다.조건모든 정점이 연결되어 있어야 함 (연결 그래프)사이클이 없어야 함 (트리 구조)정점의 갯수가 V인 그래프의 최소 신장 트리는 V-1개의 간선을 가진다.📌 크루스칼 알고리즘 (Kruskal's Algorithm)🔧 핵심 아이디어"간선을 하나씩 가중치가 작은 순으로 선택하되, 사이클을 만들지 않도록 유니온-파인드(Disjoint Set)를 이용해서 연결한다."🪜 동작 순서간선을 가중치 기준으로 오름차순 정렬한다.가장 가중치가 낮은 간선부터 하나씩 선택한다.선택한 두 정점이 **서로 다른 집합(사이클 X)**이면 연결한다.모든..